LeetCode-探险模式-数据结构与算法

知识点记录

  此文用于记录学习 $\text{LeetCode}$ 网站探险模式的数据结构与算法板块获得的知识点。ƪ(˘⌣˘)ʃ

数组 $\text{1}$

 $\text{Q1.}$ 数组串联

  最直接的思路就是遍历两次参数数组即可，时间、空间复杂度均为 $\text{O(n)}$，不多赘述，笔者写的代码如下：

class Solution {
public:
    vector<int> getConcatenation(vector<int>& nums) {
        vector<int> ans;
        for (int times = 0; times < 2; times++) {
            for (int i = 0; i < nums.size(); i++) {
                ans.push_back(nums[i]);
            }
        }
        return ans;
    }
};

 $\text{Q2.}$ 重新排列数组

  将数组拆为左右两个来看，新建答案数组，依次左右各录入一个数即可。

  上述思路的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        vector<int> ans;
        for (int i = 0; i < nums.size() / 2; i++) {
            ans.push_back(nums[i]);
            ans.push_back(nums[i + nums.size() / 2]);
        }
        return ans;
    }
};

  记：学习题解得到一个新的解法，可以在时间复杂度不变的情况下将空间复杂度降为 $\text{O(1)}$，即直接在原数组上做操作。

  原理是观察到题中所给的数据规模：1 <= nums[i] <= 10^3，推出一个这样的 $\text{int}$ 型元素其实最多只占用了 $\text{32}$ 比特位中的低 $\text{10}$ 位，于是我们可以利用剩余的比特位存储当前角标下正确排序的元素值，比如第 $\text{11-20}$ 位。存储时将目标值乘以 $\text{1024}$ 后与原值相加，替换时除以 $\text{1024}$ 取回。

  复写代码如下：

class Solution {
public:
    vector<int> shuffle(vector<int>& nums, int n) {
        for (int i = 0; i < 2 * n; i++) {
            // 观察原来处于 i 位的元素会被置于哪里
            int j;
            if (i < n) {
                j = 2 * i;
            }
            else {
                j = 2 * (i - n) + 1;
            }
            // 由于在遍历时，i 位元素的值会发生变化，这时只应该考虑低十位，使用按位且过滤
            nums[j] += (nums[i] & 1023) * 1024;
            // 乘 1024 本质是按位移，故 x * 1024 可以写为 x << 10，前提是有效位不能左溢出
        }
        for (int i = 0; i < 2 * n; i++) {
            nums[i] = nums[i] / 1024;
            // 同理，x / 1024 也可以写为 x >> 10，前提是有效位不能右溢出
        }
        return nums;
    }
};

 $\text{Q3.}$ 最大连续 $\text{1}$ 的个数

  新建临时结果数组 $\text{ans}$，存储每一段连续 $\text{1}$ 的个数；新建暂存值 $\text{temp}$，初始化为 $\text{0}$。

  $\text{temp}$ 每遇 $\text{1}$ 则自加 $\text{1}$ ，每遇 $\text{0}$ 则先存入当前值，再归 $\text{0}$，最终得到所有连续 $\text{1}$ 段各自的长度。比较出最大值可得出结果，该法的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        vector<int> ans;
        int temp = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]) {
                temp++;
            }
            else {
                ans.push_back(temp);
                temp = 0;
            }
            if (i == nums.size() - 1) {
                ans.push_back(temp);
            }
        }
        int end = 0;
        for (int i = 0; i < ans.size(); i++) {
            if (end < ans[i]) {
                end = ans[i];
            }
        }
        return end;
    }
};

  记：学习题解得到一个新的解法，可以在时间复杂度不变的情况下将空间复杂度降为 $\text{O(1)}$，即直接在原二值 $\text{int}$ 数组上做操作，添加前缀和使数组变为一般的 $\text{int}$ 型数组。

  如下例所示，我们可以修改第 $\text{i}$ 位元素的值，使其变成在当前段中是第几个 $\text{1}$。于是， $\text{1}$ 段越长，其最后一个 $\text{1}$ 对应位置上的值越大，最后直接比较 $\text{nums}$ 数组中的值，其最大值即最长连续 $\text{1}$ 段的长。

