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

Commit1526105

Browse files
Update
1 parent7747476 commit1526105

9 files changed

+411
-28
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,8 +50,11 @@
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+
*[字符串：反转个字符串还有这个用处？](https://mp.weixin.qq.com/s/PmcdiWSmmccHAONzU0ScgQ)
5354
*[字符串：KMP是时候上场了（一文读懂系列）](https://mp.weixin.qq.com/s/70OXnZ4Ez29CKRrUpVJmug)
5455
*[字符串：都来看看KMP的看家本领！](https://mp.weixin.qq.com/s/Gk9FKZ9_FSWLEkdGrkecyg)
56+
*[字符串：听说你对KMP有这些疑问？](https://mp.weixin.qq.com/s/mqx6IM2AO4kLZwvXdPtEeQ)
57+
*[字符串：KMP算法还能干这个！](https://mp.weixin.qq.com/s/lR2JPtsQSR2I_9yHbBmBuQ)
5558

5659
（持续更新中....）
5760

‎pics/347.前K个高频元素.png

61.6 KB
Loading

‎pics/39.组合总和.png

176 KB
Loading

‎pics/77.组合.png

90 KB
Loading

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

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -240,6 +240,46 @@ public:
240240
}
241241
};
242242
243+
```
244+
245+
前缀表不减一版本
246+
```
247+
class Solution {
248+
public:
249+
void getNext(int* next, const string& s) {
250+
int j = 0;
251+
next[0] = 0;
252+
for(int i = 1; i < s.size(); i++) {
253+
while (j > 0 && s[i] != s[j]) {
254+
j = next[j - 1];
255+
}
256+
if (s[i] == s[j]) {
257+
j++;
258+
}
259+
next[i] = j;
260+
}
261+
}
262+
int strStr(string haystack, string needle) {
263+
if (needle.size() == 0) {
264+
return 0;
265+
}
266+
int next[needle.size()];
267+
getNext(next, needle);
268+
int j = 0;
269+
for (int i = 0; i < haystack.size(); i++) {
270+
while(j > 0 && haystack[i] != needle[j]) {
271+
j = next[j - 1];
272+
}
273+
if (haystack[i] == needle[j]) {
274+
j++;
275+
}
276+
if (j == needle.size() ) {
277+
return (i - needle.size() + 1);
278+
}
279+
}
280+
return -1;
281+
}
282+
};
243283
```
244284
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
245285

‎problems/0039.组合总和.md

Lines changed: 48 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -30,36 +30,74 @@ candidates 中的数字可以无限制重复被选取。
3030

3131
#思路
3232

33+
题目中的**无限制重复被选取，吓得我赶紧想想 出现0 可咋办**，然后看到下面提示：1 <= candidates[i] <= 200，我就放心了。
34+
35+
36+
这道题上来可以这么想，看看一个数能不能构成target，一个for循环遍历一遍，再看看两个数能不能构成target，两个for循环遍历，在看看三个数能不能构成target，三个for循环遍历，直到candidates.size()个for循环遍历一遍。
37+
38+
遇到这种问题，就要想到递归的层级嵌套关系就可以解决这种多层for循环的问题，而回溯则帮我们选择每一个合适的集合！
39+
40+
那么使用回溯的时候，要知道求的是排列，还是组合，排列和组合是不一样的。
41+
42+
一些同学可能海分不清，我大概说一下：
43+
44+
**组合是不强调元素顺序的，排列是强调元素顺序的。**
45+
46+
例如 集合 1，2 和 集合 2，1 在组合上，就是一个集合，因为不强调顺序，而要是排列的话，1，2 和 2，1 就是两个集合了。
47+
48+
**求组合，和求排列的回溯写法是不一样的，代码上有小小细节上的改变。**
49+
50+
本题选组过程如下：
51+
52+
<imgsrc='../pics/39.组合总和.png'width=600> </img></div>
53+
54+
55+
分析完过程，回溯算法的模板框架如下：
56+
```
57+
backtracking() {
58+
if (终止条件) {
59+
存放结果;
60+
}
61+
62+
for (选择：选择列表（可以想成树中节点孩子的数量）) {
63+
递归，处理节点;
64+
backtracking();
65+
回溯，撤销处理结果
66+
}
67+
}
68+
```
69+
70+
按照模板不难写出如下代码，但很一些细节，我在注释中标记出来了。
71+
3372
#C++代码
3473

3574
```
36-
// 无限制重复被选取。 吓得我赶紧想想 0 可咋办
3775
class Solution {
3876
private:
3977
vector<vector<int>> result;
40-
void backtracking(vector<int>& candidates, int target, vector<int>& vec, int sum, int startIndex) {
78+
vector<int> path;
79+
void backtracking(vector<int>& candidates, int target, int sum, int startIndex) {
4180
if (sum > target) {
4281
return;
4382
}
4483
if (sum == target) {
45-
result.push_back(vec);
84+
result.push_back(path);
4685
return;
4786
}
48-
49-
//因为可重复，所以我们从0开始， 这道题目感觉像是47.全排列II，其实不是
87+
88+
//这里i 依然从 startIndex开始，因为求的是组合，如果求的是排列，那么i每次都从0开始
5089
for (int i = startIndex; i < candidates.size(); i++) {
5190
sum += candidates[i];
52-
vec.push_back(candidates[i]);
53-
backtracking(candidates, target,vec,sum, i); // 关键点在这里，不用i+1了
91+
path.push_back(candidates[i]);
92+
backtracking(candidates, target, sum, i); // 关键点在这里，不用i+1了，表示可以重复读取当前的数
5493
sum -= candidates[i];
55-
vec.pop_back();
94+
path.pop_back();
5695
5796
}
5897
}
5998
public:
6099
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
61-
vector<int> vec;
62-
backtracking(candidates, target, vec, 0, 0);
100+
backtracking(candidates, target, 0, 0);
63101
return result;
64102
}
65103
};

‎problems/0077.组合.md

Lines changed: 139 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -15,24 +15,99 @@
1515

1616
#思路
1717

18+
这是回溯法的经典题目。
19+
20+
直觉上当然是使用for循环，例如示例中k为2，很容易想到 用两个for循环，这样就可以输出 和示例中一样的结果。
21+
22+
代码如下：
23+
```
24+
int n = 4;
25+
for (int i = 1; i <= n; i++) {
26+
for (int j = i + 1; j <= n; j++) {
27+
cout << i << " " << j << endl;
28+
}
29+
}
30+
```
31+
32+
输入：n = 100, k = 3
33+
那么就三层for循环，代码如下：
34+
35+
```
36+
for (int i = 1; i <= n; i++) {
37+
for (int j = i + 1; j <= n; j++) {
38+
for (int u = j + 1; u <=n; n++) {
39+
40+
}
41+
}
42+
}
43+
```
44+
**如果n为 100，k为50呢，那就50层for循环，是不是开始窒息。**
45+
46+
那么回溯法就能解决这个问题了。
47+
48+
回溯是用来做选择的，递归用来节点层叠嵌套，**每一次的递归是层叠嵌套的关系，可以用于解决多层嵌套循环的问题。**
49+
50+
其实子集和组合问题都可以抽象为一个树形结构，如下：
51+
52+
53+
<imgsrc='../pics/77.组合.png'width=600> </img></div>
54+
55+
可以看一下这个棵树，一开始集合是 1，2，3，4， 从左向右去数，取过的数，不在重复取。
56+
57+
第一取1，集合变为2，3，4 ，因为k为2，我们只需要去一个数就可以了，分别取，2，3，4， 得到集合[1,2][1,3][1,4]，以此类推。
58+
59+
**其实这就转化成从集合中选取子集的问题，可选择的范围随着选择的进行而限缩，于是做剪枝，调整可选择的范围**
60+
61+
如何在这个树上遍历，然后收集到我们要的结果集呢，用的就是回溯搜索法，**可以发现，每次搜索到了叶子节点，我们就找到了一个结果。**
62+
63+
分析完过程，我们来看一下 回溯算法的模板框架如下：
64+
```
65+
backtracking() {
66+
if (终止条件) {
67+
存放结果;
68+
}
69+
70+
for (选择：选择列表（可以想成树中节点孩子的数量）) {
71+
递归，处理节点;
72+
backtracking();
73+
回溯，撤销处理结果
74+
}
75+
}
76+
```
77+
78+
分析模板：
79+
80+
什么是达到了终止条件，树中就可以看出，搜到了叶子节点了，就找到了一个符合题目要求的答案，就把这个答案存放起来。
81+
82+
看一下这个for循环，这个for循环是做什么的，for 就是处理树中节点各个孩子的情况， 一个节点有多少个孩子，这个for循环就执行多少次。
83+
84+
最后就要看这个递归的过程了，注意这个backtracking就是自己调用自己，实现递归。
85+
86+
一些同学对递归操作本来就不熟练，递归上面又加上一个for循环，可能就更迷糊了， 我来给大家捋顺一下。
87+
88+
这个backtracking 其实就是向树的叶子节点方向遍历， for循环可以理解是横向遍历，backtracking 就是纵向遍历，这样就把这棵树全遍历完了。
89+
90+
那么backtracking就是一直往深处遍历，总会遇到叶子节点，遇到了叶子节点，就要返回，那么backtracking的下面部分就是回溯的操作了，撤销本次处理的结果。
91+
92+
分析完模板，本题代码如下：
1893

1994
#C++ 代码
2095

2196
```
2297
class Solution {
2398
private:
2499
vector<vector<int>> result; // 存放符合条件结果的集合
25-
vector<int>vec; // 用来存放符合条件结果
100+
vector<int>path; // 用来存放符合条件结果
26101
void backtracking(int n, int k, int startIndex) {
27-
if (vec.size() == k) {
28-
result.push_back(vec);
102+
if (path.size() == k) {
103+
result.push_back(path);
29104
return;
30105
}
31106
// 这个for循环有讲究，组合的时候 要用startIndex，排列的时候就要从0开始
32107
for (int i = startIndex; i <= n; i++) {
33-
vec.push_back(i);
108+
path.push_back(i); // 处理节点
34109
backtracking(n, k, i + 1);
35-
vec.pop_back();
110+
path.pop_back(); // 回溯，撤销处理的节点
36111
}
37112
}
38113
public:
@@ -43,3 +118,62 @@ public:
43118
}
44119
};
45120
```
121+
122+
##剪枝优化
123+
124+
在遍历的过程中如下代码 ：
125+
126+
```
127+
for (int i = startIndex; i <= n; i++)
128+
```
129+
130+
这个遍历的范围是可以剪枝优化的，怎么优化呢？
131+
132+
来举一个例子，n = 4， k = 4的话，那么从2开始的遍历都没有意义了。
133+
134+
已经选择的元素个数：path.size();
135+
136+
要选择的元素个数 : k - path.size();
137+
138+
在集合n中开始选择的起始位置 : n - (k - path.size());
139+
140+
因为起始位置是从1开始的，而且代码里是n <= 起始位置，所以 集合n中开始选择的起始位置 : n - (k - path.size()) + 1;
141+
142+
所以优化之后是：
143+
144+
```
145+
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++)
146+
```
147+
148+
整体代码如下：
149+
150+
```
151+
class Solution {
152+
private:
153+
vector<vector<int>> result; // 存放符合条件结果的集合
154+
vector<int> path; // 用来存放符合条件结果
155+
void backtracking(int n, int k, int startIndex) {
156+
if (path.size() == k) {
157+
result.push_back(path);
158+
return;
159+
}
160+
// 这个for循环有讲究，组合的时候 要用startIndex，排列的时候就要从0开始
161+
for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) {
162+
path.push_back(i); // 处理节点
163+
backtracking(n, k, i + 1);
164+
path.pop_back(); // 回溯，撤销处理的节点
165+
}
166+
}
167+
public:
168+
169+
vector<vector<int>> combine(int n, int k) {
170+
backtracking(n, k, 1);
171+
return result;
172+
}
173+
};
174+
```
175+
176+
177+
178+
#观后感
179+
我来写一下观后感： 很厉害，转化成从集合中选取子集的问题，可选择的范围随着选择的进行而限缩，于是做剪枝，调整可选择的范围。 每一次的递归是层叠嵌套的关系，可以用于解决多层嵌套循环的问题。 每一层递归中，尽量节省循环次数，这样在后续的递归调用中，节省下来的循环会被以至少指数等级放大。

0 commit comments

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