Leetcode 刷题记录 21 —— 技巧

Leetcode 刷题记录 21 —— 技巧

本系列为笔者的 Leetcode 刷题记录，顺序为 Hot 100 题官方顺序，根据标签命名，记录笔者总结的做题思路，附部分代码解释和疑问解答，01~07为C++语言，08及以后为Java语言，一共为 01~21，本系列全部结束。

01 只出现一次的数字

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

位运算

02 多数元素

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        int n = nums.length;
        int ans = 0;

        for(int num : nums){
            if(!map.containsKey(num)){
                map.put(num, 1);
            }else{
                map.put(num, map.get(num) + 1);
            }
        }

        for(int num : nums){
            if(map.get(num) > (n/2)){
                ans = num;
                break;
            }
        }
        return ans;
    }
}

03 颜色分类

class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        int ptr = 0;

        //第一次遍历，将0交换到头部
        for(int i=0; i<n; i++){
            if(nums[i] == 0){
                int temp = nums[ptr];
                nums[ptr] = nums[i];
                nums[i] = temp; 
                ptr++;
            }
        }

        //第二次遍历，将1交换到0之后
        for(int i=ptr; i<n; i++){
            if(nums[i] == 1){
                int temp = nums[ptr];
                nums[ptr] = nums[i];
                nums[i] = temp; 
                ptr++;
            }
        }
    }
}

04 下一个排列

class Solution {
    public void nextPermutation(int[] nums) {
        int len = nums.length;

        //特殊情况判断
        if(nums == null || nums.length < 2){
            return;
        }

        int i = len -2, j = len - 1, k = len - 1;
        while(i >= 0 && nums[i] >= nums[j]){
            i--;
            j--;
        }

        if(i >= 0){
            while(nums[i] >= nums[k]){
                k--;
            }

            int temp = nums[i];
            nums[i] = nums[k];
            nums[k] = temp;
        }

        int left = j, right = len - 1;
        while(left < right){
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }
    }
}