角标 0 1 2 3 4 5 6 7
数值 1 1 0 0 1 1 1 0
改为 1 2 0 0 1 2 3 0 => 观察到实际上就是从角标为 1 的位置开始改，如果是 1，则修改值为当前值同前一位值相加，形成前缀和
                    => i for 1:n-1，如果 nums[i] == 1，则修改值为 nums[i] + nums[i-1]

  复写代码如下：

class Solution {
public:
    int findMaxConsecutiveOnes(vector<int>& nums) {
        for (int i = 1; i < nums.size(); i++) {
            // 如果是 1，令值为前缀和；如果是 0，忽略
            if (nums[i]) {
                nums[i] = nums[i] + nums[i - 1];
            }
        }
        int end = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (end < nums[i]) {
                end = nums[i];
            }
        }
        return end;
    }
};

数组 $\text{2}$

 $\text{Q1.}$ 错误的集合

  显然，我们需要记录数字出现的次数，故新建一个数组 $\text{have}$，初始化为 $\text{0}$。每个角标 $\text{i}$ 对应位置表示数 $\text{i+1}$ 出现了几次，最后在 $\text{have}$ 找到次数为 $\text{2}$ 和 $\text{0}$ 的数，即为结果。该法的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    vector<int> findErrorNums(vector<int>& nums) {
        vector<int> have(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            have[nums[i] - 1]++;
        }
        vector<int> end(2, 0);
        for (int i = 0; i < nums.size(); i++) {
            if (have[i] == 2) {
                end[0] = i + 1;
            }
            if (!have[i]) {
                end[1] = i + 1;
            }
        }
        return end;
    }
};

 $\text{Q2.}$ 有多少小于当前数字的数字

  直接套用前一题的思路，新建一个数组 $\text{have}$，初始化为 $\text{0}$。每个角标 $\text{i}$ 对应位置表示数 $\text{i+1}$ 出现了几次，最后对每个数 $\text{n}$，输出 $\text{have[0]}$ 到 $\text{have[n-1]}$ 的和，即为结果。该法的时间复杂度为 $\text{O(}n^2\text{)}$、空间复杂度为 $\text{O(n)}$，代码如下：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> have(101, 0);
        for (int i = 0; i < nums.size(); i++) {
            have[nums[i]]++;
        }
        vector<int> end;
        for (int i = 0; i < nums.size(); i++) {
            int temp = 0;
            for (int j = 0; j < nums[i]; j++) {
                temp += have[j];
            }
            end.push_back(temp);
        }
        return end;
    }
};

  记：学习题解得到一个新的解法，可以将时间复杂度降为 $\text{O(n)}$，空间复杂度降为 $\text{O(1)}$，使用了前缀和的思想。

  对计数频率数组 $\text{have}$，在统计完频率后，自 $\text{have[1]}$ 开始，自加前一项的值，形成前缀和，即可表示不大于当前角标值的数字出现了几次。最后，只需使 $\text{nums[i]}$ 的值变成 $\text{have[nums[i] - 1]}$ 的值就行了，前提是 $\text{nums[i] > 1}$。复写代码如下：

