思想

今天看最后一部分，杂项。这一板块的内容没有统一的处理方式，更像是脑筋急转弯。类似于数学卷子上的开放式题目或者超纲题目。看一看，涨涨见识吧。

题目

31. Next Permutation

下一个排列数。给我们一个数组，让我们找出按照字典序（从小到大），下一个排列数是谁。

比如，[1, 2, 3] 的下一个排列数是 [1, 3, 2]，就像比 123 大的下一个数是 132 一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();

        // find desc array edge
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        // find the minimum number in the desc array larger than edge
        if (i >= 0) {
            int j = n - 1;
            while (nums[i] >= nums[j]) {
                j--;
            }

            swap(nums[i], nums[j]);
        }

        reverse(nums.begin() + i + 1, nums.end());
    }
};

这题的思路在于模拟排列数的构造方法。算法是这样的：

  1. 对于一个数组，找出从末尾为起点，降序数组的范围；
  2. 记录第一个破坏降序的元素下标；
  3. 在降序数组中，找到最小的大于该元素的元素，交换它们两个；
  4. 翻转降序数组。

这个想法其实很直观，我们举个例子。

对于 [1, 3, 2] 这个输入，降序数组的范围是 [3, 2]。那么第一个破坏降序数组的元素就是 1。

你说，为什么要找降序数组？这是因为对于破坏降序数组的第一个元素（结合本例，后续用 1 代替）来说，意味着它待在所处位置时，能获得的最大值就是当前值。如果要前进，必须要把它和降序数组中的某个元素交换。

那么，和谁交换？和降序数组中比 1 大的最小元素交换，也就是 2。因为这样能够保证交换后以及将降序数组逆序后的数在字典序上为当前值的下一个。

比如 [1, 3, 2]，1 和 2 交换得到 [2, 3, 1]。先暂停，231 确实不是 132 的下一个，但是，2 作为开头是必要条件！换言之，必须 1 和 2 交换，如果和 3 交换，肯定得不到正确结果。

这是从边界元素的方面讨论的。另一方面，对倒序数组来说，1 和 2 交换确保了倒序数组是所有可取排列中的最大值，这样，逆序后才能确保是新的起点。

最后的逆序如何解释？倒序数组是最大值，那逆序之后就是新的起点咯。

Follow Up: 如果要生成全部排列数，该怎么办？用回溯法。

说真的，我有些忘记回溯法了，刷完了 100 道题，还是需要再回顾，再忘记，再回顾…

41. First Missing Positive

这题给了我们一个数组，让我们找出缺失的第一个正数。要求 $O(n)$ 时间和 $O(1)$ 空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();

        for (int i = 0; i < n; i++) {
            // nums[i] in range, and in the correct location
            while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1]) {
                swap(nums[i], nums[nums[i] - 1]);
            }
        }

        for (int i = 0; i < n; i++) {
            if (nums[i] != i + 1) {
                return i + 1;
            }
        }
        
        return n + 1;
    }
};

这题的核心在于把下标和值对应起来，最理想的情况是每个数站在自己的下标。比如 1 在 [0]、2 在 [1]。这样，在排列完毕后，如果某个位置的值和预期不一样，说明缺失了它。

为什么让 1 在 [0] 而不是 [1]？因为 0 并不是我们期待的数字，所以「让 0 处在 [0]」我们并不关心。就算它成立，也不能说明什么。

而且，这样还会导致的问题是，如果 n 表示数组大小，那 n 无处可去，去 [0] 吗？那还不如让 1 在 [0] 呢，更直观。

关于对应关系的判断条件，需要展开讲讲：

1
while (nums[i] > 0 && nums[i] <= n && nums[i] != nums[nums[i] - 1])

这句话的意思有 3 个含义：

  • 如果你是 0 或者负数，就在原地待着吧，等着别人替换你。你是标记，代表了缺失的正数；
  • 如果你比 n 大，也原地待着吧。如果 n 个空位用来存放 1 - n，结果出现了比 n 大的数，肯定在 1 - n 之间有缺失。你也代表缺失的正数；
  • 就算你是合法范围内，如果你是重复出现的合法值，也在原地待着吧。比如，nums[1] = 2 成立，结果现在 nums[5] 也等于 2。那你也待着吧，和第二点的道理一样，肯定 1 - n 有缺失。

重点展开第三点，看上去 nums[i] != nums[nums[i] - 1] 和 i != nums[i] - 1 的道理差不多？后者要求下标和当前位置严格相同，前者要求更弱，如果下标不同但是取值相同，是可以接受的。

条件需要放松，例如对于 [1, 1]，如果用严格的条件，会死循环。

53. Maximum Subarray

这题要求我们求出一个数组的子数组（必须连续）之和的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int prev = 0, curr = 0;
        int ans = INT_MIN;

        for (int num : nums) {
            curr = prev < 0 ? num : num + prev;
            prev = curr;

            ans = max(ans, curr);
        }

        return ans;
    }
};

一道非常经典的动态规划。不必多说。Follow Up 问是否能用分治法。我看了看那段代码，说实话，有些繁琐。暂时不想理会它。

56. Merge Intervals

