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

Commit57d6ce8

Browse files
Update
1 parent71d8678 commit57d6ce8

15 files changed

+215
-33
lines changed

‎README.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,7 @@
107107
*[二叉树：以为使用了递归，其实还隐藏着回溯](https://mp.weixin.qq.com/s/ivLkHzWdhjQQD1rQWe6zWA)
108108
*[二叉树：做了这么多题目了，我的左叶子之和是多少？](https://mp.weixin.qq.com/s/gBAgmmFielojU5Wx3wqFTA)
109109
*[二叉树：我的左下角的值是多少？](https://mp.weixin.qq.com/s/MH2gbLvzQ91jHPKqiub0Nw)
110+
*[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)
110111

111112

112113

@@ -264,6 +265,7 @@
264265
|[0116.填充每个节点的下一个右侧节点指针](https://github.com/youngyangyang04/leetcode/blob/master/problems/0116.填充每个节点的下一个右侧节点指针.md)|二叉树|中等|**广度优先搜索**|
265266
|[0117.填充每个节点的下一个右侧节点指针II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0117.填充每个节点的下一个右侧节点指针II.md)|二叉树|中等|**广度优先搜索**|
266267
|[0131.分割回文串](https://github.com/youngyangyang04/leetcode/blob/master/problems/0131.分割回文串.md)|回溯|中等|**回溯**|
268+
|[0141.环形链表](https://github.com/youngyangyang04/leetcode/blob/master/problems/0141.环形链表.md)|链表|简单|**快慢指针/双指针**|
267269
|[0142.环形链表II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0142.环形链表II.md)|链表|中等|**快慢指针/双指针**|
268270
|[0144.二叉树的前序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0144.二叉树的前序遍历.md)|树|中等|**递归****迭代/栈**|
269271
|[0145.二叉树的后序遍历](https://github.com/youngyangyang04/leetcode/blob/master/problems/0145.二叉树的后序遍历.md)|树|困难|**递归****迭代/栈**|

‎pics/42.接雨水1.png

84.4 KB
Loading

‎pics/42.接雨水2.png

83.7 KB
Loading

‎pics/42.接雨水3.png

46.4 KB
Loading

‎pics/654.最大二叉树.png

25.9 KB
Loading

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

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -97,4 +97,8 @@ public:
9797
};
9898
```
9999

100+
#拓展
101+
102+
请问为什么 getCombinations(const string& digits, int index, const string& s)函数里的string& s 前要加const，不加的报错
103+
100104
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎problems/0042.接雨水.md

Lines changed: 81 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -6,41 +6,103 @@
66
// 找左面最大的， 找右边最大的，找左右边际的时候容易迷糊。我已开始还找左大于右的。 （还不够）
77
// 每次记录单条，不要记录整个面积
88

9-
#C++代码
9+
##暴力解法
10+
11+
这道题目暴力解法并不简单，我们来看一下思路。
12+
13+
首先要明确，要按照行来计算，还是按照列来计算。如图所示：
14+
15+
<imgsrc='../pics/42.接雨水2.png'width=600> </img></div>
16+
17+
<imgsrc='../pics/42.接雨水1.png'width=600> </img></div>
18+
19+
一些同学在实现暴力解法的时候，很容易一会按照行来计算一会按照列来计算，这样就会越写越乱。
20+
21+
我个人倾向于按照列来计算，比较容易理解，接下来看一下按照列如何计算。
22+
23+
首先，**如果按照列来计算的话，宽度一定是1了，我们再把每一列的雨水的高度求出来就可以了。**
24+
25+
可以看出每一列雨水的高度，取决于，该列 左侧最高的柱子和右侧最高的柱子中最矮的那个柱子的高度。
26+
27+
这句话可以有点绕，来举一个理解，例如求列4的雨水高度，如图：
28+
29+
<imgsrc='../pics/42.接雨水3.png'width=600> </img></div>
30+
31+
列4 左侧最高的柱子是列3，高度为2（以下用lHeight表示）。
32+
33+
列4 右侧最高的柱子是列7，高度为3（以下用rHeight表示）。
34+
35+
列4 柱子的高度为1（以下用height表示）
36+
37+
那么列4的雨水高度为 列3和列7的高度最小值减列4高度，即： min(lHeight, rHeight) - height。
38+
39+
列4的雨水高度求出来了，宽度为1，相乘就是列4的雨水体积了。
40+
41+
此时求出了列4的雨水体积。
42+
43+
一样的方法，只要从头遍历一遍所有的列，然后求出每一列雨水的体积，相加之后就是总雨水的体积了。
44+
45+
首先从头遍历所有的列，并且**要注意第一个柱子和最后一个柱子不接雨水**，代码如下：
46+
```
47+
for (int i = 0; i < height.size(); i++) {
48+
// 第一个柱子和最后一个柱子不接雨水
49+
if (i == 0 || i == height.size() - 1) continue;
50+
}
51+
```
52+
53+
在for循环中求左右两边最高柱子，代码如下：
54+
55+
```
56+
int rHeight = height[i]; // 记录右边柱子的最高高度
57+
int lHeight = height[i]; // 记录左边柱子的最高高度
58+
for (int r = i + 1; r < height.size(); r++) {
59+
if (height[r] > rHeight) rHeight = height[r];
60+
}
61+
for (int l = i - 1; l >= 0; l--) {
62+
if (height[l] > lHeight) lHeight = height[l];
63+
}
64+
```
65+
66+
最后，计算该列的雨水高度，代码如下：
67+
68+
```
69+
int h = min(lHeight, rHeight) - height[i];
70+
if (h > 0) sum += h; // 注意只有h大于零的时候，在统计到总和中
71+
```
72+
73+
整体代码如下：
1074

11-
按照列来
1275
```
1376
class Solution {
1477
public:
1578
int trap(vector<int>& height) {
1679
int sum = 0;
17-
// for (int i = 0; i < height.size(); i++) {
18-
// cout << height[i] << " ";
19-
// }
20-
// cout << endl;
2180
for (int i = 0; i < height.size(); i++) {
81+
// 第一个柱子和最后一个柱子不接雨水
2282
if (i == 0 || i == height.size() - 1) continue;
2383
24-
int lIndex, rIndex;
25-
int rValue = height[i];
26-
int lValue = height[i];
84+
int rHeight = height[i]; // 记录右边柱子的最高高度
85+
int lHeight = height[i]; // 记录左边柱子的最高高度
2786
for (int r = i + 1; r < height.size(); r++) {
28-
if (height[r] > rValue) {
29-
rValue = height[r];
30-
rIndex = r;
31-
}
87+
if (height[r] > rHeight) rHeight = height[r];
3288
}
3389
for (int l = i - 1; l >= 0; l--) {
34-
if (height[l] > lValue) {
35-
lValue = height[l];
36-
lIndex = l;
37-
}
90+
if (height[l] > lHeight) lHeight = height[l];
3891
}
39-
int h = min(lValue, rValue) - height[i];
40-
// 我为啥要算 (rIndex - lIndex + 1);就是按照行 按照列 区分不清啊
92+
int h = min(lHeight, rHeight) - height[i];
4193
if (h > 0) sum += h;
4294
}
4395
return sum;
4496
}
4597
};
4698
```
99+
100+
因为每次遍历列的时候，还要向两边寻找最高的列，所以时间复杂度为O(n^2)。
101+
空间复杂度为O(1)。
102+
103+
104+
#单调栈
105+
106+
单调栈究竟如何做呢，得画一个图，不太好理解
107+
108+
按照列来算的，遇到相同的怎么办。

‎problems/0141.环形链表.md

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,11 @@ fast和slow各自再走一步， fast和slow就相遇了
1919

2020
这是因为fast是走两步，slow是走一步，**其实相对于slow来说，fast是一个节点一个节点的靠近slow的**，所以fast一定可以和slow重合。
2121

22+
动画如下：
23+
24+
25+
<imgsrc='../video/141.环形链表.gif'width=600> </img></div>
26+
2227

2328
##C++代码如下
2429

‎problems/0142.环形链表II.md

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,11 @@ fast和slow各自再走一步， fast和slow就相遇了
4343

4444
这是因为fast是走两步，slow是走一步，**其实相对于slow来说，fast是一个节点一个节点的靠近slow的**，所以fast一定可以和slow重合。
4545

46+
动画如下：
47+
48+
49+
<videosrc='../video/142.环形链表II1.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
50+
4651

4752
##如果有环，如何找到这个环的入口
4853

@@ -83,6 +88,11 @@ fast指针走过的节点数：` x + y + n (y + z)`，n为fast指针在环内走
8388

8489
让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。
8590

91+
动画如下：
92+
93+
<videosrc='../video/142.环形链表II.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
94+
95+
8696
那么 n如果大于1是什么情况呢，就是fast指针在环形转n圈之后才遇到 slow指针。
8797

8898
其实这种情况和n为1的时候 效果是一样的，一样可以通过这个方法找到 环形的入口节点，只不过，index1 指针在环里 多转了(n-1)圈，然后再遇到index2，相遇点依然是环形的入口节点。

‎problems/0654.最大二叉树.md

Lines changed: 113 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1,19 +1,35 @@
11
##题目地址
22
https://leetcode-cn.com/problems/maximum-binary-tree/
33

4+
>用数组构建二叉树都是一样的套路
5+
6+
#654.最大二叉树
7+
8+
给定一个不含重复元素的整数数组。一个以此数组构建的最大二叉树定义如下：
9+
10+
* 二叉树的根是数组中的最大元素。
11+
* 左子树是通过数组中最大值左边部分构造出的最大二叉树。
12+
* 右子树是通过数组中最大值右边部分构造出的最大二叉树。
13+
14+
通过给定的数组构建最大二叉树，并且输出这个树的根节点。
15+
16+
示例 ：
17+
18+
<imgsrc='../pics/654.最大二叉树.png'width=600> </img></div>
19+
20+
提示：
21+
22+
给定的数组的大小在[1, 1000] 之间。
23+
424
##思路
525

626
最大二叉树的构建过程如下：
727

8-
<videosrc='../video/654.最大二叉树.mp4'controls='controls'width='640'height='320'autoplay='autoplay'> Your browser does not support the video tag.</video></div>
28+
<imgsrc='../video/654.最大二叉树.gif'width=600> </img></div>
929

10-
典型的递归问题，依然按照递归三部曲来分析：
30+
构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。
1131

12-
* 确定递归函数的参数和返回值
13-
* 确定终止条件
14-
* 确定单层递归的逻辑
15-
16-
###确定递归函数的参数和返回值
32+
* 确定递归函数的参数和返回值
1733

1834
参数就是传入的是存放元素的数组，返回该数组构造的二叉树的头结点，返回类型是指向节点的指针。
1935

@@ -23,9 +39,11 @@ https://leetcode-cn.com/problems/maximum-binary-tree/
2339
TreeNode* constructMaximumBinaryTree(vector<int>& nums)
2440
2541
```
26-
###确定终止条件
42+
* 确定终止条件
43+
44+
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了叶子节点了。
2745

28-
题目中说了输入的数组大小一定是大于等于1的，所以我们不用考虑小于1的情况，那么当递归遍历的时候，如果传入的数组大小为1，说明遍历到了具体节点了，那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
46+
那么应该定义一个新的节点，并把这个数组的数值赋给新的节点，然后返回这个节点。 这表示一个数组大小是1的时候，构造了一个新的节点，并返回。
2947

3048
代码如下：
3149

@@ -36,11 +54,12 @@ if (nums.size() == 1) {
3654
    return node;
3755
}
3856
```
39-
###确定单层递归的逻辑
57+
58+
* 确定单层递归的逻辑
4059

4160
这里有三步工作
4261

43-
1. 先要找到数组中最大的值和对应的下表，最大的值就是根节点
62+
1. 先要找到数组中最大的值和对应的下表，最大的值构造根节点，下表用来下一步分割数组。
4463

4564
代码如下：
4665
```
@@ -82,8 +101,6 @@ if (maxValueIndex < (nums.size() - 1)) {
82101
```
83102
这样我们就分析完了，整体代码如下：（详细注释）
84103

85-
##C++代码
86-
87104
```
88105
class Solution {
89106
public:
@@ -105,7 +122,7 @@ public:
105122
node->val = maxValue;
106123
// 最大值所在的下表左区间 构造左子树
107124
if (maxValueIndex > 0) {
108-
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
125+
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
109126
node->left = constructMaximumBinaryTree(newVec);
110127
}
111128
// 最大值所在的下表右区间 构造右子树
@@ -117,4 +134,86 @@ public:
117134
}
118135
};
119136
```
137+
138+
以上代码比较冗余，效率也不高，每次还要切割的时候每次都要定义新的vector（也就是数组），但逻辑比较清晰。
139+
140+
和文章[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg)中一样的优化思路，就是每次分隔不用定义新的数组，而是通过下表索引直接在原数组上操作。
141+
142+
优化后代码如下：
143+
144+
```
145+
class Solution {
146+
private:
147+
// 在左闭右开区间[left, right)，构造二叉树
148+
TreeNode* traversal(vector<int>& nums, int left, int right) {
149+
if (left >= right) return nullptr;
150+
151+
// 分割点下表：maxValueIndex
152+
int maxValueIndex = left;
153+
for (int i = left + 1; i < right; ++i) {
154+
if (nums[i] > nums[maxValueIndex]) maxValueIndex = i;
155+
}
156+
157+
TreeNode* root = new TreeNode(nums[maxValueIndex]);
158+
159+
// 左闭右开：[left, maxValueIndex)
160+
root->left = traversal(nums, left, maxValueIndex);
161+
162+
// 左闭右开：[maxValueIndex + 1, right)
163+
root->right = traversal(nums, maxValueIndex + 1, right);
164+
165+
return root;
166+
}
167+
public:
168+
TreeNode* constructMaximumBinaryTree(vector<int>& nums) {
169+
return traversal(nums, 0, nums.size());
170+
}
171+
};
172+
```
173+
174+
#拓展
175+
176+
可以发现上面的代码看上去简洁一些，**主要是因为第二版其实是允许空节点进入递归，所以不用在递归的时候加判断节点是否为空**
177+
178+
第一版递归过程：（加了if判断，为了不让空节点进入递归）
179+
```
180+
181+
if (maxValueIndex > 0) { // 这里加了判断是为了不让空节点进入递归
182+
vector<int> newVec(nums.begin(), nums.begin() + maxValueIndex);
183+
node->left = constructMaximumBinaryTree(newVec);
184+
}
185+
186+
if (maxValueIndex < (nums.size() - 1)) { // 这里加了判断是为了不让空节点进入递归
187+
vector<int> newVec(nums.begin() + maxValueIndex + 1, nums.end());
188+
node->right = constructMaximumBinaryTree(newVec);
189+
}
190+
```
191+
192+
第二版递归过程： （如下代码就没有加if判断）
193+
194+
```
195+
root->left = traversal(nums, left, maxValueIndex);
196+
197+
root->right = traversal(nums, maxValueIndex + 1, right);
198+
```
199+
200+
第二版代码是允许空节点进入递归，所以没有加if判断，当然终止条件也要有相应的改变。
201+
202+
第一版终止条件，是遇到叶子节点就终止，因为空节点不会进入递归。
203+
204+
第二版相应的终止条件，是遇到空节点，也就是数组区间为0，就终止了。
205+
206+
207+
#总结
208+
209+
这道题目其实和[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg) 是一个思路，比[二叉树：构造二叉树登场！](https://mp.weixin.qq.com/s/7r66ap2s-shvVvlZxo59xg) 还简单一些。
210+
211+
**注意类似用数组构造二叉树的题目，每次分隔尽量不要定义新的数组，而是通过下表索引直接在原数组上操作，这样可以节约时间和空间上的开销。**
212+
213+
一些同学也会疑惑，什么时候递归函数前面加if，什么时候不加if，这个问题我在最后也给出了解释。
214+
215+
其实就是不同代码风格的实现，**一般情况来说：如果让空节点（空指针）进入递归，就不加if，如果不让空节点进入递归，就加if限制一下， 终止条件也会相应的调整。**
216+
217+
218+
120219
>更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

‎video/141.环形链表.gif

1.82 MB
Loading

‎video/141.环形链表.mp4

182 KB
Binary file not shown.

‎video/142.环形链表II.mp4

1.61 MB
Binary file not shown.

‎video/142.环形链表II1.mp4

1.18 MB
Binary file not shown.

‎video/654.最大二叉树.gif

724 KB
Loading

0 commit comments

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