trick

一些小巧思

佩服古人的智慧!

136.只出现一次的数字

巧妙利用异或的性质

解：

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

169.多数元素

Boyer–Moore 投票算法

解：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int count = 0;
        int candidate = 0;
        for(int i = 0; i < nums.size(); i++){
            if(count == 0){
                candidate = nums[i];
            }
            if(nums[i] == candidate){
                count++;
            }else{
                count--;
            }
        }
        return candidate;
    }
};

75.颜色分类

用三个指针维护区间，左边全是0，右边全是2，中间扫描

扫到0放左边，扫到2放右边，i只在当前位置已确定安全时才前进

解:

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int l = 0; // 0区右边界
        int r = nums.size() - 1; // 2区左边界
        int i = 0; // 当前指针

        while(i <= r) {
            if(nums[i] == 0) {
                swap(nums[i], nums[l]);
                l++;
                i++;
            }else if(nums[i] == 1) {
                i++;
            }else {
                // nums[i] == 2
                swap(nums[i], nums[r]);
                r--;
            }
        }
    }
};