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

• 分析

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