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

Commitdb295f4

Browse files
Update
1 parentf407ffd commitdb295f4

13 files changed

+307
-77
lines changed

‎README.md

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -148,6 +148,8 @@
148148
*[回溯算法：排列问题！](https://mp.weixin.qq.com/s/SCOjeMX1t41wcvJq49GhMw)
149149
*[回溯算法：排列问题（二）](https://mp.weixin.qq.com/s/9L8h3WqRP_h8LLWNT34YlA)
150150
*[本周小结！（回溯算法系列三）](https://mp.weixin.qq.com/s/tLkt9PSo42X60w8i94ViiA)
151+
*[本周小结！（回溯算法系列三）续集](https://mp.weixin.qq.com/s/kSMGHc_YpsqL2j-jb_E_Ag)
152+
*[视频来了！！带你学透回溯算法（理论篇）](https://mp.weixin.qq.com/s/wDd5azGIYWjbU0fdua_qBg)
151153

152154

153155
（持续更新中....）
@@ -388,6 +390,7 @@
388390
|[0350.两个数组的交集II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0350.两个数组的交集II.md)|哈希表|简单|**哈希**|
389391
|[0383.赎金信](https://github.com/youngyangyang04/leetcode/blob/master/problems/0383.赎金信.md)|数组|简单|**暴力****字典计数****哈希**|
390392
|[0404.左叶子之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0404.左叶子之和.md)|树/二叉树|简单|**递归****迭代**|
393+
|[0406.根据身高重建队列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0406.根据身高重建队列.md)|树/二叉树|简单|**递归****迭代**|
391394
|[0416.分割等和子集](https://github.com/youngyangyang04/leetcode/blob/master/problems/0416.分割等和子集.md)|动态规划|中等|**背包问题/01背包**|
392395
|[0429.N叉树的层序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0429.N叉树的层序遍历.md)|树|简单|**队列/广度优先搜索**|
393396
|[0434.字符串中的单词数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0434.字符串中的单词数.md)|字符串|简单|**模拟**|

‎pics/135.分发糖果.png

52.4 KB
Loading

‎pics/135.分发糖果1.png

126 KB
Loading

‎pics/406.根据身高重建队列.png

70.5 KB
Loading

‎pics/51.N皇后.png

20.3 KB
Loading

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -320,7 +320,7 @@ void getNext(int* next, const string& s){
320320

321321
在文本串s里 找是否出现过模式串t。
322322

323-
定义两个下表j 指向模式串起始位置，i指向文本串其实位置。
323+
定义两个下表j 指向模式串起始位置，i指向文本串起始位置。
324324

325325
那么j初始值依然为-1，为什么呢？**依然因为next数组里记录的起始位置为-1。**
326326

‎problems/0051.N皇后.md

Lines changed: 144 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,12 @@
1+
>开始棋盘问题，如果对回溯法还不了解的同学可以看这个视频
12
2-
#题目链接
3+
如果对回溯法理论还不清楚的同学，可以先看这个视频[视频来了！！带你学透回溯算法（理论篇）](https://mp.weixin.qq.com/s/wDd5azGIYWjbU0fdua_qBg)
34

4-
https://leetcode-cn.com/problems/n-queens/
55

66
#第51题. N皇后
7+
8+
题目链接：https://leetcode-cn.com/problems/n-queens/
9+
710
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
811

912
上图为 8 皇后问题的一种解法。
@@ -14,86 +17,168 @@ n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并
1417
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
1518

1619
示例:
17-
18-
输入: 4
19-
输出:[
20-
[".Q..", // 解法 1
21-
"...Q",
22-
"Q...",
23-
"..Q."],
24-
25-
["..Q.", // 解法 2
26-
"Q...",
27-
"...Q",
28-
".Q.."]
29-
]
30-
解释: 4 皇后问题存在两个不同的解法。
31-
32-
提示：
33-
20+
输入: 4
21+
输出:[
22+
[".Q..", // 解法 1
23+
"...Q",
24+
"Q...",
25+
"..Q."],
26+
27+
["..Q.", // 解法 2
28+
"Q...",
29+
"...Q",
30+
".Q.."]
31+
]
32+
解释: 4 皇后问题存在两个不同的解法。
33+
34+
提示：
3435
>皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一到七步，可进可退。（引用自 百度百科 - 皇后 ）
3536
3637

3738
#思路
3839

39-
都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了 排列，组合，子集问题之后，遇到这种二位矩阵还会有点不知所措。
40+
都知道n皇后问题是回溯算法解决的经典问题，但是用回溯解决多了组合、切割、子集、排列问题之后，遇到这种二位矩阵还会有点不知所措。
4041

4142
首先来看一下皇后们的约束条件：
4243

4344
1. 不能同行
4445
2. 不能同列
4546
3. 不能同斜线
4647

47-
4848
确定完约束条件，来看看究竟要怎么去搜索皇后们的位置，其实搜索皇后的位置，可以抽象为一棵树。
4949

50-
下面我用一个3 * 3 的棋牌，如图：
50+
下面我用一个3 * 3 的棋牌，将搜索过程抽象为一颗树，如图：
5151

52-
<imgsrc='../pics/51.N皇后1.png'width=600> </img></div>
52+
![51.N皇后](https://img-blog.csdnimg.cn/20201116173551789.png)
5353

54-
将搜索过程抽象为一颗树，如图：
54+
从图中，可以看出，二维矩阵中矩阵的高就是这颗树的高度，矩阵的宽就是树形结构中每一个节点的宽度。
5555

56+
那么我们用皇后们的约束条件，来回溯搜索这颗树，**只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了**。
5657

57-
<imgsrc='../pics/51.N皇后.png'width=600> </img></div>
58+
##回溯三部曲
5859

59-
从图中，可以看出，二维矩阵，其实矩阵的行，就是 这颗树的高度，矩阵的宽就是二叉树没一个节点孩子的宽度。
60+
按照我总结的如下回溯模板，我们来依次分析：
6061

62+
```
63+
void backtracking(参数) {
64+
if (终止条件) {
65+
存放结果;
66+
return;
67+
}
68+
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
69+
处理节点;
70+
backtracking(路径，选择列表); // 递归
71+
回溯，撤销处理结果
72+
}
73+
}
74+
```
75+
76+
* 递归函数参数
6177

62-
那么我们用皇后们的约束条件，来回溯搜索这颗二叉树，**只要搜索到了树的叶子节点，说明就找到了皇后们的合理位置了。**
78+
我依然是定义全局变量二维数组result来记录最终结果。
6379

64-
我总结的回溯模板如下：
80+
参数n是棋牌的大小，然后用row来记录当前遍历到棋盘的第几层了。
81+
82+
代码如下：
6583

6684
```
67-
backtracking() {
68-
if (终止条件) {
69-
存放结果;
85+
vector<vector<string>> result;
86+
void backtracking(int n, int row, vector<string>& chessboard) {
87+
```
88+
89+
* 递归终止条件
90+
91+
在如下树形结构中：
92+
![51.N皇后](https://img-blog.csdnimg.cn/20201116173551789.png)
93+
94+
可以看出，当递归到棋盘最底层（也就是叶子节点）的时候，就可以收集结果并返回了。
95+
96+
代码如下：
97+
98+
```
99+
if (row == n) {
100+
result.push_back(chessboard);
101+
return;
102+
}
103+
```
104+
105+
* 单层搜索的逻辑
106+
107+
递归深度就是row控制棋盘的行，每一层里for循环的col控制棋盘的列，一行一列，确定了放置皇后的位置。
108+
109+
每次都是要从新的一行的起始位置开始搜，所以都是从0开始。
110+
111+
代码如下：
112+
113+
```
114+
for (int col = 0; col < n; col++) {
115+
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
116+
chessboard[row][col] = 'Q'; // 放置皇后
117+
backtracking(n, row + 1, chessboard);
118+
chessboard[row][col] = '.'; // 回溯，撤销皇后
70119
}
120+
}
121+
```
71122

72-
for (枚举同一个位置的所有可能性，可以想成节点孩子的数量) {
73-
递归，处理节点;
74-
backtracking();
75-
回溯，撤销处理结果
123+
* 验证棋牌是否合法
124+
125+
按照如下标准去重：
126+
127+
1. 不能同行
128+
2. 不能同列
129+
3. 不能同斜线 （45度和135度角）
130+
131+
代码如下：
132+
133+
```
134+
bool isValid(int row, int col, vector<string>& chessboard, int n) {
135+
int count = 0;
136+
// 检查列
137+
for (int i = 0; i < row; i++) { // 这是一个剪枝
138+
if (chessboard[i][col] == 'Q') {
139+
return false;
140+
}
141+
}
142+
// 检查 45度角是否有皇后
143+
for (int i = row - 1, j = col - 1; i >=0 && j >= 0; i--, j--) {
144+
if (chessboard[i][j] == 'Q') {
145+
return false;
146+
}
147+
}
148+
// 检查 135度角是否有皇后
149+
for(int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
150+
if (chessboard[i][j] == 'Q') {
151+
return false;
152+
}
76153
}
154+
return true;
77155
}
78156
```
79157

80-
那么按照这个模板不能写出如下代码：
158+
在这份代码中，细心的同学可以发现为什么没有在同行进行检查呢？
159+
160+
因为在单层搜索的过程中，每一层递归，只会选for循环（也就是同一行）里的一个元素，所以不用去重了。
161+
162+
那么按照这个模板不难写出如下代码：
81163

82-
#C++代码
164+
##C++代码
83165

84166
```
85167
class Solution {
86168
private:
87-
void backtracking(int n, int row, vector<string>& chessboard, vector<vector<string>>& result) {
169+
vector<vector<string>> result;
170+
// n 为输入的棋盘大小
171+
// row 是当前递归到棋牌的第几行了
172+
void backtracking(int n, int row, vector<string>& chessboard) {
88173
if (row == n) {
89174
result.push_back(chessboard);
90175
return;
91176
}
92177
for (int col = 0; col < n; col++) {
93-
if (isValid(row, col, chessboard, n)) {
94-
chessboard[row][col] = 'Q';
95-
backtracking(n, row + 1, chessboard, result);
96-
chessboard[row][col] = '.';
178+
if (isValid(row, col, chessboard, n)) { // 验证合法就可以放
179+
chessboard[row][col] = 'Q'; // 放置皇后
180+
backtracking(n, row + 1, chessboard);
181+
chessboard[row][col] = '.'; // 回溯，撤销皇后
97182
}
98183
}
99184
}
@@ -121,11 +206,25 @@ bool isValid(int row, int col, vector<string>& chessboard, int n) {
121206
}
122207
public:
123208
vector<vector<string>> solveNQueens(int n) {
209+
result.clear();
124210
std::vector<std::string> chessboard(n, std::string(n, '.'));
125-
vector<vector<string>> result;
126-
127-
backtracking(n, 0, chessboard, result);
211+
backtracking(n, 0, chessboard);
128212
return result;
129213
}
130214
};
131215
```
216+
217+
可以看出，除了验证棋盘合法性的代码，省下来部分就是按照回溯法模板来的。
218+
219+
#总结
220+
221+
本题是我们解决棋盘问题的第一道题目。
222+
223+
如果从来没有接触过N皇后问题的同学看着这样的题会感觉无从下手，可能知道要用回溯法，但也不知道该怎么去搜。
224+
225+
**这里我明确给出了棋盘的宽度就是for循环的长度，递归的深度就是棋盘的高度，这样就可以套进回溯法的模板里了**。
226+
227+
大家可以在仔细体会体会！
228+
229+
就酱，如果感觉「代码随想录」干货满满，就分享给身边的朋友同学吧，他们可能也需要！
230+

‎problems/0053.最大子序和.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ public:
4949

5050
<imgsrc='../video/53.最大子序和.gif'width=600> </img></div>
5151

52-
红色的其实位置就是贪心每次取count为正数的时候，开始一个区间的统计。
52+
红色的起始位置就是贪心每次取count为正数的时候，开始一个区间的统计。
5353

5454
不难写出如下C++代码（关键地方已经注释）
5555

‎problems/0135.分发糖果.md

Lines changed: 62 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,85 @@
11

2+
##思路
3+
4+
这道题目一定是要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑就会顾此失彼。
5+
6+
本题贪心贪在哪里呢？
7+
8+
先确定每个孩子左边的情况（也就是从前向后遍历）
9+
10+
如果ratings[i] > ratings[i - 1] 那么[i]的糖 一定要比[i - 1]的糖多一个，所以贪心：candyVec[i] = candyVec[i - 1] + 1
11+
12+
代码如下：
13+
14+
```
15+
// 从前向后
16+
for (int i = 1; i < ratings.size(); i++) {
17+
if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
18+
}
19+
```
20+
21+
如图：
22+
23+
![135.分发糖果](https://img-blog.csdnimg.cn/20201117114916878.png)
24+
25+
再确定每个孩子右边的情况（从后向前遍历）
26+
27+
遍历顺序这里有同学可能会有疑问，为什么不能从前向后遍历呢？
28+
29+
因为如果从前向后遍历，根据 ratings[i + 1] 来确定 ratings[i] 对应的糖果，那么每次都不能利用上前一次的比较结果了。
30+
**所以确定每个孩子右边的情况一定要从后向前遍历！**
31+
32+
此时又要开始贪心，如果 ratings[i] > ratings[i + 1]，就取candyVec[i + 1] + 1 和 candyVec[i] 最大的糖果数量，**因为candyVec[i]只有取最大的才能既保持对左边candyVec[i - 1]的糖果多，也比右边candyVec[i + 1]的糖果多**。
33+
34+
如图：
35+
36+
![135.分发糖果1](https://img-blog.csdnimg.cn/20201117115658791.png)
37+
38+
所以代码如下：
39+
40+
```
41+
// 从后向前
42+
for (int i = ratings.size() - 2; i >= 0; i--) {
43+
if (ratings[i] > ratings[i + 1] ) {
44+
candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1);
45+
}
46+
}
47+
```
48+
49+
* 将问题分解为若干个子问题
50+
* 找出适合的贪心策略
51+
* 求解每一个子问题的最优解
52+
* 将局部最优解堆叠成全局最优解
53+
54+
* 分解为子问题
55+
56+
57+
258
这道题目上来也是没什么思路啊
359

460

561
这道题目不好想啊，贪心很巧妙
62+
663
```
764
class Solution {
865
public:
966
int candy(vector<int>& ratings) {
1067
vector<int> candyVec(ratings.size(), 1);
11-
// 从前向后
68+
// 从前向后
1269
for (int i = 1; i < ratings.size(); i++) {
1370
if (ratings[i] > ratings[i - 1]) candyVec[i] = candyVec[i - 1] + 1;
1471
}
1572
// 从后向前
1673
for (int i = ratings.size() - 2; i >= 0; i--) {
17-
if (ratings[i] > ratings[i + 1]&& candyVec[i] < candyVec[i + 1] + 1) {
18-
candyVec[i] = candyVec[i+ 1] + 1;
74+
if (ratings[i] > ratings[i + 1] ) {
75+
candyVec[i] =max(candyVec[i], candyVec[i+ 1] + 1);
1976
}
2077
}
21-
// 统计结果
78+
// 统计结果
2279
int result = 0;
2380
for (int i = 0; i < candyVec.size(); i++) result += candyVec[i];
2481
return result;
2582
}
2683
};
84+
2785
```

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -172,7 +172,7 @@ if (result.size() == ticketNum + 1) {
172172
if (target.second > 0 ) { // 记录到达机场是否飞过了
173173
result.push_back(target.first);
174174
target.second--;
175-
if (backtracking(ticketNum,index + 1,result)) return true;
175+
if (backtracking(ticketNum, result)) return true;
176176
result.pop_back();
177177
target.second++;
178178
}

0 commit comments

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