class Solution {
public:
    vector<int> smallerNumbersThanCurrent(vector<int>& nums) {
        vector<int> have(101, 0);
        for (int i = 0; i < nums.size(); i++) {
            have[nums[i]]++;
        }
        for (int i = 1; i < have.size(); i++) {
            have[i] += have[i-1];
        }
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i]) {
                nums[i] = have[nums[i] - 1];
            }
        }
        return nums;
    }
};

 $\text{Q3.}$ 找到所有数组中消失的数字

  实际上是题“$\text{Q1.}$ 错误的集合”的变形，只需要在 $\text{have}$ 找到所有次数为 $\text{0}$ 的数并输出就行。该法的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        vector<int> have(nums.size(), 0);
        for (int i = 0; i < nums.size(); i++) {
            have[nums[i] - 1]++;
        }
        vector<int> end;
        for (int i = 0; i < nums.size(); i++) {
            if (!have[i]) {
                end.push_back(i + 1);
            }
        }
        return end;
    }
};

  对于进阶要求，观察到输入数组的长度也是 $\text{n}$，如果能修改对应角标位置的元素的值，使得能根据元素值判断出角标值对应的数字是否出现过，即可解决。根据上述思路，我们可以取值 $\text{nums[i]}$，如果 $\text{nums[abs(nums[i]) - 1]}$ （加 $\text{abs()}$ 是因为经过修改，$\text{nums[i]}$ 可能为负数，使得访问的角标值为负数而报错）处的元素值大于 $\text{0}$，对其乘以 $\text{-1}$，表示该角标值对应的数字已经出现，如果小于 $\text{0}$，则说明已经出现过，忽略。最后，只要找到元素值为整数的角标值，换算为对应数即为结果。该法在时间复杂度不变的情况下将空间复杂度降为 $\text{O(1)}$，代码如下：

class Solution {
public:
    vector<int> findDisappearedNumbers(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            if (nums[abs(nums[i]) - 1] > 0) {
                nums[abs(nums[i]) - 1] *= -1;
            }
        }
        vector<int> end;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] > 0) {
                end.push_back(i + 1);
            }
        }
        return end;
    }
};

栈

 $\text{Q1.}$ 用栈操作构建数组

  根据题意，可将题目拆分出两个问题：判断当前入栈的数是否在数组 $\text{target}$ 中，以及判断当前栈是否等价于该数组。

  显然，$\text{target}$ 严格递增，于是我们从 $\text{target[0]}$ 开始判断，假定当前应该入栈的数为 $\text{x}$，如果其等于 $\text{target[0]}$，则入栈后不再出栈，且 $\text{target}$ 遍历的角标值右移，变为 $\text{target[1]}$。以此类推，直到 $\text{target[target.size() - 1]}$ 也被遍历，输出结果。该法的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    vector<string> buildArray(vector<int>& target, int n) {
        vector<string> end;
        int targetId = 0;
        for (int i = 1; i <= n; i++) {
            if (targetId < target.size()) {
                if (i == target[targetId]) {
                    end.push_back("Push");
                    targetId++;
                } else {
                    end.push_back("Push");
                    end.push_back("Pop");
                }
            }
        }
        return end;
    }
};

 $\text{Q2.}$ 有多少小于当前数字的数字

  首先来学习一下逆波兰表达式（也即后缀表达式）是什么，其定义是这样的：

$$对一个表达式~\text{E}: \begin{cases} \ \text{E}~是一个变量或常量，则其后缀表达式即其本身 \\ \ \text{E}~是~\text{E}_1~\text{op}~\text{E}_2~形式的表达式，则其后缀表达式为~\text{E}_1~\text{E}_2~\text{op} \\ \ \text{E}~是~(\text{E}_1)~形式的表达式，则~\text{E}_1~的后缀式就是~\text{E}~的后缀式 \end{cases}$$

  基于上述算法定义，我们只需定义一个栈：每遇到数字，令其按序入栈；每遇到算术符 $\text{op}$，按序出栈两个数字 $\text{B}$、$\text{A}$，进行计算 $\text{A op B}$，将结果再入栈。最后唯一在栈中的数字即为所求结果。该法的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> nums;
        for (int i = 0; i < tokens.size(); i++) {
            // 长大于 1 或首位为数字即可判定为整数（特例：负数）
            if (tokens[i].size() > 1 || isdigit(tokens[i][0])) {
                // 使用 stoi() 函数可快速将 string 型变量转为 int 型，需声明 <string>
                nums.push(stoi(tokens[i]));
            } else {
                int b = nums.top();
                nums.pop();
                int a = nums.top();
                nums.pop();
                switch (tokens[i][0]) {
                case '+':
                    nums.push(a + b);
                    break;
                case '-':
                    nums.push(a - b);
                    break;
                case '*':
                    nums.push(a * b);
                    break;
                case '/':
                    nums.push(a / b);
                    break;
                }
                cout << nums.top() << " ";
            }
        }
        return nums.top();
    }
};

  记：学习题解，看到了一个执行时间为 $\text{0ms}$ 的方法，使用数组模拟栈，这里不再学习（用栈的题还是得栈）。

 $\text{Q3.}$ 函数的独占时间

  根据题意，可以观察到，如果从最先结束的函数开始计算时间会很简单。于是考虑新建一个栈，新建一个计时的 $\text{int}$ 数组 $\text{count}$，新建标记位 $\text{left}$、$\text{right}$、$\text{temptime}$，并初始化为 $\text{0}$。从原调用日志末尾依次读取：如果读到的是 $\text{end}$ 日志，入栈；如果读到的是 $\text{start}$ 日志，读取栈顶后出栈，在计时数组中执行：

