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

Commit00356b6

Browse files
Update
1 parentbaf55b4 commit00356b6

11 files changed

+304
-24
lines changed

‎README.md‎

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,6 @@
6969

7070
* 双指针法
7171
*[数组：就移除个元素很难么？](https://mp.weixin.qq.com/s/wj0T-Xs88_FHJFwayElQlA)
72-
*[数组：977. 有序数组的平方]()
7372
*[字符串：这道题目，使用库函数一行代码搞定](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
7473
*[字符串：替换空格](https://mp.weixin.qq.com/s/t0A9C44zgM-RysAQV3GZpg)
7574
*[字符串：花式反转还不够！](https://mp.weixin.qq.com/s/X3qpi2v5RSp08mO-W5Vicw)
@@ -121,6 +120,7 @@
121120
*[本周小结！（二叉树系列四）](https://mp.weixin.qq.com/s/CbdtOTP0N-HIP7DR203tSg)
122121
*[二叉树：搜索树的公共祖先问题](https://mp.weixin.qq.com/s/Ja9dVw2QhBcg_vV-1fkiCg)
123122
*[二叉树：搜索树中的插入操作](https://mp.weixin.qq.com/s/lwKkLQcfbCNX2W-5SOeZEA)
123+
*[二叉树：搜索树中的删除操作](https://mp.weixin.qq.com/s/-p-Txvch1FFk3ygKLjPAKw)
124124

125125

126126

@@ -178,21 +178,28 @@
178178
*[0015.三数之和](https://mp.weixin.qq.com/s/r5cgZFu0tv4grBAexdcd8A)
179179
*[0018.四数之和](https://mp.weixin.qq.com/s/nQrcco8AZJV1pAOVjeIU_g)
180180
*[0026.删除排序数组中的重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/0026.删除排序数组中的重复项.md)
181-
*[19.删除链表的倒数第N个节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/19.删除链表的倒数第N个节点)
181+
*[0019.删除链表的倒数第N个节点](https://github.com/youngyangyang04/leetcode/blob/master/problems/19.删除链表的倒数第N个节点)
182182
*[0206.翻转链表](https://mp.weixin.qq.com/s/pnvVP-0ZM7epB8y3w_Njwg)
183183
*[0142.环形链表II](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)
184184
*[0344.反转字符串](https://mp.weixin.qq.com/s/X02S61WCYiCEhaik6VUpFA)
185185
*[剑指Offer05.替换空格](https://mp.weixin.qq.com/s/t0A9C44zgM-RysAQV3GZpg)
186186
*[0151.翻转字符串里的单词](https://mp.weixin.qq.com/s/X3qpi2v5RSp08mO-W5Vicw)
187+
*[0977.有序数组的平方](https://github.com/youngyangyang04/leetcode/blob/master/problems/0977.有序数组的平方.md)
187188

188189

189190
* 栈与队列经典题目
190191
*[0232.用栈实现队列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0232.用栈实现队列.md)
191192
*[0225.用队列实现栈](https://github.com/youngyangyang04/leetcode/blob/master/problems/0225.用队列实现栈.md)
192193
*[0020.有效的括号](https://github.com/youngyangyang04/leetcode/blob/master/problems/0020.有效的括号.md)
193194
*[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)
194-
*[0239.滑动窗口最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0239.滑动窗口最大值.md)
195+
*[0150.逆波兰表达式求值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0150.逆波兰表达式求值.md)
195196
*[0347.前K个高频元素](https://github.com/youngyangyang04/leetcode/blob/master/problems/0347.前K个高频元素.md)
197+
* 单调队列
198+
*[0239.滑动窗口最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0239.滑动窗口最大值.md)
199+
* 单调栈
200+
*[0739.每日温度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0739.每日温度.md)
201+
*[0042.接雨水](https://github.com/youngyangyang04/leetcode/blob/master/problems/0042.接雨水.md)
202+
*[0084.柱状图中最大的矩形](https://github.com/youngyangyang04/leetcode/blob/master/problems/0084.柱状图中最大的矩形.md)
196203

197204
* 二叉树经典题目
198205
*[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)
@@ -288,6 +295,7 @@
288295
|[0143.重排链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0143.重排链表.md)|链表|中等|**快慢指针/双指针** 也可以用数组，双向队列模拟，考察链表综合操作的好题|
289296
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)|树|中等|**递归****迭代/栈**|
290297
|[0145.二叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0145.二叉树的后序遍历.md)|树|困难|**递归****迭代/栈**|
298+
|[0150.逆波兰表达式求值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0150.逆波兰表达式求值.md)|栈|中等|**栈**|
291299
|[0151.翻转字符串里的单词](https://github.com/youngyangyang04/leetcode/blob/master/problems/0151.翻转字符串里的单词.md)|字符串|中等|**模拟/双指针**|
292300
|[0155.最小栈](https://github.com/youngyangyang04/leetcode/blob/master/problems/0155.最小栈.md)|栈|简单|**栈**|
293301
|[0199.二叉树的右视图](https://github.com/youngyangyang04/leetcode/blob/master/problems/0199.二叉树的右视图.md)|二叉树|中等|**广度优先遍历/队列**|
@@ -323,6 +331,7 @@
323331
|[0459.重复的子字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0459.重复的子字符串.md)|字符创|简单|**KMP**|
324332
|[0486.预测赢家](https://github.com/youngyangyang04/leetcode/blob/master/problems/0486.预测赢家.md)|动态规划|中等|**递归****记忆递归****动态规划**|
325333
|[0491.递增子序列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0491.递增子序列.md)|深度优先搜索|中等|**深度优先搜索/回溯算法**|
334+
|[0496.下一个更大元素I](https://github.com/youngyangyang04/leetcode/blob/master/problems/0496.下一个更大元素I.md)|栈|中等|**单调栈** 入门题目，但是两个数组还是有点绕的|
326335
|[0501.二叉搜索树中的众数](https://github.com/youngyangyang04/leetcode/blob/master/problems/0501.二叉搜索树中的众数.md)|二叉树|简单|**递归/中序遍历**|
327336
|[0513.找树左下角的值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0513.找树左下角的值.md)|二叉树|中等|**递归****迭代**|
328337
|[0515.在每个树行中找最大值](https://github.com/youngyangyang04/leetcode/blob/master/problems/0515.在每个树行中找最大值.md)|二叉树|简单|**广度优先搜索/队列**|
@@ -343,9 +352,11 @@
343352
|[0701.二叉搜索树中的插入操作](https://github.com/youngyangyang04/leetcode/blob/master/problems/0701.二叉搜索树中的插入操作.md)|树|简单|**递归****迭代**|
344353
|[0705.设计哈希集合](https://github.com/youngyangyang04/leetcode/blob/master/problems/0705.设计哈希集合.md)|哈希表|简单|**模拟**|
345354
|[0707.设计链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0707.设计链表.md)|链表|中等|**模拟**|
355+
|[0739.每日温度](https://github.com/youngyangyang04/leetcode/blob/master/problems/0739.每日温度.md)|栈|中等|**单调栈** 适合单调栈入门|
346356
|[0841.钥匙和房间](https://github.com/youngyangyang04/leetcode/blob/master/problems/0841.钥匙和房间.md)|孤岛问题|中等|**bfs****dfs**|
347357
|[0844.比较含退格的字符串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0844.比较含退格的字符串.md)|字符串|简单|**栈****双指针优化** 使用栈的思路但没有必要使用栈|
348-
|[0977.有序数组的平方](https://github.com/youngyangyang04/leetcode/blob/master/problems/0977.有序数组的平方.md)|数组|中等|**双指针**|
358+
|[0925.长按键入](https://github.com/youngyangyang04/leetcode/blob/master/problems/0925.长按键入.md)|字符串|简单|**双指针/模拟** 是一道模拟类型的题目|
359+
|[0977.有序数组的平方](https://github.com/youngyangyang04/leetcode/blob/master/problems/0977.有序数组的平方.md)|数组|中等|**双指针** 还是比较巧妙的|
349360
|[1002.查找常用字符](https://github.com/youngyangyang04/leetcode/blob/master/problems/1002.查找常用字符.md)|栈|简单|**栈**|
350361
|[1047.删除字符串中的所有相邻重复项](https://github.com/youngyangyang04/leetcode/blob/master/problems/1047.删除字符串中的所有相邻重复项.md)|哈希表|简单|**哈希表/数组**|
351362
|[剑指Offer05.替换空格](https://github.com/youngyangyang04/leetcode/blob/master/problems/剑指Offer05.替换空格.md)|字符串|简单|**双指针**|

‎pics/925.长按键入.png‎

37.4 KB
Loading

‎problems/0084.柱状图中最大的矩形.md‎

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -41,7 +41,6 @@ public:
4141
本题是从栈底到栈头 从小到大，和 接雨水正好反过来。
4242

4343

44-
4544
```
4645
class Solution {
4746
public:
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
2+
##思路
3+
4+
要考率 和 普通数组转成二叉树有什么差别
5+
6+
注意这里是构造平衡二叉搜索树，其实 这里不用强调，因为数组构造二叉树，构成平衡树是自然而然的事情，因为大家默认都是从中间取值，不可能随机取，自找麻烦
7+
8+
一想 这道题目还是有难度的，
9+
10+
一定是递归 分治
11+
12+
循环不变量 的题目列表
13+
14+
注意答案不是唯一的
15+
16+
输入：[-10,-3,0,5,9]
17+
输出：[0,-10,5,null,-3,null,9]
18+
预期结果：[0,-3,9,-10,null,5]
19+
20+
```
21+
class Solution {
22+
private:
23+
TreeNode* traversal(vector<int>& nums, int left, int right) {
24+
if (left > right) return nullptr;
25+
int mid = (left + right) / 2; // 注意越界
26+
TreeNode* root = new TreeNode(nums[mid]);
27+
root->left = traversal(nums, left, mid - 1);
28+
root->right = traversal(nums, mid + 1, right);
29+
return root;
30+
}
31+
public:
32+
TreeNode* sortedArrayToBST(vector<int>& nums) {
33+
TreeNode* root = traversal(nums, 0, nums.size() - 1);
34+
return root;
35+
}
36+
};
37+
```
38+

‎problems/0450.删除二叉搜索树中的节点.md‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -137,6 +137,8 @@ public:
137137
};
138138
```
139139

140+
###普通二叉树的删除方式
141+
140142
这里我在介绍一种通用的删除，普通二叉树的删除方式（没有使用搜索树的特性，遍历整棵树），用交换值的操作来删除目标节点。
141143

142144
代码中目标节点（要删除的节点）被操作了两次：
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
##链接
2+
https://leetcode-cn.com/problems/next-greater-element-i/
3+
4+
##思路
5+
6+
两个数组逻辑还是有点绕
7+
最好还是把所有情况列出来
8+
9+
```
10+
class Solution {
11+
public:
12+
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
13+
stack<int> st;
14+
vector<int> result(nums1.size(), -1);
15+
if (nums1.size() == 0) return result;
16+
17+
unordered_map<int, int> umap; // key:下表元素，value：下表
18+
for (int i = 0; i < nums1.size(); i++) {
19+
umap[nums1[i]] = i;
20+
}
21+
st.push(0);
22+
for (int i = 1; i < nums2.size(); i++) {
23+
while (!st.empty() && nums2[i] > nums2[st.top()]) {
24+
if (umap.count(nums2[st.top()]) > 0) { // 看map里是否存在这个元素
25+
int index = umap[nums2[st.top()]]; // 根据map找到nums2[st.top()] 在 nums1中的下表
26+
result[index] = nums2[i];
27+
}
28+
st.pop();
29+
}
30+
st.push(i);
31+
}
32+
return result;
33+
}
34+
};
35+
```
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
2+
##链接
3+
https://leetcode-cn.com/problems/next-greater-element-ii/
4+
5+
##思路
6+
7+
可以把两个数组拼接在一起
8+
9+
代码性能不行啊，得找找优化的方式
10+
11+
```
12+
class Solution {
13+
public:
14+
vector<int> nextGreaterElements(vector<int>& nums) {
15+
vector<int> nums1(nums.begin(), nums.end());
16+
nums.insert(nums.end(), nums1.begin(), nums1.end());
17+
vector<int> result(nums.size(), -1);
18+
if (nums.size() == 0) return result;
19+
stack<int> st;
20+
st.push(0);
21+
for (int i = 0; i < nums.size(); i++) {
22+
while (!st.empty() && nums[i] > nums[st.top()]) {
23+
result[st.top()] = nums[i];
24+
st.pop();
25+
}
26+
st.push(i);
27+
}
28+
result.resize(nums.size() / 2);
29+
return result;
30+
}
31+
};
32+
```
33+
34+
35+
这样好像能高一些
36+
```
37+
class Solution {
38+
public:
39+
vector<int> nextGreaterElements(vector<int>& nums) {
40+
vector<int> nums1(nums.begin(), nums.end());
41+
nums.resize(nums.size() * 2);
42+
int h = nums.size() / 2;
43+
for (int i = 0; i < nums.size() / 2; i++) {
44+
nums[h + i] = nums[i];
45+
}
46+
//nums.insert(nums.end(), nums1.begin(), nums1.end());
47+
vector<int> result(nums.size(), -1);
48+
if (nums.size() == 0) return result;
49+
stack<int> st;
50+
st.push(0);
51+
for (int i = 0; i < nums.size(); i++) {
52+
while (!st.empty() && nums[i] > nums[st.top()]) {
53+
result[st.top()] = nums[i];
54+
st.pop();
55+
}
56+
st.push(i);
57+
}
58+
result.resize(nums.size() / 2);
59+
return result;
60+
}
61+
};
62+
```

‎problems/0669.修剪二叉搜索树.md‎

Lines changed: 40 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,16 @@
11

2+
##题目链接
3+
4+
https://leetcode-cn.com/problems/trim-a-binary-search-tree/
5+
26
>如果不对递归有深刻的理解，本题有点难
37
8+
>单纯移除一个节点那还不够，要修剪！
9+
410
#669. 修剪二叉搜索树
511

12+
题目链接：https://leetcode-cn.com/problems/trim-a-binary-search-tree/
13+
614
给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。
715

816
![669.修剪二叉搜索树](https://img-blog.csdnimg.cn/20201014173115788.png)
@@ -11,11 +19,13 @@
1119

1220
#思路
1321

14-
相信看到这道题目大家都感觉是一道简单题（事实上leetcode上也表明是简单）。
22+
相信看到这道题目大家都感觉是一道简单题（事实上leetcode上也标明是简单）。
23+
24+
但还真的不简单！
1525

1626
##递归法
1727

18-
直接想法就是：递归处理，然后遇到`root->val < low || root->val > high` 的时候直接return NULL。一波修建，赶紧利落。
28+
直接想法就是：递归处理，然后遇到`root->val < low || root->val > high` 的时候直接return NULL，一波修改，赶紧利落。
1929

2030
不难写出如下代码：
2131

@@ -31,7 +41,7 @@ public:
3141
};
3242
```
3343

34-
**然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树。**
44+
**然而[1, 3]区间在二叉搜索树的中可不是单纯的节点3和左孩子节点0就决定的，还要考虑节点0的右子树**。
3545

3646
我们在重新关注一下第二个示例，如图：
3747

@@ -43,7 +53,7 @@ public:
4353

4454
其实不用重构那么复杂。
4555

46-
在上图中我们发现节点0并不符合区间要求，那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了（就是把元素0减掉），如图：
56+
在上图中我们发现节点0并不符合区间要求，那么将节点0的右孩子 节点2 直接赋给 节点3的左孩子就可以了（就是把节点0从二叉树中移除），如图：
4757

4858
<imgsrc='../pics/669.修剪二叉搜索树1.png'width=600> </img></div>
4959

@@ -52,14 +62,13 @@ public:
5262

5363
* 确定递归函数的参数以及返回值
5464

55-
首先**我们要返回函数参数节点（root）为根节点的树 修剪完之后的 新的根节点**，这里我们为什么需要返回值呢？
65+
这里我们为什么需要返回值呢？
5666

67+
因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是从二叉树中移除节点）的操作。
5768

58-
因为是要遍历整棵树，做修改，其实不需要返回值也可以，我们也可以完成修剪（其实就是要删除节点）的操作。
69+
但是有返回值，更方便，可以通过递归函数的返回值来移除节点。
5970

60-
但是有返回值，更方便，可以通过 这样的赋值语句：`root->left = trimBST(root->left, int low, int high)` 直接删除root的左孩子（如果root的左孩子不在范围内的话）。
61-
62-
**因为`trimBST(root->left, int low, int high)` 将返回当前root左子树（以root->left为根节点的二叉树）修剪完之后的新的根节点。**
71+
这样的做法在[二叉树：搜索树中的插入操作](https://mp.weixin.qq.com/s/lwKkLQcfbCNX2W-5SOeZEA)和[二叉树：搜索树中的删除操作](https://mp.weixin.qq.com/s/-p-Txvch1FFk3ygKLjPAKw)中大家已经了解过了。
6372

6473
代码如下：
6574

@@ -77,7 +86,7 @@ if (root == nullptr ) return nullptr;
7786

7887
* 确定单层递归的逻辑
7988

80-
如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树的头结点。
89+
如果root（当前节点）的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
8190

8291
代码如下：
8392

@@ -88,7 +97,7 @@ if (root->val < low) {
8897
}
8998
```
9099

91-
如果root(当前节点)的元素小于high的，那么应该递归左子树，并返回左子树的头结点。
100+
如果root(当前节点)的元素小于high的，那么应该递归左子树，并返回左子树符合条件的头结点。
92101

93102
代码如下：
94103

@@ -99,33 +108,43 @@ if (root->val > high) {
99108
}
100109
```
101110

102-
接下来要将处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。
111+
接下来要将下一层处理完左子树的结果赋给root->left，处理完右子树的结果赋给root->right。
103112

104113
最后返回root节点，代码如下：
105114

106-
107115
```
108116
root->left = trimBST(root->left, low, high); // root->left接入符合条件的左孩子
109117
root->right = trimBST(root->right, low, high); // root->right接入符合条件的右孩子
110118
return root;
111119
```
112120

113-
此时大家是不是还没发现这个 多余的节点究竟是如何删除的？
121+
此时大家是不是还没发现这多余的节点究竟是如何从二叉树中移除的呢？
122+
123+
在回顾一下上面的代码，针对下图中二叉树的情况：
124+
125+
<imgsrc='../pics/669.修剪二叉搜索树1.png'width=600> </img></div>
126+
127+
如下代码相当于把节点0的右孩子（节点2）返回给上一层，
128+
```
129+
if (root->val < low) {
130+
TreeNode* right = trimBST(root->right, low, high); // 寻找符合区间[low, high]的节点
131+
return right;
132+
}
133+
```
134+
135+
然后如下代码相当于用节点3的左孩子 把下一层返回的 节点0的右孩子（节点2） 接住。
114136

115-
其实就是通过，这两个语句删除的。
116137
```
117138
root->left = trimBST(root->left, low, high);
118-
root->right = trimBST(root->right, low, high);
119139
```
120140

121-
root重新规划root的左右孩子究竟是谁，拿图中示例为例，此时root为节点3，那么trimBST(root->left, low, high)返回的就是节点2，`root->left = trimBST(root->left, low, high);` 相当于把节点0删除了。
141+
此时节点3的右孩子就变成了节点2，将节点0从二叉树中移除了。
122142

123143
最后整体代码如下：
124144

125145
```
126146
class Solution {
127147
public:
128-
// 注意这里是返回该树的头结点
129148
TreeNode* trimBST(TreeNode* root, int low, int high) {
130149
if (root == nullptr ) return nullptr;
131150
if (root->val < low) {
@@ -159,6 +178,8 @@ public:
159178
};
160179
```
161180

181+
只看代码，其实不太好理解节点是符合移除的，这一块大家可以自己在模拟模拟！
182+
162183
##迭代法
163184

164185
因为二叉搜索树的有序性，不需要使用栈模拟递归的过程。
@@ -212,6 +233,6 @@ public:
212233

213234
**如果不对递归有深刻的理解，这道题目还是有难度的！**
214235

215-
本题我依然给出递归法和迭代法，大家只要掌握递归其实就可以了，如果想进一步学习，就把迭代法也写一写。
236+
本题我依然给出递归法和迭代法，初学者掌握递归就可以了，如果想进一步学习，就把迭代法也写一写。
216237

217238
**就酱，如果学到了，就转发给身边需要的同学吧！**

0 commit comments

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