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

Commit4ebcfbb

Browse files
Update
1 parent015394c commit4ebcfbb

10 files changed

+174
-31
lines changed
64.3 KB
Loading

‎pics/131.分割回文串.png‎

103 KB
Loading

‎pics/37.解数独.png‎

153 KB
Loading

‎problems/0017.电话号码的字母组合.md‎

Lines changed: 5 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -24,11 +24,13 @@ https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/
2424

2525
这是一个回溯法的经典题目，**不要以为回溯是一个性能很高的算法，回溯其实就是暴力枚举，纯暴力，搜出所有的可能性。**
2626

27-
回溯一般都伴随着递归，而这种组合问题，都可以画成一个树形结构。如图所示：
27+
回溯一般都伴随着递归，而这种组合问题，都可以画成一个树形结构。
2828

29-
<imgsrc='../pics/17. 电话号码的字母组合.jpeg'width=600> </img></div>
29+
例如：输入："23"，如图所示：
3030

31-
可以想成遍历这棵树，然后把叶子节点都保存下来。
31+
<imgsrc='../pics/17. 电话号码的字母组合.png'width=600> </img></div>
32+
33+
可以想成遍历这棵树，然后把叶子节点都保存下来，输出["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]。
3234

3335

3436
3. 输入1 * #按键等等异常情况

‎problems/0020.有效的括号.md‎

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -94,7 +94,11 @@ cd a/b/c/../../
9494

9595
那么什么时候说明左括号和右括号全都匹配了呢，就是字符串遍历完之后，栈是空的，就说明全都匹配了。
9696

97-
分析完之后，代码其实就比较好些了，如下：
97+
分析完之后，代码其实就比较好写了，
98+
99+
但还有一些技巧，在匹配左括号的时候，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈代码实现要简单的多了！
100+
101+
实现代码如下：
98102

99103
##C++代码
100104

@@ -118,5 +122,7 @@ public:
118122
}
119123
};
120124
```
125+
技巧性的东西没有固定的学习方法，还是要多看多练，自己总灵活运用了。
126+
121127
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
122128

‎problems/0037.解数独.md‎

Lines changed: 26 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -4,46 +4,61 @@ https://leetcode-cn.com/problems/sudoku-solver/
44

55
#思路
66

7-
这道题目和之前递归的方式都不一样，这里相当于两层递归，之前的都是一层递归
7+
棋盘搜索问题依然是要使用回溯法，暴力搜索，只不过这次我们要做的是双层递归。
8+
9+
怎么做双层递归呢？如果大家之前做过回溯类型的题目，例如：，77.组合（组合问题），131.分割回文串（分割问题），78.子集（子集问题），46.全排列（排列问题），以及51.N皇后（N皇后问题）等等，都会发现，这些都是单层递归。
10+
11+
**如果大家以上这几道题目没有做过的话，不建议上来就做这道题哈！**
12+
13+
n皇后因为每一行每一列只放一个皇后，只需要一层for循环遍历行数，递归来处理每一行的一个皇后放在哪里就可以。
14+
15+
本题就不一样了，本题中棋盘每一个位置都要放一个数字，这个问题的树形结构要比N皇后更宽更深。
16+
17+
如图所示：
18+
19+
<imgsrc='../pics/37.解数独.png'width=600> </img></div>
20+
21+
可以看出我们需要的是一个二维的递归（也就是两个for循环，递归遍历每一个棋盘的位置）
22+
23+
这道题目和之前递归的方式都不一样，这里相当于两层递归，之前的都是一层递归。
824

925
#C++代码
1026

1127
```
1228
class Solution {
1329
private:
1430
bool backtracking(vector<vector<char>>& board) {
15-
for (int i = 0; i < board.size(); i++) {
16-
for (int j = 0; j < board[0].size(); j++) {
31+
for (int i = 0; i < board.size(); i++) { // 遍历行
32+
for (int j = 0; j < board[0].size(); j++) { // 遍历列
1733
if (board[i][j] != '.') continue;
18-
for (char k = '1'; k <= '9'; k++) {
19-
if (isValid(i, j, k, board)) {
34+
for (char k = '1'; k <= '9'; k++) { // (i, j) 这个位置放k是否合适
35+
if (isValid(i, j, k, board)) {
2036
board[i][j] = k;
21-
if (backtracking(board)) return true;
37+
if (backtracking(board)) return true; // 如果找到合适一组立刻返回
2238
board[i][j] = '.';
2339
}
2440
}
2541
return false;
2642
}
2743
}
28-
return true;
44+
return true; // 遍历完没有返回false，说明找到了合适棋盘位置了
2945
3046
}
3147
bool isValid(int row, int col, char val, vector<vector<char>>& board) {
3248
33-
for (int i = 0; i < 9; i++) {
49+
for (int i = 0; i < 9; i++) { // 判断行里是否重复
3450
if (board[row][i] == val) {
3551
return false;
3652
}
3753
}
38-
for (int j = 0; j < 9; j++) {
54+
for (int j = 0; j < 9; j++) { // 判断列里是否重复
3955
if (board[j][col] == val) {
4056
return false;
4157
}
42-
4358
}
4459
int startRow = (row / 3) * 3;
4560
int startCol = (col / 3) * 3;
46-
for (int i = startRow; i < startRow + 3; i++) {
61+
for (int i = startRow; i < startRow + 3; i++) { // 判断9方格里是否重复
4762
for (int j = startCol; j < startCol + 3; j++) {
4863
if (board[i][j] == val ) {
4964
return false;

‎problems/0131.分割回文串.md‎

Lines changed: 76 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -4,30 +4,97 @@ https://leetcode-cn.com/problems/palindrome-partitioning/
44

55
##思路
66

7+
（分割 有这么多系列啊！！！！！）
8+
9+
本题这涉及到两个关键问题：
10+
11+
1. 切割问题，有不同的切割方式
12+
2. 判断回文
13+
14+
相信这里不同的切割方式可以搞懵很多同学了。
15+
16+
17+
这种题目，想用for循环暴力解法，可能都不那么容易写出来，所以要换一种暴力的方式，就是回溯
18+
19+
一些同学可能想不清楚 回溯究竟是如果切割子串
20+
21+
我们来分析一下切割，其实切割，类似于组合问题。
22+
23+
例如对于字符串abcdef，
24+
25+
组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中在选组第三个.....。
26+
切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中在切割第三段.....。
27+
28+
感受出来了不？
29+
30+
所以切割问题，也可以抽象为一颗树形结构，如图：
31+
32+
<imgsrc='../pics/131.分割回文串.png'width=600> </img></div>
33+
34+
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
35+
36+
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
37+
38+
回溯法模板：
39+
40+
```
41+
backtracking() {
42+
if (终止条件) {
43+
存放结果;
44+
}
45+
46+
for (选择：选择列表（可以想成树中节点孩子的数量）) {
47+
递归，处理节点;
48+
backtracking();
49+
回溯，撤销处理结果
50+
}
51+
}
52+
53+
```
54+
55+
在来分析一下终止条件，要从上图中可以看出，切割线切到了字符串最后面，说明找到了一种切割方法，那么此时，就是本层递归的终止终止条件。
56+
57+
那么在代码里什么是切割线呢，在处理集合问题的时候，参数我们都要传入startIndex，表示下一轮递归遍历的起始位置，这个startIndex就是切割线。
58+
59+
代码如下：
60+
61+
```
62+
void backtracking (const string& s, int startIndex) {
63+
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
64+
if (startIndex >= s.size()) {
65+
result.push_back(path);
66+
return;
67+
}
68+
}
69+
```
70+
71+
在来看看在递归循环，中如何截取子串呢
72+
73+
774

875
##C++代码
976
```
1077
class Solution {
1178
private:
1279
vector<vector<string>> result;
13-
14-
// startIndex: 搜索的起始位置，vec: 放已经回文的子串
15-
voidsearch(const string& s, int startIndex, vector<string>& vec) {
80+
vector<string> path; // 放已经回文的子串
81+
// startIndex: 搜索的起始位置
82+
voidbacktracking(const string& s, int startIndex) {
1683
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
1784
if (startIndex >= s.size()) {
18-
result.push_back(vec);
85+
result.push_back(path);
1986
return;
2087
}
2188
for (int i = startIndex; i < s.size(); i++) {
2289
if (isPalindrome(s, startIndex, i)) { // 是回文子串
2390
// 获取[startIndex,i]在s中的子串
2491
string str = s.substr(startIndex, i - startIndex + 1);
25-
vec.push_back(str);
92+
path.push_back(str);
2693
} else { // 如果不是则直接跳过
2794
continue;
2895
}
29-
search(s, i + 1,vec); // 寻找i+1为起始位置的子串
30-
vec.pop_back(); // 回溯过程，弹出本次已经填在的子串
96+
backtracking(s, i + 1,path); // 寻找i+1为起始位置的子串
97+
path.pop_back(); // 回溯过程，弹出本次已经填在的子串
3198
}
3299
}
33100
bool isPalindrome(const string& s, int start, int end) {
@@ -41,8 +108,8 @@ private:
41108
public:
42109
vector<vector<string>> partition(string s) {
43110
result.clear();
44-
vector<string> vec;
45-
search(s, 0 , vec);
111+
path.clear();
112+
backtracking(s, 0);
46113
return result;
47114
}
48115
};
Lines changed: 54 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,60 @@
11
##题目地址
22
https://leetcode-cn.com/problems/remove-all-adjacent-duplicates-in-string/
33

4-
##思路
4+
>匹配问题都是栈的强项
5+
6+
#1047. 删除字符串中的所有相邻重复项
7+
8+
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
9+
10+
在 S 上反复执行重复项删除操作，直到无法继续删除。
11+
12+
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
13+
14+
15+
示例：
16+
输入："abbaca"
17+
输出："ca"
18+
解释：
19+
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。
20+
 
21+
22+
提示：
23+
1 <= S.length <= 20000
24+
S 仅由小写英文字母组成。
25+
26+
#思路
27+
28+
##题外话
29+
30+
这道题目就像是我们玩过的游戏对对碰，如果相同的元素放在挨在一起就要消除。
31+
32+
可能我们在玩游戏的时候感觉理所当然应该消除，但程序又怎么知道该如果消除呢，特别是消除之后又有新的元素可能挨在一起。
33+
34+
此时游戏的后端逻辑就可以用一个栈来实现（我没有实际考察对对碰或者爱消除游戏的代码实现，仅从原理上进行推断）。
35+
36+
游戏开发可能使用栈结构，编程语言的一些功能实现也会使用栈结构，实现函数递归调用就需要栈，但不是每种编程语言都支持递归，例如：
37+
38+
<imgsrc='../pics/1047.删除字符串中的所有相邻重复项.png'width=600> </img></div>
39+
40+
**递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中**，然后递归返回的时候，从栈顶弹出上一次递归的各项参数，所以这就是递归为什么可以返回上一层位置的原因。
41+
42+
相信大家应该遇到过一种错误就是栈溢出，系统输出的异常是`Segmentation fault`（当然不是所有的`Segmentation fault` 都是栈溢出导致的） ，如果你使用了递归，就要想一想是不是无限递归了，那么系统调用栈就会溢出。
43+
44+
而且**在企业项目开发中，尽量不要使用递归！**在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归（或者递归层级过深），**造成栈溢出错误（这种问题还不好排查！）**
45+
46+
好了，题外话over，我们进入正题。
47+
48+
##正题
49+
50+
本题要删除相邻相同元素，其实也是匹配问题，相同左元素相当于左括号，相同右元素就是相当于右括号，匹配上了就删除。
51+
52+
那么再来看一下本题：可以把字符串顺序放到一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
553

6-
这道题目就像是我们玩过的游戏对对碰， 可以把字符串放到与一个栈中，然后如果相同的话 栈就弹出，这样最后栈里剩下的元素都是相邻不相同的元素了。
754

855
如动画所示：
956

10-
<videosrc='../video/1047.删除字符串中的所有相邻重复项.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
57+
<imgsrc='../video/1047.删除字符串中的所有相邻重复项.gif'width=600> </img></div>
1158

1259
从栈中弹出剩余元素，此时是字符串ac，因为从栈里弹出的元素是倒叙的，所以在对字符串进行反转一下，就得到了最终的结果。
1360

@@ -22,20 +69,20 @@ public:
2269
if (st.empty() || s != st.top()) {
2370
st.push(s);
2471
} else {
25-
st.pop(); // s== st.top()
72+
st.pop(); // s与 st.top()相等的情况
2673
}
2774
}
2875
string result = "";
29-
while(!st.empty()) {
76+
while(!st.empty()) { // 将栈中元素放到result字符串汇总
3077
result += st.top();
3178
st.pop();
3279
}
33-
reverse(result.begin(), result.end()); // 此时字符串需要反转一下
80+
reverse(result.begin(), result.end()); // 此时字符串需要反转一下
3481
return result;
3582
3683
}
3784
};
3885
```
3986

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

‎problems/回溯总结.md‎

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
2+
* 集合问题
3+
* 切割问题
4+
* 子集问题
5+
* 排列问题
6+
* 皇后问题
662 KB
Loading

0 commit comments

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