Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitd5a824d

Browse files
Update
1 parent1d5570b commitd5a824d

8 files changed

+200
-25
lines changed

‎README.md

Lines changed: 19 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
*[哈希表：这道题目我做过？](https://mp.weixin.qq.com/s/sYZIR4dFBrw_lr3eJJnteQ)
4141
*[哈希表：解决了两数之和，那么能解决三数之和么？](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
4242
*[双指针法：一样的道理，能解决四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
43+
*[必须掌握的数组理论知识](https://mp.weixin.qq.com/s/X7R55wSENyY62le0Fiawsg)
4344
*[数组：每次遇到二分法，都是一看就会，一写就废](https://mp.weixin.qq.com/s/fCf5QbPDtE6SSlZ1yh_q8Q)
4445
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
4546
*[数组：滑动窗口拯救了你](https://mp.weixin.qq.com/s/UrZynlqi4QpyLlLhBPglyg)
@@ -331,22 +332,6 @@ vector<vector<int>> levelOrder(TreeNode* root) {
331332
332333
```
333334

334-
##回溯算法
335-
336-
```
337-
backtracking() {
338-
if (终止条件) {
339-
存放结果;
340-
}
341-
342-
for (选择：选择列表（可以想成树中节点孩子的数量）) {
343-
递归，处理节点;
344-
backtracking();
345-
回溯，撤销处理结果
346-
}
347-
}
348-
349-
```
350335

351336

352337
可以直接解决如下题目：
@@ -376,6 +361,23 @@ int countNodes(TreeNode* root) {
376361
}
377362
```
378363

364+
##回溯算法
365+
366+
```
367+
backtracking() {
368+
if (终止条件) {
369+
存放结果;
370+
}
371+
372+
for (选择：选择列表（可以想成树中节点孩子的数量）) {
373+
递归，处理节点;
374+
backtracking();
375+
回溯，撤销处理结果
376+
}
377+
}
378+
379+
```
380+
379381
（持续补充ing）
380382

381383
#LeetCode 最强题解:
@@ -435,6 +437,7 @@ int countNodes(TreeNode* root) {
435437
|[0237.删除链表中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0237.删除链表中的节点.md)|链表|简单|**原链表移除****添加虚拟节点** 递归|
436438
|[0239.滑动窗口最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0239.滑动窗口最大值.md)|滑动窗口/队列|困难|**单调队列**|
437439
|[0242.有效的字母异位词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0242.有效的字母异位词.md)|哈希表|简单|**哈希**|
440+
|[0257.二叉树的所有路径](https://github.com/youngyangyang04/leetcode/blob/master/problems/0257.二叉树的所有路径.md)|树|简单|**递归/回溯**|
438441
|[0332.重新安排行程](https://github.com/youngyangyang04/leetcode/blob/master/problems/0332.重新安排行程.md)|深度优先搜索/回溯|中等|**深度优先搜索/回溯算法**|
439442
|[0344.反转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0344.反转字符串.md)|字符串|简单|**双指针**|
440443
|[0347.前K个高频元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0347.前K个高频元素.md)|哈希/堆/优先级队列|中等|**哈希/优先级队列**|
51.8 KB
Loading

‎problems/0028.实现strStr().md

Lines changed: 167 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -4,15 +4,178 @@ https://leetcode-cn.com/problems/implement-strstr/
44

55
##思路
66

7-
KMP 经典算法
8-
KMP的经典思想是:当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。
7+
本题是KMP 经典题目。
8+
9+
KMP的经典思想就是:**当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。**
10+
11+
如果对KMP理论基础还不够了解的同学请看[]()
12+
13+
定义一个函数getNext来构建next数组， 函数参数为指向next数组的指针，和一个字符串。 然后在函数里完成对next数组的构建。
14+
15+
16+
这其实就是计算模式串s，前缀表的过程。 主要有如下三步：
17+
18+
1. 初始化
19+
2. 处理前后缀不相同的情况
20+
3. 处理前后缀相同的情况
21+
22+
1. 初始化：
23+
24+
定义两个指针i和j，j指向前缀终止位置（严格来说是终止位置减一的位置），i指向后缀终止位置（与j同理）。
25+
26+
然后还要对next数组进行初始化赋值，如下：
27+
28+
```
29+
        int j = -1;
30+
        next[0] = j;
31+
```
32+
33+
j 为什么要初始化为 -1呢，因为之前说过 前缀表要统一减一的操作，所以j初始化为-1。
34+
35+
next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是j）
36+
37+
所以初始化next[0] = j 。
38+
39+
40+
2. 处理前后缀不相同的情况
41+
42+
43+
因为j初始化为-1，那么i就从1开始，进行s[i] 与 s[j+1]的比较。
44+
45+
所以遍历模式串s的循环下表i 要从 1开始，代码如下：
46+
47+
```
48+
        for(int i = 1; i < s.size(); i++) {
49+
```
50+
51+
如果 s[i] 与 s[j+1]不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回溯。
52+
53+
怎么回溯呢？
54+
55+
next[j]就是记录着j（包括j）之前的子串的相同前后缀的长度。
56+
57+
那么 s[i] 与 s[j+1] 不相同，就要找 j+1前一个元素在next数组里的值（就是next[j]）。
58+
59+
所以，处理前后缀不相同的情况代码如下：
60+
61+
```
62+
while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
63+
    j = next[j]; // 向前回溯
64+
}
65+
```
66+
67+
3. 处理前后缀相同的情况
68+
69+
如果s[i] 与 s[j + 1] 相同，那么就同时向后移动i 和j 说明找到了相同的前后缀，同时还要将j（前缀的长度）赋给next[i], 因为next[i]要记录相同前后缀的长度。
70+
71+
代码如下：
72+
73+
```
74+
if (s[i] == s[j + 1]) { // 找到相同的前后缀
75+
    j++;
76+
}
77+
next[i] = j;
78+
```
79+
80+
最后整体构建next数组的函数代码如下：
81+
82+
```
83+
    void getNext(int* next, const string& s){
84+
        int j = -1;
85+
        next[0] = j;
86+
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
87+
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
88+
                j = next[j]; // 向前回溯
89+
            }
90+
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
91+
                j++;
92+
            }
93+
            next[i] = j; // 将j（前缀的长度）赋给next[i]
94+
        }
95+
    }
96+
```
97+
98+
99+
代码构造next数组的逻辑流程如下：
100+
101+
<imgsrc='../../media/video/KMP精讲3.gif'width=600> </img></div>
102+
103+
104+
得到了next数组之后，就要用这个来做匹配了。
105+
106+
在文本串s里 找是否出现过模式串t。
107+
108+
定义两个下表j 指向模式串起始位置，i指向文本串其实位置。
109+
110+
那么j初始值依然为-1，为什么呢？**依然因为next数组里记录的起始位置为-1。**
111+
112+
i就从0开始，遍历文本串，代码如下：
113+
114+
```
115+
for (int i = 0; i < s.size(); i++) 
116+
```
117+
118+
接下来就是 s[i] 与 t[j + 1] （因为j从-1开始的） 经行比较。
119+
120+
如果 s[i] 与 t[j + 1] 不相同，j就要从next数组里寻找下一个匹配的位置。
121+
122+
代码如下：
123+
124+
```
125+
while(j >= 0 && s[i] != t[j + 1]) {
126+
    j = next[j];
127+
}
128+
```
129+
130+
如果 s[i] 与 t[j + 1] 相同，那么i 和 j 同时向后移动， 代码如下：
131+
132+
```
133+
if (s[i] == t[j + 1]) {
134+
    j++; // i的增加在for循环里
135+
}
136+
```
137+
138+
如何判断在文本串s里出现了模式串t呢，如果j指向了模式串t的末尾，那么就说明模式串t完全匹配文本串s里的某个子串了。
139+
140+
本题要在文本串字符串中找出模式串出现的第一个位置 (从0开始)，所以返回当前在文本串匹配模式串的位置i 减去 模式串的长度，就是文本串字符串中出现模式串的第一个位置。
141+
142+
代码如下：
143+
144+
```
145+
if (j == (t.size() - 1) ) {
146+
    return (i - t.size() + 1);
147+
}
148+
```
149+
150+
那么使用next数组，用模式串匹配文本串的整体代码如下：
151+
152+
```
153+
        int j = -1; // 因为next数组里记录的起始位置为-1
154+
        for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
155+
            while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
156+
                j = next[j]; // j 寻找之前匹配的位置
157+
            }
158+
            if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动
159+
                j++; // i的增加在for循环里
160+
            }
161+
            if (j == (t.size() - 1) ) { // 文本串s里出现了模式串t
162+
                return (i - t.size() + 1);
163+
            }
164+
        }
165+
```
166+
167+
此时所有逻辑的代码都已经写出来了，本题整体代码如下：
168+
169+
170+
171+
9172

10173
##C++代码
11174

12175
```
13176
class Solution {
14177
public:
15-
voidpreKmp(int* next, const string& s){
178+
voidgetNext(int* next, const string& s){
16179
next[0] = -1;
17180
int j = -1;
18181
for(int i = 1; i < s.size(); i++){
@@ -30,7 +193,7 @@ public:
30193
return 0;
31194
}
32195
int next[needle.size()];
33-
preKmp(next, needle);
196+
getNext(next, needle);
34197
35198
int j = -1;
36199
for (int i = 0; i < haystack.size(); i++) {

‎problems/0257.二叉树的所有路径.md

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -213,7 +213,7 @@ public:
213213

214214
注意在函数定义的时候`void traversal(TreeNode* cur, string path, vector<string>& result)` ，定义的是`string path`，说明每次都是复制赋值。
215215

216-
那么在如上代码中，貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在`traversal(cur->left, path + "->", result);`中的`path + "->"`。 每次函数调用完，path依然是没有+ 上"->" 的，这就是回溯了。
216+
那么在如上代码中，**貌似没有看到回溯的逻辑，其实不然，回溯就隐藏在`traversal(cur->left, path + "->", result);`中的`path + "->"`。** 每次函数调用完，path依然是没有+ 上"->" 的，这就是回溯了。
217217

218218
**综合以上，第二种写法更简洁，但是把很多重要的点隐藏在了代码细节里，第一种写法虽然代码多一些，但是每一个处理逻辑都完整的展现了出来。**
219219

@@ -222,3 +222,4 @@ public:
222222

223223

224224

225+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0332.重新安排行程.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -123,3 +123,4 @@ public:
123123
124124
```
125125

126+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0344.反转字符串.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -122,5 +122,5 @@ public:
122122
}
123123
};
124124
```
125-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
125+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
126126

‎problems/剑指Offer58-II.左旋转字符串.md

Lines changed: 10 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -40,9 +40,9 @@ https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/
4040

4141
例如 ：示例1中 输入：字符串abcdefg，n=2
4242

43-
1. 反转区间为前n的子串 ： bacdefg
44-
2. 反转区间为n到末尾的子串：bagfedc
45-
3. 反转整个字符串：cdefgab
43+
如图：
44+
45+
<imgsrc='../pics/剑指Offer58-II.左旋转字符串.png'width=600> </img></div>
4646

4747
最终得到左旋2个单元的字符串：cdefgab
4848

@@ -77,4 +77,11 @@ public:
7777

7878
好了，反转字符串一共就介绍到这里，相信大家此时对反转字符串的常见操作已经很了解了。
7979

80+
#题外话
81+
82+
一些同学热衷于使用substr，来做这道题。
83+
其实使用substr 和 反转 时间复杂度是一样的 ，都是O(n)，但是使用substr申请了额外空间，所以空间复杂度是O(n)，而反转方法的空间复杂度是O(1)。
84+
85+
**如果想让这套题目有意义，就不要申请额外空间。**
86+
8087
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎video/KMP详解1.gif

687 KB
Loading

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp