选择题
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 循环时，需要特别注意越界问题，同时在涉及解引用时，也要注意越界问题
今天的选择题都和数据在内存中的存储有关；编程题则比较简单，无非就是进行遍历判断比较，编码时需要注意越界问题
相关文章推荐
Day2 排序子序列、倒置字符串
Day1 组队竞赛、删除公共字符
C++题解 | 逆波兰表达式相关
C语言题解 | 去重数组&&合并数组
C语言题解 | 消失的数字&轮转数组
