LeetCode 热题 100-技巧
位运算
两个相同的数字异或结果是0，因此将数组中每个数字进行异或运算，最后得到的数字就是只出现一次的那个数字。
1
2
3
4
5
6
7
8
9
| class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int i = 0; i < nums.length; i++) {
ans = ans ^ nums[i];
}
return ans;
}
}
JAVA
|
Boyer-Moore 投票算法
- 若记 众数 的票数为 +1 ，非众数 的票数为 −1 ，则一定有所有数字的 票数和 >0 。
- 若数组的前 a 个数字的 票数和 =0 ，则 数组剩余 (n−a) 个数字的 票数和一定仍 >0 ，即后 (n−a) 个数字的 众数仍为 x 。
- 初始化： 票数统计 votes = 0 ， 众数 x。
- 循环： 遍历数组 nums 中的每个数字 num 。
- 当 票数 votes 等于 0 ，则假设当前数字 num 是众数。
- 当 num = x 时，票数 votes 自增 1 ；当 num != x 时，票数 votes 自减 1 。
- 返回值： 返回 x 即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int majorityElement(int[] nums) {
int votes = 0, cadidates = 0;
for (int i = 0; i < nums.length; i++) {
if (votes == 0) {
cadidates = nums[i];
}
if (nums[i] == cadidates) {
votes++;
} else {
votes--;
}
}
return cadidates;
}
}
JAVA
|
计数
直观的想法是统计0、1、2的个数，然后再遍历一遍填入。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public void sortColors(int[] nums) {
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < nums.length; i++){
if (nums[i] == 0) {
cnt0++;
} else if (nums[i] == 1) {
cnt1++;
}
}
for (int i = 0; i < cnt0; i++) {
nums[i] = 0;
}
for (int i = cnt0; i < cnt1 + cnt0; i++) {
nums[i] = 1;
}
for (int i = cnt0 + cnt1; i < nums.length; i++) {
nums[i] = 2;
}
}
}
JAVA
|
三次覆写
遍历数组： i：代表目前为止(0 + 1 + 2) 的数量：
- n1: 代表目前为止 (0 + 1)的数量
- n0: 代表目前为止 (0)的数量
一次判断当前数字属于哪一类，然后修改对应的nums[]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public void sortColors(int[] nums) {
int cnt0 = 0, cnt1 = 0;
for (int i = 0; i < nums.length; i++) {
int num = nums[i];
nums[i] = 2;
if (num < 2) {
nums[cnt1++] = 1;
}
if (num < 1) {
nums[cnt0++] = 0;
}
}
}
}
JAVA
|
双指针
使用三个指针（p0，p1 和 i）来实现原地排序，核心思想是 一次遍历 数组，利用指针来分别追踪0、1、2应该在的位置。
遍历数组：
- 当 nums[i] == 1 时，说明当前元素应该是 1。我们将其与 p1 指向的元素交换，并且将 p1 增加1。
- 当 nums[i] == 0 时，说明当前元素应该是 0。我们首先将其与 p0 指向的元素交换，然后，如果 p0 < p1，我们需要再交换一次，将 nums[i] 和 nums[p1] 交换，避免在处理 0 的时候，把 1 错放到 0 的位置。然后，我们将 p0 和 p1 都增加1。
- 当 nums[i] == 2 时，我们什么也不做，只需要继续遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public void sortColors(int[] nums) {
int p0 = 0, p1 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
swap(nums, i, p1);
p1++;
} else if (nums[i] == 0) {
swap(nums, i, p0);
if (p0 < p1) {
swap(nums, i, p1);
}
p0++;
p1++;
}
}
}
private void swap(int[] nums, int a , int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
}
JAVA
|
分析
- 从后向前 查找第一个 相邻升序 的元素对 (i,j)，满足 A[i] < A[j] (i < j)。此时 [j,end) 必然是降序。
- 在 [j,end) 从后向前 查找第一个满足 A[i] < A[k] 的 k。
- 将 A[i] 与 A[k] 交换
- 可以断定这时 [j,end) 必然是降序，逆置 [j,end)，使其升序
- 如果在步骤 1 找不到符合的相邻元素对，说明当前 [begin,end) 为一个降序顺序，则直接跳到步骤 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public void nextPermutation(int[] nums) {
int n = nums.length;
int i = n - 2, j = n - 1;
while (i >= 0 && nums[i] >= nums[j]) {
i--;
j--;
}
if (i >= 0) {
int k = n - 1;
while (k >= j && nums[i] >= nums[k]) {
k--;
}
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;
}
int left = j, right = n - 1;
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
}
JAVA
|
二分查找
定义 cnt[i] 表示 nums 数组中小于等于 i 的数有多少个，假设我们重复的数是 target，那么 [1,target−1]里的所有数满足 cnt[i]≤i，[target,n] 里的所有数满足 cnt[i]>i，具有单调性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
int left = 1, right = n - 1, ans = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
left = mid + 1;
} else {
right = mid - 1;
ans = mid;
}
}
return ans;
}
}
JAVA
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
二进制
考虑第 i 位，我们记 nums 数组中二进制展开后第 i 位为 1 的数有 x 个，数字 [1,n] 这 n 个数二进制展开后第 i 位为 1 的数有 y 个，那么重复的数第 i 位为 1 当且仅当 x>y。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
| class Solution {
public int findDuplicate(int[] nums) {
int n = nums.length;
int bitNum = 31;
while (((n - 1) >> bitNum) == 0) {
bitNum--;
}
int ans = 0;
for (int k = 0; k <= bitNum; k++) {
int x = 0, y = 0;
for (int i = 0; i < n; i++) {
if ((nums[i] & (1 << k)) != 0) {
x++;
}
if (i >= 1 && ((i & (1 << k)) != 0)) {
y++;
}
}
if (x > y) {
ans |= (1 << k);
}
}
return ans;
}
}
JAVA
|
- 时间复杂度：O(nlogn)
- 空间复杂度：O(1)
快慢指针
对 nums 数组建图，每个位置 i 连一条 i→nums[i] 的边。由于存在的重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的 target 就是这个环的入口，那么整个问题就等价于环形链表问题。
先设置慢指针 slow 和快指针 fast ，慢指针每次走一步，快指针每次走两步，根据「Floyd 判圈算法」两个指针在有环的情况下一定会相遇，此时我们再将 slow 放置起点 0，两个指针每次同时移动一步，相遇的点就是答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int findDuplicate(int[] nums) {
int slow = 0, fast = 0;
do{
slow = nums[slow];
fast = nums[nums[fast]];
} while (slow != fast);
slow = 0;
while (slow != fast) {
slow = nums[slow];
fast = nums[fast];
}
return slow;
}
}
JAVA
|
总结
技巧类的题目很难想，只能多做，多积累。至此hot100的题目都做完了，其实大部分题目之前都做过，甚至做过好几遍，但是再做时可能还是理不清思路，要多复习。明天开始做hot150，但是这次不再追求每天做多少题目了，主要是对hot100里没做过的题目做一下，然后复习已经做过的，保证做过的题目一定弄透彻。