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、123
• 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 循环时需要特别注意越界问题同时在涉及解引用时也要注意越界问题

今天的选择题都和数据在内存中的存储有关编程题则比较简单无非就是进行遍历判断比较编码时需要注意越界问题

---

相关文章推荐

Day1 组队竞赛、删除公共字符

C++题解 | 逆波兰表达式相关

C语言题解 | 去重数组&&合并数组

C语言题解 | 消失的数字&轮转数组