Hot100之技巧

136只出现一次的数字

题目

思路解析

异或操作的性质：

相同的位异或的结果是0，不同的位异或的结果是1

• x ^ x = 0：任何数字和自身异或，结果为 0。
• x ^ 0 = x：任何数字和 0 异或，结果为它本身

代码

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

---

169多数元素

题目

思路解析

中间那个就是

代码

class Solution {public int majorityElement(int[] nums) {Arrays.sort(nums);return nums[nums.length / 2];}
}

---

75颜色分类

题目

思路解析

左边0中间1

使用两次双指针交换

第一次将所有是0的放到左边

第一轮交换结束后，left为最后一个0的右边的位置

开始第二轮交换

第二轮交换是将所有的1放到中间

也就是我使用了两次的双指针交换

---

左边0右边2

我们左指针left从0开始，有指针right从n-1开始

我们遇到0就和nums【left】交换，然后left++

遇到2就和nums【right】交换，然后right--

---

最简洁的代码

我们从左往右先遍历

我们有个temp记录一开始的nums【i】

nums【i】一开始我们先统一变为2

然后当我们temp<2的时候，我们不管这是0还是1，我们变成1,然后n1++

然后我们再来一个判断temp<1，此时这个是0，我们变成0然后n0++

这样子依次轮着覆盖，然后n1最后会到达1的起始位置，n0最后最到达0的最后位置

---

代码

左边0中间1

class Solution {public void sortColors(int[] nums) {
int n=nums.length;
int left=0;
int right=n-1;while(left<right)
{if(nums[left]==0)left++;else if(nums[left]!=0&&nums[right]==0){int temp=nums[left];nums[left]=nums[right];nums[right]=temp;}else{right--;}
}right=n-1;while(left<right)
{if(nums[left]==1)left++;else if(nums[left]!=1&&nums[right]==1){int temp =nums[left];nums[left]=nums[right];nums[right]=temp;}else{right--;}
}}
}

---

左边0右边2

class Solution {public void sortColors(int[] nums) {int left = 0, right = nums.length - 1, current = 0;while (current <= right) {if (nums[current] == 0) {// 交换当前值和 left 的值，把 0 放到左边int temp = nums[current];nums[current] = nums[left];nums[left] = temp;left++;current++;} else if (nums[current] == 2) {// 交换当前值和 right 的值，把 2 放到右边int temp = nums[current];nums[current] = nums[right];nums[right] = temp;right--;} else {// 如果是 1，不需要交换，只移动指针current++;}}}
}

---

最简洁的代码

class Solution {public void sortColors(int[] nums) {int n0 = 0, n1 = 0;for(int i = 0; i < nums.length; i++){int num = nums[i];nums[i] = 2;if(num < 2){nums[n1++] = 1;}if(num < 1){nums[n0++] = 0;}}}
}

---

31下一个排列

题目

---

思路解析

下一个排列指的是，下一个比这个数大的数是什么

【1，3，5，4，2】的下一个数是什么？

先给出答案，【1，4，2，3，5】

查找答案的流程：

1. 从右往左找，找到第一个小于右边数的数X，即nums【i】<nums【i+1】，我们找到的第一个数X就是3
2. 从最右边向左找第一个大于数X，即3的数，找到了这个数是4
3. 将4和3进行交换，得到【1，4，5，3，2】，将x位置的右边，也就是【5，3，2】进行反转

问题答疑

1. 第一步找到X后，为什么右边的数是单调递减的

反证法。假设 x 右边的数不是单调递减的，也就是说，在 x 的右边，存在 nums[i]<nums[i+1] 的情况，那么我们应把 nums[i] 当作 x，这与事实矛盾

1. 为什么第二步交换后，右边的序列仍然是单调递减的？

设交换前 nums=[…,x,c,b,a,…] 且 a<x<b<c，那么 x 右边最小的大于 x 的数是 b

交换 x 和 b 后，右边数字为 c,x,a,…，满足 c>x>a>⋯，仍然是单调递减的

1. 如果 nums 是第一个排列，我们是怎么算的？

例如 nums=[1,2,3]。第一步找到 2，第二步交换 2 和 3，第三步反转 2（只有一个数，反转后还是 2），最终得到 [1,3,2]。读者可以动手算算 [1,3,2] 的后续排列，以加深印象

有两个函数，一个是swap（）交换节点，一个reverse（）反转节点

---

代码

class Solution {public void nextPermutation(int[] nums) {int n = nums.length;int left = n - 2;while (left >= 0 && nums[left] >= nums[left + 1]) {left--;}if (left >= 0) {int right = n - 1;while (nums[left] >= nums[right]) {right--;}swap(nums, left, right);}reverse(nums, left + 1, n - 1);}private void swap(int nums[], int left, int right) {int temp = nums[left];nums[left] = nums[right];nums[right] = temp;}private void reverse(int nums[], int left, int right) {while (left < right) {swap(nums, left++, right--);}}
}

---

287寻找重复数

题目

---

思路解析

将数和下标建立成映射关系，如果有环就是一对多的关系

所以可以根据环形链表2的思路来做题

---

代码

class Solution {public int findDuplicate(int[] nums) {int slow = nums[0];int fast = nums[nums[0]];// 第一阶段：找到相遇点while (slow != fast) {slow = nums[slow];fast = nums[nums[fast]];}// 第二阶段：找到环的入口int head = 0;while (slow != head) {slow = nums[slow];head = nums[head];}return slow;}
}