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

Commit141cccb

Browse files
Update
1 parent1c4ab01 commit141cccb

File tree

7 files changed

+233
-30
lines changed

7 files changed

+233
-30
lines changed

‎README.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -138,6 +138,7 @@
138138
*[本周小结！（回溯算法系列一）](https://mp.weixin.qq.com/s/m2GnTJdkYhAamustbb6lmw)
139139
*[回溯算法：求组合总和（二）](https://mp.weixin.qq.com/s/FLg8G6EjVcxBjwCbzpACPw)
140140
*[回溯算法：求组合总和（三）](https://mp.weixin.qq.com/s/_1zPYk70NvHsdY8UWVGXmQ)
141+
*[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)
141142

142143
（持续更新中....）
143144

@@ -336,6 +337,7 @@
336337
|[0113.路径总和II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0113.路径总和II.md)|二叉树树|简单|**深度优先搜索/递归****回溯****栈**|
337338
|[0116.填充每个节点的下一个右侧节点指针](https://github.com/youngyangyang04/leetcode/blob/master/problems/0116.填充每个节点的下一个右侧节点指针.md)|二叉树|中等|**递归****迭代/广度优先搜索**|
338339
|[0117.填充每个节点的下一个右侧节点指针II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0117.填充每个节点的下一个右侧节点指针II.md)|二叉树|中等|**递归****迭代/广度优先搜索**|
340+
|[0127.单词接龙](https://github.com/youngyangyang04/leetcode/blob/master/problems/ 0127.单词接龙.md)|广度优先搜索|中等|**广度优先搜索**|
339341
|[0129.求根到叶子节点数字之和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0129.求根到叶子节点数字之和.md)|二叉树|中等|**递归/回溯** 递归里隐藏着回溯，和113.路径总和II类似|
340342
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|
341343
|[0141.环形链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0141.环形链表.md)|链表|简单|**快慢指针/双指针**|
@@ -377,6 +379,7 @@
377379
|[0434.字符串中的单词数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0434.字符串中的单词数.md)|字符串|简单|**模拟**|
378380
|[0450.删除二叉搜索树中的节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/0450.删除二叉搜索树中的节点.md)|树|中等|**递归**|
379381
|[0454.四数相加II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0454.四数相加II.md)|哈希表|中等|**哈希**|
382+
|[0455.分发饼干](https://github.com/youngyangyang04/leetcode/blob/master/problems/0455.分发饼干.md)|贪心|简单|**贪心**|
380383
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)|字符创|简单|**KMP**|
381384
|[0486.预测赢家](https://github.com/youngyangyang04/leetcode/blob/master/problems/0486.预测赢家.md)|动态规划|中等|**递归****记忆递归****动态规划**|
382385
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯算法**|

‎pics/127.单词接龙.png‎

45.2 KB
Loading

‎pics/455.分发饼干.png‎

34.5 KB
Loading

‎problems/0057.插入区间.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,8 @@
11

2+
#链接
3+
https://leetcode-cn.com/problems/insert-interval/
4+
5+
#思路
26
这道题目合并的情况有很多种，想想都让人头疼。
37

48
我把这道题目化为三步：

‎problems/0093.复原IP地址.md‎

Lines changed: 111 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -1,17 +1,18 @@
11
##题目地址
2-
https://leetcode-cn.com/problems/restore-ip-addresses/
32

4-
#93. 复原IP地址
3+
>一些录友表示跟不上现在的节奏，想从头开始打卡学习起来，可以在公众号左下方，「算法汇总」可以找到历史文章，都是按系列排好顺序的，挨个看就可以了，看文章下的留言你就会发现，有很多录友都在从头打卡，你并不孤单！
4+
5+
#93.复原IP地址
6+
7+
题目地址：https://leetcode-cn.com/problems/restore-ip-addresses/
58

69
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
710

811
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
912

1013
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
1114

12-
 
13-
14-
示例 1：
15+
示例 1：
1516
输入：s = "25525511135"
1617
输出：["255.255.11.135","255.255.111.35"]
1718

@@ -36,17 +37,44 @@ https://leetcode-cn.com/problems/restore-ip-addresses/
3637
s 仅由数字组成
3738

3839

39-
##思路
40+
#思路
41+
42+
做这道题目之前，最好先把[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)这个做了。
4043

41-
这道题目相信大家刚看时看到的时候，应该会一脸茫然。
44+
这道题目相信大家刚看的时候，应该会一脸茫然。
4245

43-
那么只要意识到这是切割问题，那么切割问题就可以使用回溯搜索法把所有可能性搜出来，和[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md) 类似。
46+
其实只要意识到这是切割问题，**切割问题就可以使用回溯搜索法把所有可能性搜出来**，和刚做过的[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)就十分类似了。
4447

45-
那么切割问题可以抽象为树型结构，如图：
48+
切割问题可以抽象为树型结构，如图：
4649

4750
<imgsrc='../pics/93.复原IP地址.png'width=600> </img></div>
4851

49-
终止条件： 和[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md) 不同，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
52+
53+
##回溯三部曲
54+
55+
* 递归参数
56+
57+
在[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)中我们就提到切割问题类似组合问题。
58+
59+
startIndex一定是需要的，因为不能重复分割，记录下一层递归分割的起始位置。
60+
61+
本题我们还需要一个变量pointNum，记录添加逗点的数量。
62+
63+
所以代码如下：
64+
65+
```
66+
vector<string> result;// 记录结果
67+
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
68+
void backtracking(string& s, int startIndex, int pointNum) {
69+
```
70+
71+
* 递归终止条件
72+
73+
终止条件和[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)情况就不同了，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
74+
75+
pointNum表示逗点数量，pointNum为3说明字符串分成了4段了。
76+
77+
然后验证一下第四段是否合法，如果合法就加入到结果集里
5078

5179
代码如下：
5280

@@ -60,24 +88,40 @@ if (pointNum == 3) { // 逗点数量为3时，分隔结束
6088
}
6189
```
6290

63-
那么再来看循环遍历的过程如何截取子串。
91+
* 单层搜索的逻辑
92+
93+
在[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)中已经讲过在循环遍历中如何截取子串。
94+
95+
在`for (int i = startIndex; i < s.size(); i++)`循环中[startIndex, i]这个区间就是截取的子串，需要判断这个子串是否合法。
6496

65-
在`for (int i = startIndex; i < s.size(); i++)`循环中[startIndex, i]这个区间就是截取的子串，需要判断这个子串是否合法，如果合法就在字符串后面加上符号`.`表示已经分割。
97+
如果合法就在字符串后面加上符号`.`表示已经分割。
98+
99+
如果不合法就结束本层循环，如图中剪掉的分支：
100+
101+
<imgsrc='../pics/93.复原IP地址.png'width=600> </img></div>
66102

67103
然后就是递归和回溯的过程：
68104

69-
递归调用时，下一层递归的startIndex要从i+2开始（因为刚刚在字符串中加入了分隔符`.`），同时记录分割符的数量pointNum 要 +1。
105+
递归调用时，下一层递归的startIndex要从i+2开始（因为需要在字符串中加入了分隔符`.`），同时记录分割符的数量pointNum 要 +1。
70106

71-
回溯的时候，就将刚刚加入的分隔符`.` 删掉就可以了，**pointNum其实也要减一，但是 pointNum+1 的逻辑放在递归函数的参数里了，这里相当于隐藏了回溯pointNum的过程**。
107+
回溯的时候，就将刚刚加入的分隔符`.` 删掉就可以了，pointNum也要-1。
72108

73-
递归和回溯代码如下：
109+
代码如下：
74110

75111
```
76-
// 插入逗点之后下一个子串的起始位置为i+2
77-
backtracking(s, i + 2, pointNum + 1);
78-
s.erase(s.begin() + i + 1); // 回溯时删掉逗点
112+
for (int i = startIndex; i < s.size(); i++) {
113+
if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
114+
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
115+
pointNum++;
116+
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
117+
pointNum--; // 回溯
118+
s.erase(s.begin() + i + 1); // 回溯删掉逗点
119+
} else break; // 不合法，直接结束本层循环
120+
}
79121
```
80122

123+
##判断子串是否合法
124+
81125
最后就是在写一个判断段位是否是有效段位了。
82126

83127
主要考虑到如下三点：
@@ -111,9 +155,27 @@ bool isValid(const string& s, int start, int end) {
111155
}
112156
```
113157

114-
关键代码已经讲完，整体代码如下：
158+
##C++代码
159+
115160

116-
##C++代码
161+
根据[关于回溯算法，你该了解这些！](https://mp.weixin.qq.com/s/gjSgJbNbd1eAA5WkA-HeWw)给出的回溯算法模板：
162+
163+
```
164+
void backtracking(参数) {
165+
if (终止条件) {
166+
存放结果;
167+
return;
168+
}
169+
170+
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
171+
处理节点;
172+
backtracking(路径，选择列表); // 递归
173+
回溯，撤销处理结果
174+
}
175+
}
176+
```
177+
178+
可以写出如下回溯算法C++代码：
117179

118180
```
119181
class Solution {
@@ -128,16 +190,14 @@ private:
128190
}
129191
return;
130192
}
131-
// 从起始位置开始构造字段字符串串
132193
for (int i = startIndex; i < s.size(); i++) {
133-
// 判断 [startIndex,i] 这个区间的子串是否合法
134-
if (isValid(s, startIndex, i)) {
135-
// 合法，在i的后面插入一个逗点
136-
s.insert(s.begin() + i + 1 , '.');
137-
// 插入逗点之后下一个子串的起始位置为i+2
138-
backtracking(s, i + 2, pointNum + 1);
139-
s.erase(s.begin() + i + 1); // 回溯时删掉逗点
140-
} else break;
194+
if (isValid(s, startIndex, i)) { // 判断 [startIndex,i] 这个区间的子串是否合法
195+
s.insert(s.begin() + i + 1 , '.'); // 在i的后面插入一个逗点
196+
pointNum++;
197+
backtracking(s, i + 2, pointNum); // 插入逗点之后下一个子串的起始位置为i+2
198+
pointNum--; // 回溯
199+
s.erase(s.begin() + i + 1); // 回溯删掉逗点
200+
} else break; // 不合法，直接结束本层循环
141201
}
142202
}
143203
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
@@ -167,6 +227,27 @@ public:
167227
return result;
168228
}
169229
};
230+
170231
```
171232

172-
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
233+
#总结
234+
235+
在[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)中我列举的分割字符串的难点，本题都覆盖了。
236+
237+
而且本题还需要操作字符串添加逗号作为分隔符，并验证区间的合法性。
238+
239+
可以说是[回溯算法：分割回文串](https://mp.weixin.qq.com/s/Pb1epUTbU8fHIht-g_MS5Q)的加强版。
240+
241+
在本文的树形结构图中，我已经把详细的分析思路都画了出来，相信大家看了之后一定会思路清晰不少！
242+
243+
**就酱，「代码随想录」值得推荐给你的朋友们！**
244+
245+
246+
一些录友表示跟不上现在的节奏，想从头开始打卡学习起来，可以在在公众号左下方，「算法汇总」可以找到历史文章，都是按系列排好顺序的，挨个看就可以了，别忘了打卡。
247+
248+
**很多录友都在从头开始打卡学习，看看前面文章的留言区就知道了，你并不孤单！**
249+
250+
251+
252+
>我是[程序员Carl](https://github.com/youngyangyang04)，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，期待你的关注！
253+

‎problems/0127.单词接龙.md‎

Lines changed: 73 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,73 @@
1+
2+
##题目链接
3+
4+
https://leetcode-cn.com/problems/word-ladder/
5+
6+
##思路
7+
8+
以示例1为例，从这个图中可以看出 hit 到 cog的路线，不止一条，有三条，两条是最短的长度为5，一条长度为6。
9+
10+
<imgsrc='../pics/127.单词接龙.png'width=600> </img></div>
11+
12+
本题只需要求出最短长度就可以了，不用找出路径。
13+
14+
所以这道题要解决两个问题：
15+
16+
* 图中的线是如何连在一起的
17+
* 起点和终点的最短路径长度
18+
19+
20+
首先题目中并没有给出点与点之间的连线，而是要我们自己去连，条件是字符只能差一个，所以判断点与点之间的关系，要自己判断是不是差一个字符，如果差一个字符，那就是有链接。
21+
22+
然后就是求起点和终点的最短路径长度，**这里无向图求最短路，广搜最为合适，广搜只要搜到了终点，那么一定是最短的路径**。因为广搜就是以起点中心向四周扩散的搜索。
23+
24+
本题如果用深搜，会非常麻烦。
25+
26+
另外需要有一个注意点：
27+
28+
* 本题是一个无向图，需要用标记位，标记着节点是否走过，否则就会死循环！
29+
* 本题给出集合是数组型的，可以转成set结构，查找更快一些
30+
31+
C++代码如下：（详细注释）
32+
33+
```
34+
class Solution {
35+
public:
36+
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
37+
// 将vector转成unordered_set，提高查询速度
38+
unordered_set<string> wordSet(wordList.begin(), wordList.end());
39+
// 如果endWord没有在wordSet出现，直接返回0
40+
if (wordSet.find(endWord) == wordSet.end()) return 0;
41+
// 记录word是否访问过
42+
unordered_map<string, int> visitMap; // <word, 查询到这个word路径长度>
43+
// 初始化队列
44+
queue<string> que;
45+
que.push(beginWord);
46+
// 初始化visitMap
47+
visitMap.insert(pair<string, int>(beginWord, 1));
48+
49+
while(!que.empty()) {
50+
string word = que.front();
51+
que.pop();
52+
int path = visitMap[word]; // 这个word的路径长度
53+
for (int i = 0; i < word.size(); i++) {
54+
string newWord = word; // 用一个新单词替换word，因为每次置换一个字母
55+
for (int j = 0 ; j < 26; j++) {
56+
newWord[i] = j + 'a';
57+
if (newWord == endWord) return path + 1; // 找到了end，返回path+1
58+
// wordSet出现了newWord，并且newWord没有被访问过
59+
if (wordSet.find(newWord) != wordSet.end()
60+
&& visitMap.find(newWord) == visitMap.end()) {
61+
// 添加访问信息
62+
visitMap.insert(pair<string, int>(newWord, path + 1));
63+
que.push(newWord);
64+
}
65+
}
66+
}
67+
}
68+
return 0;
69+
}
70+
};
71+
```
72+
>我是[程序员Carl](https://github.com/youngyangyang04)，组队刷题可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，期待你的关注！
73+

‎problems/0455.分发饼干.md‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
2+
##链接
3+
4+
https://leetcode-cn.com/problems/assign-cookies/
5+
6+
##思路
7+
8+
这道题目呢，其实可以用较大大的饼干优先满足可以满足的胃口大的小孩。
9+
10+
注意我这里用的是 可以满足的胃口大的小孩。这样就不会造成大饼干的浪费。
11+
12+
所以使用贪心策略，讲饼干数组和小孩数组排序。
13+
14+
然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量的大小就可以了。
15+
16+
如图：
17+
18+
<imgsrc='../pics/455.分发饼干.png'width=600> </img></div>
19+
20+
21+
C++代码整体如下：
22+
23+
```
24+
class Solution {
25+
public:
26+
int findContentChildren(vector<int>& g, vector<int>& s) {
27+
sort(g.begin(), g.end());
28+
sort(s.begin(), s.end());
29+
int index = s.size() - 1; // 饼干数组的下表
30+
int result = 0;
31+
for (int i = g.size() - 1; i >= 0; i--) {
32+
if (index >= 0 && s[index] >= g[i]) {
33+
result++;
34+
index--;
35+
}
36+
}
37+
return result;
38+
}
39+
};
40+
```
41+
>我是[程序员Carl](https://github.com/youngyangyang04)，组队刷题可以找我，本文[leetcode刷题攻略](https://github.com/youngyangyang04/leetcode-master)已收录，更多[精彩算法文章](https://mp.weixin.qq.com/mp/appmsgalbum?__biz=MzUxNjY5NTYxNA==&action=getalbum&album_id=1485825793120387074&scene=173#wechat_redirect)尽在：[代码随想录](https://img-blog.csdnimg.cn/20200815195519696.png)，期待你的关注！
42+

0 commit comments

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