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

Commite0bead0

Browse files
Update
1 parentd1dfccb commite0bead0

File tree

6 files changed

+96
-2
lines changed

6 files changed

+96
-2
lines changed

‎README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -187,6 +187,7 @@
187187
|[0037.解数独](https://github.com/youngyangyang04/leetcode/blob/master/problems/0037.解数独.md)|回溯|困难|**回溯**|
188188
|[0039.组合总和](https://github.com/youngyangyang04/leetcode/blob/master/problems/0039.组合总和.md)|数组/回溯|中等|**回溯**|
189189
|[0040.组合总和II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0040.组合总和II.md)|数组/回溯|中等|**回溯**|
190+
|[0042.接雨水](https://github.com/youngyangyang04/leetcode/blob/master/problems/0042.接雨水.md)|数组/栈/双指针|困难|**双指针****单调栈****动态规划**|
190191
|[0046.全排列](https://github.com/youngyangyang04/leetcode/blob/master/problems/0046.全排列.md)|回溯|中等|**回溯**|
191192
|[0047.全排列II](https://github.com/youngyangyang04/leetcode/blob/master/problems/0047.全排列II.md)|回溯|中等|**回溯**|
192193
|[0051.N皇后](https://github.com/youngyangyang04/leetcode/blob/master/problems/0051.N皇后.md)|回溯|困难|**回溯**|

‎problems/0042.接雨水.md

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
#题目链接
2+
3+
#思路
4+
// 只要一个柱子的
5+
// 暴力的解法 都不好写啊
6+
// 找左面最大的， 找右边最大的，找左右边际的时候容易迷糊。我已开始还找左大于右的。 （还不够）
7+
// 每次记录单条，不要记录整个面积
8+
9+
#C++代码
10+
11+
按照列来
12+
```
13+
class Solution {
14+
public:
15+
int trap(vector<int>& height) {
16+
int sum = 0;
17+
// for (int i = 0; i < height.size(); i++) {
18+
// cout << height[i] << " ";
19+
// }
20+
// cout << endl;
21+
for (int i = 0; i < height.size(); i++) {
22+
if (i == 0 || i == height.size() - 1) continue;
23+
24+
int lIndex, rIndex;
25+
int rValue = height[i];
26+
int lValue = height[i];
27+
for (int r = i + 1; r < height.size(); r++) {
28+
if (height[r] > rValue) {
29+
rValue = height[r];
30+
rIndex = r;
31+
}
32+
}
33+
for (int l = i - 1; l >= 0; l--) {
34+
if (height[l] > lValue) {
35+
lValue = height[l];
36+
lIndex = l;
37+
}
38+
}
39+
int h = min(lValue, rValue) - height[i];
40+
// 我为啥要算 (rIndex - lIndex + 1);就是按照行 按照列 区分不清啊
41+
if (h > 0) sum += h;
42+
}
43+
return sum;
44+
}
45+
};
46+
```

‎problems/0047.全排列II.md

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -7,21 +7,26 @@ https://leetcode-cn.com/problems/permutations-ii/
77

88
这里就涉及到去重了。
99

10+
1011
要注意**全排列是要取树的子节点的，如果是子集问题，就取树上的所有节点。**
1112

1213
很多同学在去重上想不明白，其实很多题解也没有讲清楚，反正代码是能过的，感觉是那么回事，稀里糊涂的先把题目过了。
1314

1415
这个去重为什么很难理解呢，**所谓去重，其实就是使用过的元素不能重复选取。** 这么一说好像很简单！
1516

17+
1618
但是什么又是“使用过”，我们把排列问题抽象为树形结构之后，**“使用过”在这个树形结构上是有两个维度的**，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。
1719

20+
1821
**没有理解这两个层面上的“使用过” 是造成大家没有彻底理解去重的根本原因。**
1922

2023
那么排列问题，既可以在 同一树层上的“使用过”来去重，也可以在同一树枝上的“使用过”来去重！
2124

2225
理解这一本质，很多疑点就迎刃而解了。
2326

24-
首先把示例中的[1,1,2]，抽象为一棵树，然后在同一树层上对nums[i-1]使用过的话，进行去重如图：
27+
**还要强调的是去重一定要对元素经行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。**
28+
29+
首先把示例中的[1,1,2] （为了方便举例，已经排序），抽象为一棵树，然后在同一树层上对nums[i-1]使用过的话，进行去重如图：
2530

2631
<imgsrc='../pics/47.全排列II1.png'width=600> </img></div>
2732

‎problems/0090.子集II.md

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -32,6 +32,8 @@ https://leetcode-cn.com/problems/subsets-ii/
3232

3333
所以要明确我们要去重的是同一树层上的“使用过”。
3434

35+
**还要强调的是去重一定要对元素经行排序，这样我们才方便通过相邻的节点来判断是否重复使用了。**
36+
3537
用示例中的[1, 2, 2] 来举例，如图所示：
3638

3739
<imgsrc='../pics/90.子集II.png'width=600> </img></div>

‎problems/二叉树的理论基础.md

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
2+
二叉树的基础概念
3+
4+
结点的度：一个结点拥有子树的数目称为结点的度
5+
6+
满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树
7+
8+
满二叉树：深度为k，有2^k-1个节点的二叉树
9+
10+
如图：
11+
<imgsrc='https://img-blog.csdnimg.cn/20200806185805576.png'width=600> </img></div>
12+
13+
因为在面试中，面试官会说明给出的二叉树，是一科什么样的二叉树，所以大家有必要了解 最基本的二叉树的类型，这样才能和面试官有效沟通。 如果面试官说给出一个完全二叉树，此时候选人不太清楚完全二叉树是什么样的树的话，就会比较麻烦了，如果这种最基础的概念没有弄清，会让面试官对候选人的印象大打折扣。
14+
15+
所以基本的概念我们要清楚，这样才能在沟通的过程中 表现出扎实的基本功。 对于二叉树，相信左子树，右子树，父节点，叶子节点，二叉树深度等等这些大家都知道了，我这里单独介绍一下（click） 节点的度：一个结点拥有子树的数目称为结点的度。这个概念在我们介绍二叉树的时候经常用到，一些同学在面试中 描述叶子节点，会说 没有左右孩子的节点，这就显得不够专业， 叶子节点 我们称之为 度为0的节点。
16+
17+
那么我们再来介绍几种常见的二叉树类型，（click）什么是满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树， （click）也可以说深度为k，有2^k-1个节点的二叉树
18+
（click ） 也就是如图所示的树称之为满二叉树。
19+
20+
21+
什么是完全二叉树？
22+
23+
叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧
24+
25+
26+
27+
那么什么是完全二叉树呢， 很多同学经常把 完全二叉树 和 满二叉树 混在一起。
28+
29+
（click）来看一下什么是 完全二叉树，叶结点只能出现在最底层的两层，且最底层叶结点均处于次底层叶结点的左侧。也就是最底层的叶子节点 要从左到右来，中间不能断 ，这么说有点抽象，我们来看图
30+
例如
31+
（click） 所以是完全二叉树（click）
32+
（click） 所以也是完全二叉树（click）
33+
（click） 所以不是完全二叉树（click）
34+
35+
那么满二叉树是不是完全二叉树呢，答案是：这个当然是了

‎problems/回溯总结.md

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,10 +8,15 @@
88
* 解数独
99

1010

11+
* 讲一讲去重为什么要排序。
12+
13+
14+
491. 递增子序列
15+
1116

1217
#单层递归
1318

1419
#双层递归
1520

1621

17-
#组合 子集问题，used[i-1] = false 来去重复， 啥问题 used[i-1] = true也是可以的来着
22+
#组合 子集问题，used[i-1] = false 来去重复， 啥问题 used[i-1] = true也是可以的来着 排列问题

0 commit comments

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