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