Skip to content

Commit fe212cf

Browse files
youngyangyang04youngyangyang04
committed
Update
1 parent e08fd0e commit fe212cf

20 files changed

+284
-91
lines changed

‎README.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -169,6 +169,10 @@
169169
* [回溯算法：解数独](https://mp.weixin.qq.com/s/eWE9TapVwm77yW9Q81xSZQ)
170170
* [一篇总结带你彻底搞透回溯算法！](https://mp.weixin.qq.com/s/r73thpBnK1tXndFDtlsdCQ)
171171

172+
* 贪心算法
173+
* [关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg)
174+
* [贪心算法：分发饼干](https://mp.weixin.qq.com/s/YSuLIAYyRGlyxbp9BNC1uw)
175+
172176

173177
（持续更新中....）
174178

‎pics/.DS_Store

6 KB
Binary file not shown.

‎pics/222.完全二叉树的节点个数.png

108 KB
Loading

‎pics/222.完全二叉树的节点个数1.png

108 KB
Loading

‎pics/491. 递增子序列1.jpg

-2.59 MB
Binary file not shown.

‎pics/55.跳跃游戏.png

5.31 KB
Loading

‎pics/90_子集 II.png

-43.6 KB
Binary file not shown.

‎problems/0037.解数独.md

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,7 @@
11
> 解数独，理解二维递归是关键
22
3+
如果对回溯法理论还不清楚的同学，可以先看这个视频[视频来了！！带你学透回溯算法（理论篇）](https://mp.weixin.qq.com/s/wDd5azGIYWjbU0fdua_qBg)
4+
35
# 37. 解数独
46

57
题目地址：https://leetcode-cn.com/problems/sudoku-solver/
@@ -207,3 +209,7 @@ public:
207209
208210
如果一直跟住「代码随想录」的节奏，你会发现自己进步飞快，从思维方式到刷题习惯，都会有质的飞跃，「代码随想录」绝对值得推荐给身边的同学朋友们！
209211
212+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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)，关注后就会发现和「代码随想录」相见恨晚！**
213+
214+
**如果感觉对你有帮助，不要吝啬给一个👍吧！**
215+

‎problems/0046.全排列.md

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11

22
> 开始排列问题
3-
> 通知：现在已经将所有历史文章，汇总到一起，有一个整体的目录，方便录友们从前面系列开始卡了，就在公众号左下角「算法汇总」，大家去瞅瞅哈
43
54
# 46.全排列
65

@@ -32,7 +31,7 @@
3231

3332
我以[1,2,3]为例，抽象成树形结构如下：
3433

35-
<img src='../pics/46.全排列.png' width=600> </img></div>
34+
![46.全排列](https://img-blog.csdnimg.cn/20201124200941742.png)
3635

3736
## 回溯三部曲
3837

@@ -44,7 +43,7 @@
4443

4544
但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:
4645

47-
<img src='../pics/46.全排列.png' width=600> </img></div>
46+
![46.全排列](https://img-blog.csdnimg.cn/20201124200941742.png)
4847

4948
代码如下：
5049

@@ -56,7 +55,7 @@ void backtracking (vector<int>& nums, vector<bool>& used)
5655

5756
* 递归终止条件
5857

59-
<img src='../pics/46.全排列.png' width=600> </img></div>
58+
![46.全排列](https://img-blog.csdnimg.cn/20201124200941742.png)
6059

6160
可以看出叶子节点，就是收割结果的地方。
6261

@@ -140,3 +139,7 @@ public:
140139

141140
就酱，如果感觉「代码随想录」诚意满满，就帮Carl宣传一波吧！
142141

142+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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)，关注后就会发现和「代码随想录」相见恨晚！**
143+
144+
**如果感觉对你有帮助，不要吝啬给一个👍吧！**
145+

‎problems/0047.全排列II.md

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,5 @@
11

22
> 排列也要去重了
3-
> 通知：很多录友都反馈之前看「算法汇总」的目录要一直往下拉，很麻烦，这次Carl将所有历史文章汇总到一篇文章中，有一个整体的目录，方便录友们从前面系列开始卡了，依然在公众号左下角[「算法汇总」](https://mp.weixin.qq.com/s/weyitJcVHBgFtSc19cbPdw)，这里会持续更新，大家快去瞅瞅哈
43
54
# 47.全排列 II
65

@@ -37,7 +36,7 @@
3736

3837
我以示例中的 [1,1,2]为例 （为了方便举例，已经排序）抽象为一棵树，去重过程如图：
3938

40-
<img src='../pics/47.全排列II1.png' width=600> </img></div>
39+
![47.全排列II1](https://img-blog.csdnimg.cn/20201124201331223.png)
4140

4241
图中我们对同一树层，前一位（也就是nums[i-1]）如果使用过，那么就进行去重。
4342

@@ -114,11 +113,11 @@ if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
114113

115114
树层上去重(used[i - 1] == false)，的树形结构如下：
116115

117-
<img src='../pics/47.全排列II2.png' width=600> </img></div>
116+
![47.全排列II2](https://img-blog.csdnimg.cn/20201124201406192.png)
118117

119118
树枝上去重（used[i - 1] == true）的树型结构如下：
120119

121-
<img src='../pics/47.全排列II3.png' width=600> </img></div>
120+
![47.全排列II3](https://img-blog.csdnimg.cn/20201124201431571.png)
122121

123122
大家应该很清晰的看到，树层上对前一位去重非常彻底，效率很高，树枝上对前一位去重虽然最后可以得到答案，但是做了很多无用搜索。
124123

@@ -145,3 +144,7 @@ if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == true) {
145144

146145
就酱，很多录友表示和「代码随想录」相见恨晚，那么大家帮忙多多宣传，让更多的同学知道这里，感谢啦！
147146

147+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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)，关注后就会发现和「代码随想录」相见恨晚！**
148+
149+
**如果感觉对你有帮助，不要吝啬给一个👍吧！**
150+

‎problems/0051.N皇后.md

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -228,3 +228,7 @@ public:
228228

229229
就酱，如果感觉「代码随想录」干货满满，就分享给身边的朋友同学吧，他们可能也需要！
230230

231+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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)，关注后就会发现和「代码随想录」相见恨晚！**
232+
233+
**如果感觉对你有帮助，不要吝啬给一个👍吧！**
234+

‎problems/0055.跳跃游戏.md

Lines changed: 36 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -1,25 +1,49 @@
11
## 链接
22
https://leetcode-cn.com/problems/jump-game/
33

4-
## 思路
4+
# 55. 跳跃游戏
55

6-
其实贪心和动态规划很容易混在一起，在面试中，我们应该本着能用贪心就用贪心，贪心解决不了再考虑用动态规划。 毕竟贪心更容易理解，并快速写出代码。
6+
给定一个非负整数数组，你最初位于数组的第一个位置。
7+
8+
数组中的每个元素代表你在该位置可以跳跃的最大长度。
9+
10+
判断你是否能够到达最后一个位置。
11+
12+
示例 1:
13+
输入: [2,3,1,1,4]
14+
输出: true
15+
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
16+
17+
示例 2:
18+
输入: [3,2,1,0,4]
19+
输出: false
20+
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
21+
22+
23+
## 思路
724

825
刚看到本题一开始可能想：当前位置元素如果是3，我究竟是跳一步呢，还是两步呢，还是三步呢，究竟跳几步才是最优呢？
926

10-
其实如果本题是要求只能跳元素数值大小的个数，不能多也不能少，问是否达到终点，那么一定要用动态规划了。
27+
可以转变一下思路，不一样非要明确一次究竟跳几步，每次取最大的跳跃步数，这个就是可以跳跃的覆盖范围。
28+
29+
这个范围内，已经是可以跳过来的，别管是怎么跳的，反正一定可以跳过来。
30+
31+
**那么就是这个跳跃覆盖范围究竟可不可以覆盖到终点！**
32+
33+
每次移动取最大跳跃步数，得到最大的覆盖范围，每移动一个单位，就更新最大覆盖范围。
34+
35+
**局部最优解：每次取最大跳跃步数（取最大覆盖范围），整体最优解：最后得到就是整体最大覆盖范围，看是否能到终点**。
1136

12-
但本题其实我们就看跳到的范围能否覆盖终点，就可以了。
1337

1438
那么我们每次取最大的覆盖范围，看最后能否覆盖终点。
1539

1640
如图：
1741

18-
<img src='../pics/55.跳跃游戏.png' width=600> </img></div>
42+
![55.跳跃游戏](https://img-blog.csdnimg.cn/20201124154758229.png)
1943

20-
那么i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值的补充，让i继续移动下去。
44+
i每次移动只能在cover的范围内移动，每移动一个元素，cover得到该元素数值（新的覆盖范围）的补充，让i继续移动下去。
2145

22-
而cover每次只取 得到该元素数值补充后的范围 和 cover本身范围 的最大值。
46+
而cover每次只取 max(该元素数值补充后的范围, cover本身范围)。
2347

2448
如果cover大于等于了终点下表，直接return true就可以了。
2549

@@ -39,3 +63,8 @@ public:
3963
}
4064
};
4165
```
66+
# 总结
67+
68+
69+
70+
其实贪心和动态规划很容易混在一起，在面试中，我们应该本着能用贪心就用贪心，贪心解决不了再考虑用动态规划。 毕竟贪心更容易理解，并快速写出代码。

‎problems/0090.子集II.md

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,7 @@
3434

3535
用示例中的[1, 2, 2] 来举例，如图所示： （**注意去重需要先对集合排序**）
3636

37-
<img src='../pics/90.子集II.png' width=600> </img></div>
37+
![90.子集II](https://img-blog.csdnimg.cn/20201124195411977.png)
3838

3939
从图中可以看出，同一树层上重复取2 就要过滤掉，同一树枝上就可以重复取2，因为同一树枝上元素的集合才是唯一子集！
4040

@@ -114,16 +114,19 @@ public:
114114

115115
其实这道题目的知识点，我们之前都讲过了，如果之前讲过的子集问题和去重问题都掌握的好，这道题目应该分分钟AC。
116116

117+
当然本题去重的逻辑，也可以这么写
117118

118-
这道题目去重的逻辑，也可以这么写
119119
```
120120
if (i > startIndex && nums[i] == nums[i - 1] ) {
121-
continue;
122-
}
121+
continue;
122+
}
123123
```
124124

125125
**就酱，如果感觉融会贯通了，就把「代码随想录」介绍给自己的同学朋友吧，也许他们也需要！**
126126

127-
> 我是[程序员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)，期待你的关注！
127+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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/20201124161234338.png)，关注后就会发现和「代码随想录」相见恨晚！**
128+
129+
**如果感觉题解对你有帮助，不要吝啬给一个👍吧！**
130+
128131

129132

‎problems/0222.完全二叉树的节点个数.md

Lines changed: 67 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,12 +1,8 @@
1-
## 题目地址
2-
https://leetcode-cn.com/problems/count-complete-tree-nodes/
3-
4-
> 今天是中秋&&国庆，所以来一道二叉树简单题吧
5-
6-
如果之前两篇[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)， [二叉树：看看这些树的最小深度](https://mp.weixin.qq.com/s/BH8-gPC3_QlqICDg7rGSGA)都认真看了的话，这道题目可以分分钟刷掉了哈哈。
71

82
# 222.完全二叉树的节点个数
93

4+
题目地址：https://leetcode-cn.com/problems/count-complete-tree-nodes/
5+
106
给出一个完全二叉树，求出该树的节点个数。
117

128
示例:
@@ -15,17 +11,17 @@ https://leetcode-cn.com/problems/count-complete-tree-nodes/
1511

1612
# 思路
1713

18-
这道题目其实没有必要强调是完全二叉树，就是求二叉树节点的个数。
14+
本篇给出按照普通二叉树的求法以及利用完全二叉树性质的求法。
1915

20-
![image.png](https://pic.leetcode-cn.com/168a07d49c103ada57202f5ad60a2d51f3d0e0ea5c8399e1caed81b709153c85-image.png)
16+
## 普通二叉树
2117

22-
依然可以使用递归法和迭代法来解决。
18+
首先按照普通二叉树的逻辑来求。
2319

2420
这道题目的递归法和求二叉树的深度写法类似， 而迭代法，[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)遍历模板稍稍修改一下，记录遍历的节点数量就可以了。
2521

2622
递归遍历的顺序依然是后序（左右中）。
2723

28-
## 递归
24+
### 递归
2925

3026
如果对求二叉树深度还不熟悉的话，看这篇：[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)。
3127

@@ -49,15 +45,16 @@ if (cur == NULL) return 0;
4945
代码如下：
5046

5147
```
52-
int leftNum = getNodesNum(cur->left); // 左
53-
int rightNum = getNodesNum(cur->right); // 右
54-
int treeNum = leftNum + rightNum + 1; // 中
55-
return treeNum;
48+
int leftNum = getNodesNum(cur->left); // 左
49+
int rightNum = getNodesNum(cur->right); // 右
50+
int treeNum = leftNum + rightNum + 1; // 中
51+
return treeNum;
5652
```
5753

5854
所以整体C++代码如下：
5955

6056
```
57+
// 版本一
6158
class Solution {
6259
private:
6360
int getNodesNum(TreeNode* cur) {
@@ -76,17 +73,23 @@ public:
7673

7774
代码精简之后C++代码如下：
7875
```
76+
// 版本二
7977
class Solution {
8078
public:
8179
int countNodes(TreeNode* root) {
8280
if (root == NULL) return 0;
8381
return 1 + countNodes(root->left) + countNodes(root->right);
8482
}
8583
};
86-
8784
```
8885

89-
## 迭代法
86+
时间复杂度：O(n)
87+
空间复杂度：O(logn)，算上了递归系统栈占用的空间
88+
89+
**网上基本都是这个精简的代码版本，其实不建议大家照着这个来写，代码确实精简，但隐藏了一些内容，连遍历的顺序都看不出来，所以初学者建议学习版本一的代码，稳稳的打基础**。
90+
91+
92+
### 迭代法
9093

9194
如果对求二叉树层序遍历还不熟悉的话，看这篇：[二叉树：层序遍历登场！](https://mp.weixin.qq.com/s/Gb3BjakIKGNpup2jYtTzog)。
9295

@@ -113,15 +116,57 @@ public:
113116
}
114117
};
115118
```
119+
时间复杂度：O(n)
120+
空间复杂度：O(n)
121+
122+
## 完全二叉树
123+
124+
以上方法都是按照普通二叉树来做的，对于完全二叉树特性不了解的同学可以看这篇 [关于二叉树，你该了解这些！](https://mp.weixin.qq.com/s/_ymfWYvTNd2GvWvC5HOE4A)，这篇详细介绍了各种二叉树的特性。
125+
126+
完全二叉树只有两种情况，情况一：就是满二叉树，情况二：最后一层叶子节点没有满。
116127

117-
# 总结
128+
对于情况一，可以直接用 2^树深度 - 1 来计算，注意这里根节点深度为1。
118129

119-
这道题目的解法其实我们在[二叉树：看看这些树的最大深度](https://mp.weixin.qq.com/s/guKwV-gSNbA1CcbvkMtHBg)和 [二叉树：看看这些树的最小深度](https://mp.weixin.qq.com/s/BH8-gPC3_QlqICDg7rGSGA)都有提到过了。
130+
对于情况二，分别递归左孩子，和右孩子，递归到某一深度一定会有左孩子或者右孩子为满二叉树，然后依然可以按照情况1来计算。
131+
132+
完全二叉树（一）如图：
133+
![222.完全二叉树的节点个数](https://img-blog.csdnimg.cn/20201124092543662.png)
134+
135+
完全二叉树（二）如图：
136+
![222.完全二叉树的节点个数1](https://img-blog.csdnimg.cn/20201124092634138.png)
137+
138+
可以看出如果整个树不是满二叉树，就递归其左右孩子，直到遇到满二叉树为止，用公式计算这个子树（满二叉树）的节点数量。
139+
140+
C++代码如下：
141+
142+
```C++
143+
class Solution {
144+
public:
145+
int countNodes(TreeNode* root) {
146+
if (root == nullptr) return 0;
147+
TreeNode* left = root->left;
148+
TreeNode* right = root->right;
149+
int leftHeight = 0, rightHeight = 0; // 这里初始为0是有目的的，为了下面求指数方便
150+
while (left) { // 求左子树深度
151+
left = left->left;
152+
leftHeight++;
153+
}
154+
while (right) { // 求右子树深度
155+
right = right->right;
156+
rightHeight++;
157+
}
158+
if (leftHeight == rightHeight) {
159+
return (2 << leftHeight) - 1; // 注意(2<<1) 相当于2^2，所以leftHeight初始为0
160+
}
161+
return countNodes(root->left) + countNodes(root->right) + 1;
162+
}
163+
};
164+
```
120165
121-
一样的分析套路，代码也差不多，估计此时大家最这一类求二叉树节点数量以及求深度应该非常熟练了。
166+
时间复杂度：O(logn * logn)
167+
空间复杂度：O(logn)
122168
123-
没有做过这道题目的同学可以愉快的刷了它了。
169+
> **我是[程序员Carl](https://github.com/youngyangyang04)，可以找我[组队刷题](https://img-blog.csdnimg.cn/20201115103410182.png)，也可以在[B站上找到我](https://space.bilibili.com/525438321)，本文[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)，关注后就会发现和「代码随想录」相见恨晚！**
124170
125-
最后祝大家中秋&国庆节日愉快哈！
171+
**如果感觉对你有帮助，不要吝啬给一个👍吧！**
126172
127-
> 更多算法干货文章持续更新，可以微信搜索「代码随想录」第一时间围观，关注后，回复「Java」「C++」 「python」「简历模板」「数据结构与算法」等等，就可以获得我多年整理的学习资料。

0 commit comments

Comments
 (0)