Day3 字符串中找出连续最长的数字串、数组中出现次数超过一半的数字
Day3 字符串中找出连续最长的数字串、数组中出现次数超过一半的数字
选择题
1.进程管理
题目：32位系统中，定义 **a[3][4] ,则变量占用内存空间为（）
选项：
- A、4
- B、48
- C、192
- D、12
分析：本题考的是 指针 大小及数组大小的计算，在 32 位平台下，指针大小为 4byte，而在 64 位平台下，指针大小为 8byte；在计算二维数组的大小时，需要通过 行 * 列 * 类型大小 的方式进行计算
在本题中，a 为一个 二维二级指针数组，无论是几级指针，在 32 位平台中都为 4byte，因此 a 的实际占用空间为 3 * 4 * 4 = 48
注意： 数组名表示数组中首元素的地址，但存在两种特殊情况：
sizeof(数组名)计算的是整个数组的大小&数组名取出的是整个数组的地址
结果：
B
2.计算机组成原理
题目：假设在一个 32 位 little endian（小端序） 的机器上运行下面的程序，结果是多少？
#include <stdio.h>
int main() {
long long a = 1, b = 2, c = 3;
printf("%d %d %d\n", a, b, c);
return 0;
}选项：
- A、1，2，3
- B、1、0、2
- C、1、3、2
- D、3、2、1
分析：在 小端序 机器中，低位存储数据的低地址，大端序 则相反；long long 占用 8byte 大小的空间，%d 匹配 int，占用 4byte 空间，当强行使用 %d 匹配 long long 输出数据时，会发生截断行为，导致数据读取时出现错位
关于 大小端序的相关问题可以查看这篇文章：《C语言进阶——数据在内存中的存储》
结合 printf 打印时的栈帧，可以得到下图中的分析
注意： 在栈中，先入栈的最后出，因此是 c 先入栈、最后出栈；高精度数据向低精度数据进行转换时，会发生 截断 行为，导致数据丢失，因此要注意数据与格式匹配（long long 匹配格式为 lld）
结果：
B
编程题
1.字符串中找出连续最长的数字串
题目链接：OR59 字符串中找出连续最长的数字串
题目分析：存在一个字符串 str，其中包含数字和其他字符，要求计算出 最长的数字子串；题目比较简单，直接 遍历+判断+统计，不断更新 最长数字子串的值，即可得到答案
遇见数字时，记录当前位置 begin，不断向后走，直到遇见非数字或结尾，记录当前位置为 end，构造字符串并与历史记录的最长数字子串进行比较，如果比其长，则更新 numStr
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
while (getline(cin, str))
{
string numStr; //最长数字子串
auto it = str.begin();
while (it < str.end())
{
if (isdigit(*it))
{
//通过区间构造数字子串
auto begin = it;
while (it != str.end() && isdigit(*it))
++it;
auto end = it;
string tmp(begin, end);
//更新最长的数字子串
if (tmp.size() > numStr.size())
numStr = tmp;
}
else
++it;
}
cout << numStr << endl;
}
}注意： 在进行 while 循环时，需要特别注意边界问题，避免出现越界
2.数组中出现次数超过一半的数字
题目链接：JZ39 数组中出现次数超过一半的数
题目分析：非常经典的题目，存在一个数组，其中某个数值超过了数组长度的一半，要求找出这个数，既然某个数超过了数组长度的一半，那么我们可以将其中的每个数出现次数统计起来，再次遍历即可确定这个数，当然这种解法比较废空间，除此之外，我们还可以将数组进行排序，中位数即出现次数超过一半的值
解法一：通过容器将其中的值与出现次数进行统计 这里使用
map对数据进行存储，然后对map进行遍历确认数值即可 时间复杂度：N+logN+N / 2空间复杂度：N / 2
#include <map>
class Solution
{
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
map<int, int> table; //建立 kv 表
for(auto e : numbers)
table[e]++;
int n = numbers.size() / 2; //数组长度
for(auto e : table)
{
//这个数值必然存在
if(e.second > n)
return e.first;
}
return 0;
}
};这种解法时间和空间效率都比较低，优点就是比较容易想到
解法二：将数组进行排序，然后返回中位数 排序后，出现次数超过一半的值，必然位于中间 时间复杂度：
N * logN空间复杂度：logN
class Solution
{
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
//先将数据进行排序
sort(numbers.begin(), numbers.end());
//直接返回中位数值
return numbers[numbers.size() / 2];
}
};这个代码就更简单了，直接两行解决问题，不过还是不符合进阶要求
解法三：将数组中，不相同的两个值置为
-1，最后再遍历数组，不为-1的值，就是目标 因为某个值出现次数超过一半，所以每 “去除” 两个不同的值，必然会将 某个值 以外的全部值去除，剩下的自然就是目标值了 时间复杂度：N + N—>N空间复杂度：1
class Solution
{
public:
int MoreThanHalfNum_Solution(vector<int> numbers)
{
size_t i = 0;
size_t j = 0;
while (i < numbers.size() && j < numbers.size())
{
// j 找到与 i 不同的值
while (j < numbers.size() && numbers[i] == numbers[j])
j++;
//如果两个都没有越界，则置 -1
if(i < numbers.size() && j < numbers.size())
numbers[i] = numbers[j] = -1;
//将 -1 跳过（-1 不参与比较）
while (i + 1 < numbers.size() && numbers[i + 1] == -1)
i++;
while (j + 1 < numbers.size() && numbers[j + 1] == -1)
j++;
i++;
j++;
}
//再次遍历，不为 -1 的值就是目标值
for (auto e : numbers)
{
if (e != -1)
return e;
}
return 0;
}
};这种解法是最优解，即减少了时间，也兼顾了空间
注意： 在进行 while 循环时，需要特别注意越界问题，同时在涉及解引用时，也要注意越界问题
今天的选择题都和数据在内存中的存储有关；编程题则比较简单，无非就是进行遍历判断比较，编码时需要注意越界问题
腾讯云开发者
