LeetCode刷题记录（技巧篇）

LeetCode刷题记录（技巧篇），个人向。

[136] Single Number

难度：Easy
语言：C++

题目描述。
简单的位运算，全部异或一遍即可。

class Solution {
  public:
    int singleNumber(vector<int> &nums) {
        int result = 0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
};

[169] Majority Element

难度：Easy
语言：C++

题目描述。
题目难点在于要求了 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度。
这里使用了 Boyer-Moore 投票算法，具体可参考这篇solution。
简单来说，这里维护了candidate和count两个变量。在当前元素和candidate相等时，count+=1，否则count-=1。此外，若count == 0，则会先更新candidate为当前元素。

class Solution {
  public:
    int majorityElement(vector<int> &nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            if (candidate == num) {
                count += 1;
            } else {
                count -= 1;
            }
        }
        return candidate;
    }
};

[75] Sort Colors

难度：Medium
语言：C++

题目描述。
题目要求one-pass和constant extra space。constant extra space很简单，关键在于这个one-pass。
已知用一个指针可以很容易想到先把0都换到前面，再把1都换到前面，但这样需要two-pass。既然一个指针是two-pass，那我们就使用两个指针，分别负责填两个颜色。
我们可以使用一个指针用来填红色（代表数字0），一个用来填蓝色（代表数字2）。第一个指针从开头开始，另一个指针从尾部开始。遇到0，我们就把数字换到开头指针（resPos）；遇到2，我们就把数字换到尾部指针（bluePos）。
但遇到2时，不能只是换一遍这么简单，因为可能换回来的还是2。因此我们应该连续不断地把2换到后面（同时也在不断bludPos -= 1），直到换回来的不是2。这时候换回来的有可能是0，我们还需要把0换到redPos，然后才开始考虑下一个元素。
为什么遇到0时只需要换一次，而不需要像遇到2一样一直换？这是因为遇到0且换回0只会发生在当前位置元素自己和自己交换的情况，不会忽略其他未处理的0。遇到0也不可能换回2，因为遇到过的2已经被换到最后了。这里出现差异的根本原因是，我们在遍历数组时是从开头即redPos这边遍历过来的，遇到0时从redPos换回来的元素都是从遍历过的位置换回来的，而遇到2时从bluePos换回的元素是来自还没遍历过的位置的。
另一种双指针的方法是一个指针处理0，一个指针处理1，可参考这篇solution。

class Solution {
  public:
    void sortColors(vector<int> &nums) {
        int redPos = 0;
        int bluePos = nums.size() - 1;
        int tmp = 0;
        for (int i = 0; i <= bluePos; ++i) {
            while (i <= bluePos && nums[i] == 2) {
                tmp = nums[bluePos];
                nums[bluePos] = 2;
                nums[i] = tmp;
                bluePos -= 1;
            }
            if (nums[i] == 0) {
                tmp = nums[redPos];
                nums[redPos] = 0;
                nums[i] = tmp;
                redPos += 1;
            }
        }
    }
};

[31] Next Permutation

难度：Medium
语言：C++

题目描述。

从后向前遍历，寻找相邻的递增序列 $[i, i+1]$ 使 $nums[i]<nums[i+1]$ ，此时 $[i+1, end]$ 都是递减序列。
再次从后向前遍历，直到遇到第一个 $j$ 使 $nums[i]<nums[j]$ 。此时 $nums[j]$ 就是比 $nums[i]$ 大一点但是在 $[i+1, end]$ 中尽可能小的数。
交换 $nums[i]$ 和 $nums[j]$ 。
此时 $[i+1, end]$ $[i + 1, e n d]$ 仍为递减序列。我们倒序该部分使其变成递增序列。
- 注意如果第一步中我们没有找到这样的 $[i, i+1]$ ，说明整个数组都是递减序列，此时我们直接倒序整个数组即可。

class Solution {
  public:
    void nextPermutation(vector<int> &nums) {
        int n = nums.size();
        int i = n - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            --i;
        }
        if (i >= 0) {
            for (int j = n - 1; j > i; --j) {
                if (nums[j] > nums[i]) {
                    int tmp = nums[i];
                    nums[i] = nums[j];
                    nums[j] = tmp;
                    break;
                }
            }
        }
        for (int left = i + 1, right = n - 1; left < right; ++left, --right) {
            int tmp = nums[left];
            nums[left] = nums[right];
            nums[right] = tmp;
        }
    }
};

[287] Find the Duplicate Number

难度：Medium
语言：C++

题目描述。
把 $i$ 到 $nums[i]$ 看作是有一条边，有重复数字就变成了图有环，重复数字就是环的入口，寻找重复数字就是寻找这个环的入口。整道题就变成了[142] Linked List Cycle II。

class Solution {
  public:
    int findDuplicate(vector<int> &nums) {
        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[fast];
            fast = nums[fast];
        } while (slow != fast);
        slow = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};

总结

这部分什么类型的题都有。[136] Single Number考察的是位运算；[169] Majority Element用了Boyer-Moore 投票算法；[75] Sort Colors使用了双指针；[31] Next Permutation算是一道找规律的题目，最后是用了两次从后向前的遍历再加上倒序；[287] Find the Duplicate Number则是被转化成了环形链表的题目。

AllenY's blog