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

Commit7747476

Browse files
Update
1 parentd5a824d commit7747476

File tree

5 files changed

+137
-60
lines changed

5 files changed

+137
-60
lines changed

‎README.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,8 @@
5050
*[字符串：简单的反转还不够！](https://mp.weixin.qq.com/s/XGSk1GyPWhfqj2g7Cb1Vgw)
5151
*[字符串：替换空格](https://mp.weixin.qq.com/s/t0A9C44zgM-RysAQV3GZpg)
5252
*[字符串：花式反转还不够！](https://mp.weixin.qq.com/s/X3qpi2v5RSp08mO-W5Vicw)
53+
*[字符串：KMP是时候上场了（一文读懂系列）](https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug)
54+
*[字符串：都来看看KMP的看家本领！](https://mp.weixin.qq.com/s/Gk9FKZ9_FSWLEkdGrkecyg)
5355

5456
（持续更新中....）
5557

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

Lines changed: 87 additions & 58 deletions
Original file line numberDiff line numberDiff line change
@@ -2,32 +2,64 @@
22
##题目地址
33
https://leetcode-cn.com/problems/implement-strstr/
44

5-
##思路
5+
>在一个串中查找是否出现过另一个串，这是KMP的看家本领。
6+
7+
#题目：28. 实现 strStr()
8+
9+
实现 strStr() 函数。
10+
11+
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。
12+
13+
示例 1:
14+
输入: haystack = "hello", needle = "ll"
15+
输出: 2
16+
17+
示例 2:
18+
输入: haystack = "aaaaa", needle = "bba"
19+
输出: -1
20+
21+
说明:
22+
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
23+
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。
24+
25+
26+
#思路
627

728
本题是KMP 经典题目。
829

930
KMP的经典思想就是:**当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配。**
1031

11-
如果对KMP理论基础还不够了解的同学请看[]()
32+
如果对KMP理论基础还不够了解的同学请看[字符串：KMP是时候上场了（一文读懂系列）](https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug)。
1233

13-
定义一个函数getNext来构建next数组， 函数参数为指向next数组的指针，和一个字符串。 然后在函数里完成对next数组的构建。
34+
**为了和[字符串：KMP是时候上场了（一文读懂系列）](https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug)字符串命名统一，方便大家理解，以下文章统称haystack为文本串, needle为模式串。**
1435

36+
都知道使用KMP算法，一定要构造next数组。
1537

16-
这其实就是计算模式串s，前缀表的过程。 主要有如下三步：
38+
#构造next数组
39+
40+
我们定义一个函数getNext来构建next数组，函数参数为指向next数组的指针，和一个字符串。 代码如下：
41+
42+
```
43+
void getNext(int* next, const string& s)
44+
```
45+
46+
**构造next数组其实就是计算模式串s，前缀表的过程。** 主要有如下三步：
1747

1848
1. 初始化
1949
2. 处理前后缀不相同的情况
2050
3. 处理前后缀相同的情况
2151

52+
接下来我们详解详解一下。
53+
2254
1. 初始化：
2355

2456
定义两个指针i和j，j指向前缀终止位置（严格来说是终止位置减一的位置），i指向后缀终止位置（与j同理）。
2557

2658
然后还要对next数组进行初始化赋值，如下：
2759

2860
```
29-
        int j = -1;
30-
        next[0] = j;
61+
int j = -1;
62+
next[0] = j;
3163
```
3264

3365
j 为什么要初始化为 -1呢，因为之前说过 前缀表要统一减一的操作，所以j初始化为-1。
@@ -45,7 +77,7 @@ next[i] 表示 i（包括i）之前最长相等的前后缀长度（其实就是
4577
所以遍历模式串s的循环下表i 要从 1开始，代码如下：
4678

4779
```
48-
        for(int i = 1; i < s.size(); i++) {
80+
for(int i = 1; i < s.size(); i++) {
4981
```
5082

5183
如果 s[i] 与 s[j+1]不相同，也就是遇到 前后缀末尾不相同的情况，就要向前回溯。
@@ -80,29 +112,31 @@ next[i] = j;
80112
最后整体构建next数组的函数代码如下：
81113

82114
```
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]
115+
void getNext(int* next, const string& s){
116+
    int j = -1;
117+
    next[0] = j;
118+
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
119+
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
120+
            j = next[j]; // 向前回溯
94121
        }
122+
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
123+
            j++;
124+
        }
125+
        next[i] = j; // 将j（前缀的长度）赋给next[i]
95126
    }
127+
}
96128
```
97129

98130

99-
代码构造next数组的逻辑流程如下：
131+
代码构造next数组的逻辑流程动画如下：
100132

101133
<imgsrc='../../media/video/KMP精讲3.gif'width=600> </img></div>
102134

103135

104136
得到了next数组之后，就要用这个来做匹配了。
105137

138+
#使用next数组来做匹配
139+
106140
在文本串s里 找是否出现过模式串t。
107141

108142
定义两个下表j 指向模式串起始位置，i指向文本串其实位置。
@@ -150,67 +184,62 @@ if (j == (t.size() - 1) ) {
150184
那么使用next数组，用模式串匹配文本串的整体代码如下：
151185

152186
```
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-
        }
187+
int j = -1; // 因为next数组里记录的起始位置为-1
188+
for (int i = 0; i < s.size(); i++) { // 注意i就从0开始
189+
    while(j >= 0 && s[i] != t[j + 1]) { // 不匹配
190+
        j = next[j]; // j 寻找之前匹配的位置
191+
    }
192+
    if (s[i] == t[j + 1]) { // 匹配，j和i同时向后移动
193+
        j++; // i的增加在for循环里
194+
    }
195+
    if (j == (t.size() - 1) ) { // 文本串s里出现了模式串t
196+
        return (i - t.size() + 1);
197+
    }
198+
}
165199
```
166200

167201
此时所有逻辑的代码都已经写出来了，本题整体代码如下：
168202

169-
170-
171-
172-
173203
##C++代码
174204

175205
```
176206
class Solution {
177207
public:
178-
voidgetNext(int*next,conststring& s){
179-
next[0] =-1;
180-
int j = -1;
181-
for(int i = 1; i <s.size();i++){
182-
while (j >= 0 &&s[i] !=s[j +1]) {
183-
j =next[j];
184-
}
185-
if(s[i] ==s[j +1]) {
186-
j++;
187-
}
188-
next[i] = j;
189-
}
190-
}
208+
    void getNext(int* next, const string& s){
209+
        int j = -1;
210+
        next[0] = j;
211+
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
212+
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
213+
                j = next[j]; // 向前回溯
214+
            }
215+
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
216+
                j++;
217+
            }
218+
            next[i] = j; // 将j（前缀的长度）赋给next[i]
219+
        }
220+
    }
191221
int strStr(string haystack, string needle) {
192222
if (needle.size() == 0) {
193223
return 0;
194224
}
195225
int next[needle.size()];
196226
getNext(next, needle);
197-
198-
int j = -1;
199-
for (int i = 0; i < haystack.size(); i++) {
200-
while(j >= 0 && haystack[i] != needle[j + 1]) {
201-
j = next[j];
227+
int j = -1; // // 因为next数组里记录的起始位置为-1
228+
for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
229+
while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
230+
j = next[j]; // j 寻找之前匹配的位置
202231
}
203-
if (haystack[i] == needle[j + 1]) {
204-
j++;
232+
if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
233+
j++; // i的增加在for循环里
205234
}
206-
if (j == (needle.size() - 1) ) {
207-
return (i - needle.size() + 1);
235+
if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
236+
return (i - needle.size() + 1);
208237
}
209238
}
210239
return -1;
211240
}
212241
};
213242
214243
```
215-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
244+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
216245
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
##题目地址
2+
https://leetcode-cn.com/problems/binary-tree-level-order-traversal-ii/
3+
4+
##思路
5+
6+
这道题目相对于[0102.二叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0102.二叉树的层序遍历.md)，就把结果倒叙过来，就可以了。
7+
8+
层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。
9+
10+
需要借用一个辅助数据结构队列来实现，**队列先进先出，符合一层一层遍历的逻辑，而是用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。**
11+
12+
使用队列实现广度优先遍历，动画如下：
13+
14+
<videosrc='../video/102二叉树的层序遍历.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
15+
16+
这样就实现了层序从左到右遍历二叉树。
17+
18+
代码如下：这份代码也可以作为二叉树层序遍历的模板。
19+
20+
##C++代码
21+
22+
```
23+
class Solution {
24+
public:
25+
vector<vector<int>> levelOrderBottom(TreeNode* root) {
26+
queue<TreeNode*> que;
27+
if (root != NULL) que.push(root);
28+
vector<vector<int>> result;
29+
while (!que.empty()) {
30+
int size = que.size();
31+
vector<int> vec;
32+
for (int i = 0; i < size; i++) {// 这里一定要使用固定大小size，不要使用que.size()
33+
TreeNode* node = que.front();
34+
que.pop();
35+
vec.push_back(node->val);
36+
if (node->left) que.push(node->left);
37+
if (node->right) que.push(node->right);
38+
}
39+
result.push_back(vec);
40+
}
41+
reverse(result.begin(), result.end());
42+
return result;
43+
44+
}
45+
};
46+
```

‎problems/0454.四数相加II.md‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -28,9 +28,9 @@ D = [ 0, 2]
2828

2929
#思路
3030

31-
本题咋眼一看好像和[第18题. 四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)，[第15题.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)差不多，其实差很多。
31+
本题咋眼一看好像和[0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)，[0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)差不多，其实差很多。
3232

33-
**本题是使用哈希法的经典题目，而[第18题. 四数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0018.四数之和.md)，[第15题.三数之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0015.三数之和.md)并不合适使用哈希法**，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。
33+
**本题是使用哈希法的经典题目，而[0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)，[0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)并不合适使用哈希法**，因为三数之和和四数之和这两道题目使用哈希法在不超时的情况下做到对结果去重是很困难的，很有多细节需要处理。
3434

3535
**而这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况，所以相对于题目18. 四数之和，题目15.三数之和，还是简单了不少！**
3636

‎video/KMP精讲3.gif‎

1.01 MB
Loading

0 commit comments

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