hot100之技巧组题目

贾雨石

只出现一次的数字(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 >= nums[i+1])  i--;
        
        if (i < 0) {
            reverse(nums, 0);
            return;
        }
        
        int j = nums.length -1;
        while (j > i && nums[j] <= nums) j--;
        swap(i, j, nums);

        reverse(nums, i+1);
    }
}

• 分析

1. 从右到左找到最大逆序数组→逆序数组翻转可得到最小数组(无逆序数组, 后续直接交换即为最小)
2. 为得到<最小更大排列> , 我们需要从逆序数组中找到<最小更大>值跟nums交换
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完成🥰🥰

来源：https://www.cnblogs.com/many-bucket/p/18952760