热榜百题中技巧类题目的探寻

热榜百题中技巧类题目的探究

仅出现一次的数字(136)

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

• 解析：利用异或运算的特性来求解

多数元素(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--;
                }
            }
        }

        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++;
            }
        }
    }

    private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

• 解析：运用双指针策略来解决

下一个排列(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);
    }

    private void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(left, right, nums);
            left++;
            right--;
        }
    }

    private void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

• 解析：
• 从右往左找出最大的逆序子数组→将逆序子数组翻转可得到最小的子数组（若不存在逆序子数组，后续直接交换就能得到最小情况）
• 为得到<最小的更大排列>，需从逆序子数组中找到<最小的更大>的值与nums[i]交换
• 翻转逆序子数组

寻找重复数(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;
    }
}

• 解析：依据<唯一性>，巧妙地将问题转化为环形链表的情形，当索引出现重复时便形成了环