合并重叠的时间间隔，返回合并后的结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        vector<vector<int>> ans;
        
        vector<int> curr = intervals[0];

        for (int i = 0; i < intervals.size(); i++) {
            if (intervals[i][0] <= curr[1]) {
                curr[1] = max(curr[1], intervals[i][1]);
            } else {
                ans.push_back(curr);
                curr = intervals[i];
            }
        }

        ans.push_back(curr);

        return ans;
    }
};

感觉做过类似的题目。之前在算法课的时候，有一个会议室时间安排问题，问怎样能安排尽可能多的会议次序，给了每个会议的开始和结束时间。思路是先排序再贪心。这里的解法，我感觉有些相像的地方，但是不全一样。

75. Sort Colors

这题要求给颜色排序，只有 3 种颜色，0、1、2，而且要求要原地交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int n = nums.size();
        int zero = 0, two = n - 1;
        int i = 0;

        while (i <= two) {
            if (nums[i] == 1) i++;
            else if (nums[i] == 0) {
                swap(nums[i], nums[zero]);
                zero++;
                i++;
            } else {
                swap(nums[i], nums[two]);
                two--;
            }
        }

        return;
    }
};

思路比较简单，把 0 尽量往数组的左侧放，2 尽量往数组的右侧放。需要注意下标的修改逻辑。什么时候要 i++？首先要明确 i 的含义，它代表正在处理的元素的下标，如果它自增，说明当前元素处理完毕，可以放心的跳过。

首先，如果遇到 2，不能放心的跳过，因为不清楚交换后的元素到底是几，可能是 0、1、2。所以必须继续处理。

如果遇到 1，放心跳过吧，1 看作占位符。

如果遇到 0，为什么也可以放心跳过呢？因为 0 是和数组前面的元素交换，它只可能是 1，或者是当前下标（元素 0）。所以也要前进。

终止条件是 <= two 因为 two 的含义是「下一个放置 2 的位置」，所以该位置到底是什么，其实不好说，还需要处理。

136. Single Number

给了一个数组，所有的元素都成双成对的出现，只有一个元素是单身狗，要求找出这个单身狗。必须 $O(n)$ 时间，$O(1)$ 空间。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;

        for (int num : nums) {
            ans ^= num;
        }

        return ans;
    }
};

异或逻辑。

169. Majority Element

要求找出一个数组中的多数元素，它出现至少 $\lfloor n / 2 \rfloor$ 次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = nums[0];
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            
            if (num == candidate)  {
                count++;
            } else {
                count--;
            }    
        }

        return candidate;
    }
};

投票问题，两两相消。设定一个候选人和票数，如果有人没投票给它，则票数 - 1。票数为 0 了则换上新候选人。最终能够胜利的候选人肯定获得了一半以上的票数。

189. Rotate Array

循环右移数组。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        k = k % nums.size();

        reverse(nums.begin(), nums.end());
        reverse(nums.begin(), nums.begin() + k);
        reverse(nums.begin() + k, nums.end());

        return;
    }
};

很巧妙。把循环转变为 3 次逆序。我反正想不到。而每次右移 1 次，重复 k 次的做法超时了。

如果采用从 [0] 和 [(0 + k) % n] 对换，[(0 + k) % n] 和 [(0 + k + k) % n] 对换这样接力的思路也不行，因为不能确保这能循环到每个元素。例如 n = 4, k = 2。

238. Product of Array Except Self

给一个输入数组，要求得到结果数组。结果数组中的每个元素值是输入数组中其他位置元素的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();

        vector<int> ans(n, 1);
        int prefix = 1;

        for (int i = 0; i < n; i++) {
            ans[i] *= prefix;
            prefix *= nums[i];
        }

        int suffix = 1;
        for (int i = n - 1;i >= 0; i--) {
            ans[i] *= suffix;
            suffix *= nums[i];
        }

        return ans;
    }
};

通过为每个位置分别计算前缀和后缀，得到结果。

还有另外一种方法，注意到如果输入数组中有两个或以上的 0，则结果是全 0。否则，对于 0 的位置是数组中其他元素的乘积，其他位置也是全 0。

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
27
28
29
30
31
32
class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int zeroPos = -1;
        int n = nums.size();
        int multi = 1;

        vector<int> ans(n, 0);

        for (int i = 0; i < n; i++) {
            if (nums[i] == 0) {
                if (zeroPos != -1) {
                    return ans;
                } else {
                    zeroPos = i;
                }
            } else {
                multi *= nums[i];
            }
        }

        if (zeroPos == -1) {
            for (int i = 0; i < n; i++) {
                ans[i] = multi / nums[i];
            }
        } else {
            ans[zeroPos] = multi;
        }

        return ans;
    }
};

没想到这个方法居然比上一个方法慢，嗯，可能用例中含有 0 的情况比较少吧。

287. Find the Duplicate Number

找出重复的数字，有 $n + 1$ 个整数，且范围在 $[1, n]$。

不能修改 nums，必须 $O(1)$ 空间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0], fast = nums[0];

        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        slow = nums[0];

        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }

        return slow;
    }
};

很巧妙，看作是链表。这样就完全等价于链表判环那道题了。

需要注意，因为一定有环，所以条件没有写成 while (fast && fast->next)，而是用了 do while 的风格。道理一样。