陈展的博客

记录点滴

0%

TryHackMe-NmapLiveHostDiscovery

发表于 更新于 分类于

知识点记录

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

数组 $\text{1}$

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

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

1
2
3
4
5
6
7
8
9
10
11
12
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)}$，代码如下：

1
2
3
4
5
6
7
8
9
10
11
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}$ 取回。

  复写代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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)}$，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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}$ 段的长。

1
2
3
4
角标 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]

  复写代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
    }
};