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

Commit634dcfb

Browse files
Update
1 parent4ebcfbb commit634dcfb

9 files changed

+296
-9
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -59,6 +59,9 @@
5959
*[字符串：总结篇！](https://mp.weixin.qq.com/s/gtycjyDtblmytvBRFlCZJg)
6060
*[栈与队列：来看看栈和队列不为人知的一面](https://mp.weixin.qq.com/s/VZRjOccyE09aE-MgLbCMjQ)
6161
*[栈与队列：我用栈来实现队列怎么样？](https://mp.weixin.qq.com/s/P6tupDwRFi6Ay-L7DT4NVg)
62+
*[栈与队列：用队列实现栈还有点别扭](https://mp.weixin.qq.com/s/yzn6ktUlL-vRG3-m5a8_Yw)
63+
*[栈与队列：系统中处处都是栈的应用](https://mp.weixin.qq.com/s/nLlmPMsDCIWSqAtr0jbrpQ)
64+
*[栈与队列：匹配问题都是栈的强项](https://mp.weixin.qq.com/s/eynAEbUbZoAWrk0ZlEugqg)
6265

6366
（持续更新中....）
6467

@@ -475,6 +478,7 @@ backtracking() {
475478
|[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**双指针**|
476479
|[ 剑指Offer58-I.翻转单词顺序](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**模拟/双指针**|
477480
|[剑指Offer58-II.左旋转字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer58-II.左旋转字符串.md)|字符串|简单|**反转操作**|
481+
|[剑指Offer59-I.滑动窗口的最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer59-I.滑动窗口的最大值.md)|滑动窗口/队列|困难|**单调队列**|
478482
|[面试题02.07.链表相交](https://github.com/youngyangyang04/leetcode/blob/master/problems/面试题02.07.链表相交.md)|链表|简单|**模拟**|
479483

480484
持续更新中....

‎pics/93.复原IP地址.png

146 KB
Loading

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

Lines changed: 113 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,117 @@
11
##题目地址
22
https://leetcode-cn.com/problems/restore-ip-addresses/
33

4+
#93. 复原IP地址
5+
6+
给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。
7+
8+
有效的 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
9+
10+
例如："0.1.2.201" 和 "192.168.1.1" 是 有效的 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效的 IP 地址。
11+
12+
 
13+
14+
示例 1：
15+
输入：s = "25525511135"
16+
输出：["255.255.11.135","255.255.111.35"]
17+
18+
示例 2：
19+
输入：s = "0000"
20+
输出：["0.0.0.0"]
21+
22+
示例 3：
23+
输入：s = "1111"
24+
输出：["1.1.1.1"]
25+
26+
示例 4：
27+
输入：s = "010010"
28+
输出：["0.10.0.10","0.100.1.0"]
29+
30+
示例 5：
31+
输入：s = "101023"
32+
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
33+
34+
提示：
35+
0 <= s.length <= 3000
36+
s 仅由数字组成
37+
38+
439
##思路
540

41+
这道题目相信大家刚看时看到的时候，应该会一脸茫然。
42+
43+
那么只要意识到这是切割问题，那么切割问题就可以使用回溯搜索法把所有可能性搜出来，和[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md) 类似。
44+
45+
那么切割问题可以抽象为树型结构，如图：
46+
47+
<imgsrc='../pics/93.复原IP地址.png'width=600> </img></div>
48+
49+
终止条件： 和[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md) 不同，本题明确要求只会分成4段，所以不能用切割线切到最后作为终止条件，而是分割的段数作为终止条件。
50+
51+
代码如下：
52+
53+
```
54+
if (pointNum == 3) { // 逗点数量为3时，分隔结束
55+
// 判断第四段子字符串是否合法，如果合法就放进result中
56+
if (isValid(s, startIndex, s.size() - 1)) {
57+
result.push_back(s);
58+
}
59+
return;
60+
}
61+
```
62+
63+
那么再来看循环遍历的过程如何截取子串。
64+
65+
在`for (int i = startIndex; i < s.size(); i++)`循环中[startIndex, i]这个区间就是截取的子串，需要判断这个子串是否合法，如果合法就在字符串后面加上符号`.`表示已经分割。
66+
67+
然后就是递归和回溯的过程：
68+
69+
递归调用时，下一层递归的startIndex要从i+2开始（因为刚刚在字符串中加入了分隔符`.`），同时记录分割符的数量pointNum 要 +1。
70+
71+
回溯的时候，就将刚刚加入的分隔符`.` 删掉就可以了，**pointNum其实也要减一，但是 pointNum+1 的逻辑放在递归函数的参数里了，这里相当于隐藏了回溯pointNum的过程**。
72+
73+
递归和回溯代码如下：
74+
75+
```
76+
// 插入逗点之后下一个子串的起始位置为i+2
77+
backtracking(s, i + 2, pointNum + 1);
78+
s.erase(s.begin() + i + 1); // 回溯时删掉逗点
79+
```
80+
81+
最后就是在写一个判断段位是否是有效段位了。
82+
83+
主要考虑到如下三点：
84+
85+
* 段位以0为开头的数字不合法
86+
* 段位里有非正整数字符不合法
87+
* 段位如果大于255了不合法
88+
89+
代码如下：
90+
91+
```
92+
// 判断字符串s在左闭又闭区间[start, end]所组成的数字是否合法
93+
bool isValid(const string& s, int start, int end) {
94+
if (start > end) {
95+
return false;
96+
}
97+
if (s[start] == '0' && start != end) { // 0开头的数字不合法
98+
return false;
99+
}
100+
int num = 0;
101+
for (int i = start; i <= end; i++) {
102+
if (s[i] > '9' || s[i] < '0') { // 遇到非数字字符不合法
103+
return false;
104+
}
105+
num = num * 10 + (s[i] - '0');
106+
if (num > 255) { // 如果大于255了不合法
107+
return false;
108+
}
109+
}
110+
return true;
111+
}
112+
```
113+
114+
关键代码已经讲完，整体代码如下：
6115

7116
##C++代码
8117

@@ -11,7 +120,7 @@ class Solution {
11120
private:
12121
vector<string> result;// 记录结果
13122
// startIndex: 搜索的起始位置，pointNum:添加逗点的数量
14-
voidsearch(string& s, int startIndex, int pointNum) {
123+
voidbacktracking(string& s, int startIndex, int pointNum) {
15124
if (pointNum == 3) { // 逗点数量为3时，分隔结束
16125
// 判断第四段子字符串是否合法，如果合法就放进result中
17126
if (isValid(s, startIndex, s.size() - 1)) {
@@ -26,7 +135,7 @@ private:
26135
// 合法，在i的后面插入一个逗点
27136
s.insert(s.begin() + i + 1 , '.');
28137
// 插入逗点之后下一个子串的起始位置为i+2
29-
search(s, i + 2, pointNum + 1);
138+
backtracking(s, i + 2, pointNum + 1);
30139
s.erase(s.begin() + i + 1); // 回溯时删掉逗点
31140
} else break;
32141
}
@@ -36,7 +145,7 @@ private:
36145
if (start > end) {
37146
return false;
38147
}
39-
if (s[start] == '0' && start != end) {// 0开头的数字不合法
148+
if (s[start] == '0' && start != end) {// 0开头的数字不合法
40149
return false;
41150
}
42151
int num = 0;
@@ -54,7 +163,7 @@ private:
54163
public:
55164
vector<string> restoreIpAddresses(string s) {
56165
result.clear();
57-
search(s, 0, 0);
166+
backtracking(s, 0, 0);
58167
return result;
59168
}
60169
};

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

Lines changed: 43 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -68,9 +68,51 @@ void backtracking (const string& s, int startIndex) {
6868
}
6969
```
7070

71-
在来看看在递归循环，中如何截取子串呢
71+
在来看看在递归循环，中如何截取子串呢？
7272

73+
在`for (int i = startIndex; i < s.size(); i++)`循环中，我们 定义了起始位置startIndex，那么[startIndex, i] 就是要截取的子串。
7374

75+
首先判断这个子串是不是回文，如果是回文，就加入在`vector<string> path`中，path用来记录切割过的回文子串。
76+
77+
代码如下：
78+
79+
```
80+
for (int i = startIndex; i < s.size(); i++) {
81+
if (isPalindrome(s, startIndex, i)) { // 是回文子串
82+
// 获取[startIndex,i]在s中的子串
83+
string str = s.substr(startIndex, i - startIndex + 1);
84+
path.push_back(str);
85+
} else { // 如果不是则直接跳过
86+
continue;
87+
}
88+
}
89+
```
90+
91+
然后就开始递归与回溯的过程，递归的时候，我们要传入i+1 作为下一轮递归的遍历的其实位置（同样也就是切割线）。 大家可以发现在处理组合问题中，也要传入的是i+1，所以 切割问题和组合问题是最像的。
92+
93+
代码如下：
94+
95+
```
96+
backtracking(s, i + 1, path); // 寻找i+1为起始位置的子串
97+
path.pop_back(); // 回溯过程，弹出本次已经填在的子串
98+
```
99+
100+
最后我们看一下回文子串要如何判断了，判断一个字符串是否是回文。
101+
102+
可以使用双指针法，一个指针从前向后，一个指针从后先前，如果前后指针所指向的元素是相等的，就是回文字符串了。
103+
104+
代码如下：
105+
```
106+
bool isPalindrome(const string& s, int start, int end) {
107+
for (int i = start, j = end; i < j; i++, j--) {
108+
if (s[i] != s[j]) {
109+
return false;
110+
}
111+
}
112+
return true;
113+
}
114+
```
115+
此时关键代码已经讲解完毕，整体代码如下（详细注释了）
74116

75117
##C++代码
76118
```

‎problems/0150.逆波兰表达式求值.md

Lines changed: 89 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,9 +1,73 @@
11
##题目地址
22
https://leetcode-cn.com/problems/evaluate-reverse-polish-notation/
33

4-
##思路
4+
>这不仅仅是一道好题，也展现出计算机的思考方式
55
6-
这道题目相当于是二叉树中的后序遍历，也引申出栈与递归之间在某种程度上是可以转换的！
6+
#150. 逆波兰表达式求值
7+
根据 逆波兰表示法，求表达式的值。
8+
9+
有效的运算符包括 + ,  - ,  * ,  / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
10+
11+
说明：
12+
13+
整数除法只保留整数部分。
14+
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
15+
 
16+
17+
示例 1：
18+
输入:["2", "1", "+", "3", " * "]
19+
输出: 9
20+
解释: 该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
21+
22+
示例 2：
23+
输入:["4", "13", "5", "/", "+"]
24+
输出: 6
25+
解释: 该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6
26+
27+
示例 3：
28+
输入:["10", "6", "9", "3", "+", "-11", " * ", "/", " * ", "17", "+", "5", "+"]
29+
输出: 22
30+
解释:
31+
该算式转化为常见的中缀算术表达式为：
32+
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
33+
= ((10 * (6 / (12 * -11))) + 17) + 5
34+
= ((10 * (6 / -132)) + 17) + 5
35+
= ((10 * 0) + 17) + 5
36+
= (0 + 17) + 5
37+
= 17 + 5
38+
= 22
39+
 
40+
41+
逆波兰表达式：是一种后缀表达式，所谓后缀就是指算符写在后面。
42+
43+
平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
44+
45+
该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。
46+
47+
逆波兰表达式主要有以下两个优点：
48+
49+
* 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
50+
51+
* 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中。
52+
53+
#思路
54+
55+
在上一篇文章中[栈与队列：匹配问题都是栈的强项](https://mp.weixin.qq.com/s/eynAEbUbZoAWrk0ZlEugqg)提到了 递归就是用栈来实现的。
56+
57+
所以**栈与递归之间在某种程度上是可以转换的！**这一点我们在后续讲解二叉树的时候，会更详细的讲解到。
58+
59+
那么来看一下本题，**其实逆波兰表达式相当于是二叉树中的后序遍历**。 大家可以把运算符作为中间节点，按照后序遍历的规则画出一个二叉树。
60+
61+
但我们没有必要从二叉树的角度去解决这个问题，只要知道逆波兰表达式是用后续遍历的方式把二叉树序列化了，就可以了。
62+
63+
在进一步看，本题中每一个子表达式要得出一个结果，然后拿这个结果再进行运算，那么**这岂不就是一个相邻字符串消除的过程，和[栈与队列：匹配问题都是栈的强项](https://mp.weixin.qq.com/s/eynAEbUbZoAWrk0ZlEugqg)中的对对碰游戏是不是就非常像了。**
64+
65+
如动画所示：
66+
<imgsrc='../video/150.逆波兰表达式求值.gif'width=600> </img></div>
67+
68+
相信看完动画大家应该知道，这和[1047. 删除字符串中的所有相邻重复项](https://mp.weixin.qq.com/s/eynAEbUbZoAWrk0ZlEugqg)是差不错的，只不过本题不要相邻元素做消除了，而是做运算！
69+
70+
代码如下：
771

872
##C++代码
973

@@ -26,9 +90,30 @@ public:
2690
st.push(stoi(tokens[i]));
2791
}
2892
}
29-
return st.top();
93+
int result = st.top();
94+
st.pop(); // 把栈里最后一个元素弹出（其实不弹出也没事）
95+
return result;
3096
}
3197
};
3298
```
33-
>更过算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
99+
100+
#题外话
101+
102+
我们习惯看到的表达式都是中缀表达式，因为符合我们的习惯，但是中缀表达式对于计算机来说就不是很友好了。
103+
104+
例如：4 + 13 / 5，这就是中缀表达式，计算机从左到右去扫描的话，扫到13，还要判断13后面是什么运算法，还要比较一下优先级，然后13还和后面的5做运算，做完运算之后，还要向前回退到 4 的位置，继续做加法，你说麻不麻烦！
105+
106+
那么将中缀表达式，转化为后缀表达式之后：["4", "13", "5", "/", "+"] ，就不一样了，计算机可以利用栈里顺序处理，不需要考虑优先级了。也不用回退了，**所以后缀表达式对计算机来说是非常友好的。**
107+
108+
可以说本题不仅仅是一道好题，也展现出计算机的思考方式。
109+
110+
在1970年代和1980年代，惠普在其所有台式和手持式计算器中都使用了RPN（后缀表达式），直到2020年代仍在某些模型中使用了RPN。
111+
112+
参考维基百科如下：
113+
114+
>During the 1970s and 1980s, Hewlett-Packard used RPN in all of their desktop and hand-held calculators, and continued to use it in some models into the 2020s.
115+
116+
117+
118+
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。
34119

‎problems/0226.翻转二叉树.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,8 @@ https://leetcode-cn.com/problems/invert-binary-tree/
55

66
###递归法
77
写递归算法的时候，要想一想是采用前中后序哪种遍历方式
8+
o
9+
如果对递归还不熟，可以看这里[彻底吃透二叉树的前中后序递归法和迭代法！！](https://leetcode-cn.com/problems/binary-tree-inorder-traversal/solution/che-di-chi-tou-er-cha-shu-de-qian-zhong-hou-xu-d-2/)
810

911
我们先看看递归算法，对于二叉树的递归方式有三种前中后序，先来看看前序遍历。
1012

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
2+
原理：[0239.滑动窗口最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0239.滑动窗口最大值.md) |滑动窗口/队列 |困难|**单调队列**|
3+
4+
```
5+
class Solution {
6+
public:
7+
class MyQueue { //单调队列（从大到小）
8+
public:
9+
deque<int> que; // 使用deque来实现单调队列
10+
void pop(int value) {
11+
if (!que.empty() && value == que.front()) {
12+
que.pop_front();
13+
}
14+
}
15+
void push(int value) {
16+
while (!que.empty() && value > que.back()) {
17+
que.pop_back();
18+
}
19+
que.push_back(value);
20+
21+
}
22+
int front() {
23+
return que.front();
24+
}
25+
};
26+
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
27+
MyQueue que;
28+
vector<int> result;
29+
if (nums.empty()) {
30+
return result;
31+
}
32+
for (int i = 0; i < k; i++) { // 先将前k的元素放进队列
33+
que.push(nums[i]);
34+
}
35+
result.push_back(que.front()); // result 记录前k的元素的最大值
36+
for (int i = k; i < nums.size(); i++) {
37+
que.pop(nums[i - k]); // 模拟滑动窗口的移动
38+
que.push(nums[i]); // 模拟滑动窗口的移动
39+
result.push_back(que.front()); // 记录对应的最大值
40+
}
41+
return result;
42+
}
43+
};
44+
45+
```
1.38 MB
Loading
1.13 MB
Binary file not shown.

0 commit comments

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