$$\text{if end.timestamp < left: }\text{count[id] += end.timestamp - start.timestamp + 1} \\ \text{else: }\text{count[id] += (end.timestamp - start.timestamp + 1) - (right - left) + temptime}$$

  然后更新标志位：

$$如果~\text{temptime}~使用，归零 \\ \text{if end.timestamp < left: }\text{left = start.timestamp and temptime += left - (end.timestamp + 1)} \\ \text{else: }\text{left = start.timestamp and right = end.timestamp + 1}$$

  最后只需依次遍历日志后，将计时数组返回即可。

  注：上述方法复杂且无法实现，直观问题是由于在父区间中可能有子区间，子区间中可能有孙区间。这样的重叠区间无法用标签量维护。实际上，直接按日志的记录顺序来入栈是最为简单的。

  具体地，新建一个栈 $\text{stack ids}$，用于存储当前正在执行的函数编号；再维护一个时间标记 $\text{prevTime}$，表示上一时刻的时间点。随后依次遍历日志：

• 如果当前日志是 $\text{start}$ 类型：
  • 如果栈不为空，说明当前栈顶的函数被中断了。计算它从 $\text{prevTime}$ 到当前时间点之前的执行时间，并累加到结果中：$\text{res[ids.top()] += timestamp - prevTime}$。
  • 将当前函数编号 $\text{id}$ 入栈。
  • 更新 $\text{prevTime}$ 为当前时间点 $\text{timestamp}$。
• 如果当前日志是 $\text{end}$ 类型：
  • 当前栈顶函数执行结束。计算它从 $\text{prevTime}$ 到当前时间点（含）的执行时间，并累加到结果中：$\text{res[ids.top()] += timestamp - prevTime + 1}$。
  • 将栈顶函数编号出栈。
  • 更新 $\text{prevTime}$ 为下一时刻 $\text{timestamp + 1}$。

  通过这种方式，我们只需要一次遍历日志，就能准确计算出每个函数的独占时间，故该法的时间、空间复杂度均为 $\text{O(n)}$，代码如下：

class Solution {
public:
    // 封装一个 split 辅助函数
    vector<string> split(const string& str, char special) {
        vector<string> end;
        string temp = "";
        for (int i = 0; i < str.size(); i++) {
            if (str[i] != special) {
                temp += str[i];
            } else {
                end.push_back(temp);
                temp = "";
            }
            if (i == str.size() - 1) {
                end.push_back(temp);
            }
        }
        return end;
    }

    vector<int> exclusiveTime(int n, vector<string>& logs) {
        vector<int> count(n, 0);
        stack<int> st;
        int prevTime = 0;
        for (const string& log : logs) {
            vector<string> temp = split(log, ':');
            int id = stoi(temp[0]);
            string type = temp[1];
            int timestamp = stoi(temp[2]);

            if (type == "start") {
                if (!st.empty()) {
                    count[st.top()] += timestamp - prevTime;
                }
                st.push(id);
                prevTime = timestamp;
            } else {
                count[st.top()] += timestamp - prevTime + 1;
                st.pop();
                prevTime = timestamp + 1;
            }
        }
        return count;
    }
};