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