Skip to content

Commit 148060d

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent e949a27 commit 148060d

18 files changed

+228
-53
lines changed

‎README.md

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -338,8 +338,8 @@ int countNodes(TreeNode* root) {
338338
|[0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md) | 数组 |中等|**双指针**|
339339
|[0020.有效的括号](https://github.com/youngyangyang04/leetcode/blob/master/problems/0020.有效的括号.md) | 栈 |简单|**栈**|
340340
|[0021.合并两个有序链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0021.合并两个有序链表.md) |链表 |简单|**模拟** |
341-
|[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md) |数组 |简单|**暴力** **快慢指针** |
342-
|[0027.移除元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0027.移除元素.md) |数组 |简单| **暴力** **快慢指针/双指针**|
341+
|[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md) |数组 |简单|**暴力** **快慢指针/快慢指针** |
342+
|[0027.移除元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0027.移除元素.md) |数组 |简单| **暴力** **双指针/快慢指针/双指针**|
343343
|[0028.实现strStr()](https://github.com/youngyangyang04/leetcode/blob/master/problems/0028.实现strStr().md) |字符串 |简单| **KMP** |
344344
|[0035.搜索插入位置](https://github.com/youngyangyang04/leetcode/blob/master/problems/0035.搜索插入位置.md) |数组 |简单| **暴力** **二分**|
345345
|[0053.最大子序和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0053.最大子序和.md) |数组 |简单|**暴力** **贪心** 动态规划 分治|

‎problems/0015.三数之和.md

Lines changed: 12 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -16,12 +16,23 @@ https://leetcode-cn.com/problems/3sum/
1616

1717
### 双指针
1818

19-
推荐使用这个方法，排序后用双指针前后操作，比较容易达到去重的目的，但也有一些细节需要注意，我在如下代码详细注释了需要注意的点。
19+
**其实这道题目使用哈希法并不十分合适**，因为在去重的操作中有很多细节需要注意，在面试中很难直接写出没有bug的代码，而且是用哈希法 在使用两层for循环的时候，能做的剪枝操作很有限，虽然时间复杂度是O(n^2)，也是可以在leetcode上通过，但是程序的执行时间依然比较长 。
20+
21+
接下来我来介绍另一个解法：双指针法，**这道题目使用双指针法 要比哈希法高效一些**，那么来讲解一下具体实现的思路。
2022

2123
动画效果如下：
2224

2325
<video src='../video/15.三数之和.mp4' controls='controls' width='640' height='320' autoplay='autoplay'> Your browser does not support the video tag.</video></div>
2426

27+
拿这个nums数组来举例，首先将数组排序，然后 有一层for循环，i从下表0的地方开始，同时定一个下表left 定义在i+1的位置上，定义下表right 在数组结尾的位置上。
28+
29+
我们依然还是在数组中找到 abc 使得a + b +c =0，我们这里相当于 a = nums[i] b = nums[left] c = nums[right]。
30+
31+
接下来我们如何移动left 和right呢， 如果nums[i] + nums[left] + nums[right] > 0 就说明 此时三数之和大了，因为数组是排序后了，所以right下表就应该想左移动，这样才能让三数之和小一些。
32+
33+
如果 nums[i] + nums[left] + nums[right] < 0 说明 此时 三数之和小了， left 就向右移动，才能让三数之和大一些，直到left与right相遇为止。
34+
35+
2536
时间复杂度：O(n^2)
2637

2738
## C++代码

‎problems/0018.四数之和.md

Lines changed: 8 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,14 @@ https://leetcode-cn.com/problems/4sum/
44

55
## 思路
66

7-
四数之和，和[三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)是一个思路，都是使用双指针法，但是有一些细节需要注意，例如： 不要判断`nums[k] > target` 就返回了，三数之和 可以通过 `nums[i] > 0` 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值
7+
8+
四数之和，和[三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)是一个思路，都是使用双指针法，但是有一些细节需要注意，例如： 不要判断`nums[k] > target` 就返回了，三数之和 可以通过 `nums[i] > 0` 就返回了，因为 0 已经是确定的数了，四数之和这道题目 target是任意值。
9+
10+
三数之和 我们是一层for循环，然后循环内有left和right下表作为指针，四数之和，就可以是两层for循环，依然是循环内有left和right下表作为指针，三数之和的时间复杂度是O(n^2)，四数之和的时间复杂度是O(n^3) 。
11+
12+
动画如下：
13+
<video src='../video/15.三数之和.mp4' controls='controls' width='640' height='320' autoplay='autoplay'> Your browser does not support the video tag.</video></div>
14+
815

916
## C++代码
1017
```

‎problems/0026.删除排序数组中的重复项.md

Lines changed: 25 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,33 @@
11
## 题目地址
22
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
33

4-
## 思路
4+
# 思路
55

6-
此题就是O(n)的解法，拼速度的话，也就是剪剪枝
7-
注意题目中：你不需要考虑数组中超出新长度后面的元素。 说明是要对原数组进行操作的
6+
此题使用双指针法，O(n)的时间复杂度，拼速度的话，可以剪剪枝。
87

9-
## 解法
8+
注意题目中：不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
9+
10+
双指针法，动画如下：
11+
12+
<video src='../video/26.删除排序数组中的重复项.mp4' controls='controls' width='640' height='320' autoplay='autoplay'> Your browser does not support the video tag.</video></div>
13+
14+
其实**双指针法在在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法，可以将时间复杂度O(n^2)的解法优化为 O(n)的解法，例如：**
15+
16+
* [0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)
17+
* [0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)
18+
* [0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
19+
* [0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)
20+
* [0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
21+
* [剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
22+
23+
**还有链表找环，也用到双指针：**
24+
25+
* [0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)
26+
27+
大家都可以去做一做，感受一下双指针法的内在逻辑！
28+
29+
30+
# C++ 代码
1031

1132

1233
```

‎problems/0027.移除元素.md

Lines changed: 82 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -1,11 +1,90 @@
11
> 笔者在BAT从事技术研发多年，利用工作之余重刷leetcode，更多原创文章请关注公众号「代码随想录」。
22
3-
## 题目地址
3+
# 题目地址
44

55
https://leetcode-cn.com/problems/remove-element/
66

7-
建议做完这道题，接着再去做 26. 删除排序数组中的重复项， 对这种类型的题目就有有所感觉
7+
# 思路
88

9+
有的同学可能说了，多余的元素，删掉不就得了。
10+
11+
**要清楚数组的元素在内存地址中是连续的，数组中的元素是不能删掉的，只能覆盖。**
12+
13+
# 暴力解法
14+
15+
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
16+
17+
如动画所示：
18+
19+
<video src='../video/27.移除元素-暴力解法.mp4' controls='controls' width='640' height='320' autoplay='autoplay'> Your browser does not support the video tag.</video></div>
20+
21+
很明显暴力解法的时间复杂度是O(n^2)，这道题目暴力解法在leetcode上是可以过的。
22+
23+
代码如下：
24+
25+
```
26+
class Solution {
27+
public:
28+
int removeElement(vector<int>& nums, int val) {
29+
int size = nums.size();
30+
for (int i = 0; i < size; i++) {
31+
if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
32+
for (int j = i + 1; j < size; j++) {
33+
nums[j - 1] = nums[j];
34+
}
35+
i--; // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
36+
size--;// 此时数组的大小-1
37+
}
38+
}
39+
return size;
40+
41+
}
42+
};
43+
```
44+
45+
# 双指针法
46+
47+
双指针法（快慢指针法）： **说白了就是通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。**
48+
49+
先看一下动画理解一下：
50+
51+
52+
<video src='../video/27.移除元素.mp4' controls='controls' width='640' height='320' autoplay='autoplay'> Your browser does not support the video tag.</video></div>
53+
54+
代码如下：
55+
```
56+
// 时间复杂度：O(n)
57+
// 空间复杂度：O(1)
58+
class Solution {
59+
public:
60+
int removeElement(vector<int>& nums, int val) {
61+
int slowIndex = 0; // index为 慢指针
62+
for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) { // i 为快指针
63+
if (val != nums[fastIndex]) { //将快指针对应的数值赋值给慢指针对应的数值
64+
nums[slowIndex++] = nums[fastIndex]; 注意这里是slowIndex++ 而不是slowIndex--
65+
}
66+
}
67+
return slowIndex;
68+
}
69+
};
70+
```
71+
72+
其实**双指针法（快慢指针法）在在数组和链表的操作中是非常常见的，很多考察数组和链表操作的面试题，都使用双指针法，可以将时间复杂度O(n^2)的解法优化为 O(n)的解法，例如：**
73+
74+
* [0015.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)
75+
* [0018.四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)
76+
* [0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
77+
* [0206.翻转链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0206.翻转链表.md)
78+
* [0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)
79+
* [剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)
80+
81+
**还有链表找环，也用到双指针：**
82+
83+
* [0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)
84+
85+
大家都可以去做一做，感受一下双指针法的内在逻辑！
86+
87+
# 本题C++代码
988
## 暴力解法
1089

1190
时间复杂度：O(n^2)
@@ -30,7 +109,7 @@ public:
30109
};
31110
```
32111

33-
## 快慢指针解法
112+
## 双指针解法
34113
时间复杂度：O(n)
35114
空间复杂度：O(1)
36115
```

‎problems/0142.环形链表II.md

Lines changed: 30 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,20 @@
1-
## 题目地址
1+
# 题目地址
22
https://leetcode-cn.com/problems/linked-list-cycle-ii/
33

4-
## 思路
4+
> 找到有没有环已经很不容易了，还要让我找到环的入口?
5+
6+
# 第142题.环形链表II
7+
8+
题意：
9+
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
10+
11+
为了表示给定链表中的环，使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
12+
13+
**说明**：不允许修改给定的链表。
14+
15+
![循环链表](https://img-blog.csdnimg.cn/20200816110112704.png)
16+
17+
# 思路
518

619
这道题目，不仅考察对链表的操作，而且还需要一些数学运算。
720

@@ -10,15 +23,15 @@ https://leetcode-cn.com/problems/linked-list-cycle-ii/
1023
* 判断链表是否环
1124
* 如果有环，如何找到这个环的入口
1225

13-
### 判断链表是否有环
26+
## 判断链表是否有环
1427

1528
可以使用快慢指针法， 分别定义 fast 和 slow指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。
1629

1730
为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢
1831

1932
首先第一点： **fast指针一定先进入环中，如果fast 指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。**
2033

21-
那么我们来看一下，**为什么fast指针和slow指针一定会相遇呢**
34+
那么来看一下，**为什么fast指针和slow指针一定会相遇呢？**
2235

2336
可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。
2437

@@ -31,41 +44,39 @@ fast和slow各自再走一步， fast和slow就相遇了
3144
这是因为fast是走两步，slow是走一步，**其实相对于slow来说，fast是一个节点一个节点的靠近slow的**，所以fast一定可以和slow重合。
3245

3346

34-
### 如果有环，如何找到这个环的入口
35-
36-
**此时我们已经可以判断链表是否有环了，那么接下来要找这个环的入口了**
47+
## 如果有环，如何找到这个环的入口
3748

49+
**此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。**
3850

3951
假设从头结点到环形入口节点 的节点数为x。
4052
环形入口节点到 fast指针与slow指针相遇节点 节点数为y。
4153
从相遇节点 再到环形入口节点节点数为 z。 如图所示：
54+
4255
<img src='../pics/142环形链表2.png' width=600> </img></div>
4356

4457
那么相遇时：
45-
slow指针走过的节点数为: x + y
46-
fast指针走过的节点数： x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数
58+
slow指针走过的节点数为: `x + y`，
59+
fast指针走过的节点数：` x + y + n (y + z)`，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。
4760

48-
49-
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2
61+
因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：
5062

5163
`(x + y) * 2 = x + y + n (y + z)`
5264

5365
两边消掉一个（x+y）: `x + y = n (y + z) `
5466

55-
因为我们要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
67+
因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。
5668

57-
所以我们要求x ，将x单独放在左面：`x = n (y + z) - y`
69+
所以要求x ，将x单独放在左面：`x = n (y + z) - y` ,
5870

59-
在从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：`x = (n - 1) (y + z) + z ` 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针
71+
再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：`x = (n - 1) (y + z) + z ` 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。
6072

61-
这个公式说明什么呢，
73+
这个公式说明什么呢？
6274

6375
先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。
6476

65-
当 n为1的时候，公式就化解为 `x = z`
66-
77+
当 n为1的时候，公式就化解为 `x = z`，
6778

68-
这就意味着，**从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点**
79+
这就意味着，**从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点**。
6980

7081

7182
也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。
@@ -77,7 +88,7 @@ fast指针走过的节点数： x + y + n (y + z)，n为fast指针在环内走
7788
其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。
7889

7990

80-
## 代码
91+
# C++代码
8192

8293
```
8394
/**

‎problems/0151.翻转字符串里的单词.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,10 @@ https://leetcode-cn.com/problems/reverse-words-in-a-string/
1616
* 将整个字符串反转
1717
* 将每个单词反转
1818

19+
如动画所示：
20+
21+
<img src='../video/151翻转字符串里的单词.gif' width=600> </img></div>
22+
1923
这样我们就完成了翻转字符串里的单词。
2024

2125
## 代码

‎problems/0202.快乐数.md

Lines changed: 9 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3,16 +3,22 @@ https://leetcode-cn.com/problems/happy-number/
33

44
# 思路
55

6-
这道题目重点是，题目中说了会 **无限循环**， 那么也就是说 求和的过程中，sum会重复出现，这对我们解题很重要，这样我们就可以使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止
6+
这道题目看上去貌似一道数学问题，其实它也需要使用哈希法！
77

8-
还有就是求和的过程，如果对 取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难
8+
这道题目重点是，题目中说了会 **无限循环**，那么也就是说**求和的过程中，sum会重复出现，这对解题很重要！**
9+
10+
这样就可以使用哈希法，来判断这个sum是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止。
11+
12+
判断sum是否重复出现就可以使用unordered_set。
13+
14+
**还有一个难点就是求和的过程，如果对取数值各个位上的单数操作不熟悉的话，做这道题也会比较艰难。**
915

1016
# C++代码
1117

1218
```
1319
class Solution {
1420
public:
15-
// 取和
21+
// 取数值各个位上的单数之和
1622
int getSum(int n) {
1723
int sum = 0;
1824
while (n) {

‎problems/0219.存在重复元素II.md

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ https://leetcode-cn.com/problems/contains-duplicate-ii/
44

55
## 思路
66

7-
使用哈希策略，map数据结构来记录数组元素和对应的元素所在下表
7+
使用哈希策略，map数据结构来记录数组元素和对应的元素所在下表，看代码，已经详细注释。
88

99
## C++代码
1010

@@ -14,7 +14,8 @@ public:
1414
bool containsNearbyDuplicate(vector<int>& nums, int k) {
1515
unordered_map<int, int> map; // key: 数组元素， value：元素所在下表
1616
for (int i = 0; i < nums.size(); i++) {
17-
if (map.find(nums[i]) != map.end()) { // 找到了在索引i之前就出现过nums[i]这个元素
17+
// 找到了在索引i之前就出现过nums[i]这个元素
18+
if (map.find(nums[i]) != map.end()) {
1819
int distance = i - map[nums[i]];
1920
if (distance <= k) {
2021
return true;

0 commit comments

Comments
 (0)