只出現一次的數字(136)

class Solution {
    public int singleNumber(int[] nums) {
        int res = 0;
        for (int num : nums){
            res ^= num;
        }
        return res;
    }
}

• 分析

異或

多數元素（169）

class Solution {
    public int majorityElement(int[] nums) {
        int res = nums[0];
        int count = 0;

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

        return res;
    }
}

• 分析

將元素分為<此元素>和<其他元素>進行統計

顏色分類（075）

class Solution {
    public void sortColors(int[] nums) {
        int cursor_0 = 0;
        int cursor_2 = nums.length -1;
        int idx = 0;

        while (idx <= cursor_2){
            if (nums[idx] == 0) swap(idx++, cursor_0++, nums);
            else if (nums[idx]==2) swap(idx, cursor_2--, nums);
            else idx++;
        }
    }
}

• 分析

雙指針

下一個排列（031）

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n-2;
        while (i >= 0 && nums[i] >= nums[i+1])  i--;
        
        if (i < 0) {
            reverse(nums, 0);
            return;
        }
        
        int j = nums.length -1;
        while (j > i && nums[j] <= nums[i]) j--;
        swap(i, j, nums);

        reverse(nums, i+1);
    }
}

• 分析

1. 從右到左找到最大逆序數組→逆序數組翻轉可得到最小數組(無逆序數組, 后續直接交換即為最小)
2. 為得到<最小更大排列> , 我們需要從逆序數組中找到<最小更大>值跟nums[i]交換
3. 翻轉逆序數組

尋找重復數（287）

class Solution {
    public int findDuplicate(int[] nums) {
        int fast = 0;
        int slow = 0;
        slow = nums[slow];
        fast = nums[nums[fast]];

        while (fast != slow){
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        int prev1 = 0;
        int prev2 = slow;

        while (prev1 != prev2){
            prev1 = nums[prev1];
            prev2 = nums[prev2];
        }

        return prev1;
    }
}

• 分析

根據<唯一性>，很巧妙的轉化成了環形鏈表

索引重復則有環

在學校的最后一天，二刷hot100完成????