Skip to content

Commit f7771e6

Browse files
youngyangyang04youngyangyang04
committed
添加贪心算法
1 parent 2fec084 commit f7771e6

File tree

2 files changed

+259
-0
lines changed

2 files changed

+259
-0
lines changed

‎problems/贪心算法总结篇.md

Lines changed: 157 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,157 @@
1+
<p align='center'>
2+
<img src="https://img-blog.csdnimg.cn/20201215214102642.png" width=400 >
3+
</p>
4+
<p align="center">
5+
<a href="https://github.com/youngyangyang04/leetcode-master"><img src="https://img.shields.io/badge/Github-leetcode--master-lightgrey" alt=""></a>
6+
<a href="https://img-blog.csdnimg.cn/20201115103410182.png"><img src="https://img.shields.io/badge/刷题-微信群-green" alt=""></a>
7+
<a href="https://img-blog.csdnimg.cn/20201210231711160.png"><img src="https://img.shields.io/badge/公众号-代码随想录-brightgreen" alt=""></a>
8+
<a href="https://space.bilibili.com/525438321"><img src="https://img.shields.io/badge/B站-代码随想录-orange" alt=""></a>
9+
<a href="https://www.zhihu.com/people/sun-xiu-yang-64"><img src="https://img.shields.io/badge/知乎-代码随想录-blue" alt=""></a>
10+
<a href="https://www.toutiao.com/c/user/60356270818/#mid=1633692776932365"><img src="https://img.shields.io/badge/头条-代码随想录-red" alt=""></a>
11+
</p>
12+
13+
我刚刚开始讲解贪心系列的时候就说了，贪心系列并不打算严格的从简单到困难这么个顺序来讲解。
14+
15+
因为贪心的简单题可能往往过于简单甚至感觉不到贪心，如果我连续几天讲解简单的贪心，估计录友们一定会不耐烦了，会感觉贪心有啥好学的。
16+
17+
但贪心的难题又真的有点难，所以我是简单困难交错着讲的，这样大家就感觉难度适中，而且贪心也没有什么框架和套路，所以对刷题顺序要求没有那么高。
18+
19+
但在贪心系列，我发的题目难度会整体呈现一个阶梯状上升，细心的录友们应该有所体会。
20+
21+
在刚刚讲过的回溯系列中，大家可以发现我是严格按照框架难度顺序循序渐进讲解的，**和贪心又不一样，因为回溯法如果题目顺序没选好，刷题效果会非常差！**
22+
23+
同样回溯系列也不允许简单困难交替着来，因为前后题目都是有因果关系的，**相信跟着刷过回溯系列的录友们都会明白我的良苦用心，哈哈**。
24+
25+
**每个系列都有每个系列的特点，我都会根据特点有所调整，大家看我每天的推送的题目，都不是随便找一个到就推送的，都是先有整体规划，然后反复斟酌具体题目的结果**。
26+
27+
那么在贪心总结篇里，我按难易程度以及题目类型大体归个类。
28+
29+
贪心大总结正式开始：
30+
31+
## 贪心理论基础
32+
33+
在贪心系列开篇词[关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg)中，我们就讲解了大家对贪心的普遍疑惑。
34+
35+
1. 贪心很简单，就是常识？
36+
37+
跟着一起刷题的录友们就会发现，贪心思路往往很巧妙，并不简单。
38+
39+
2. 贪心有没有固定的套路？
40+
41+
贪心无套路，也没有框架之类的，需要多看多练培养感觉才能想到贪心的思路。
42+
43+
3. 究竟什么题目是贪心呢？
44+
45+
Carl个人认为：如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。（并不是权威解读，一家之辞哈）
46+
47+
但我们也不用过于强调什么题目是贪心，什么不是贪心，那就太学术了，毕竟学会解题就行了。
48+
49+
4. 如何知道局部最优推出全局最优，有数学证明么？
50+
51+
在做贪心题的过程中，如果再来一个数据证明，其实没有必要，手动模拟一下，如果找不出反例，就试试贪心。面试中，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了
52+
53+
就像是 要用一下 1 + 1 = 2，没有必要再证明一下 1 + 1 究竟为什么等于 2。（例子极端了点，但是这个道理）
54+
55+
相信大家读完[关于贪心算法，你该了解这些！](https://mp.weixin.qq.com/s/O935TaoHE9Eexwe_vSbRAg)，就对贪心有了一个基本的认识了。
56+
57+
58+
## 贪心简单题
59+
60+
以下三道题目就是简单题，大家会发现贪心感觉就是常识。是的，如下三道题目，就是靠常识，但我都具体分析了局部最优是什么，全局最优是什么，贪心也要贪的有理有据！
61+
62+
* [贪心算法：分发饼干](https://mp.weixin.qq.com/s/YSuLIAYyRGlyxbp9BNC1uw)
63+
* [贪心算法：K次取反后最大化的数组和](https://mp.weixin.qq.com/s/dMTzBBVllRm_Z0aaWvYazA)
64+
* [贪心算法：柠檬水找零](https://mp.weixin.qq.com/s/0kT4P-hzY7H6Ae0kjQqnZg)
65+
66+
67+
## 贪心中等题
68+
69+
贪心中等题，靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。
70+
71+
* [贪心算法：摆动序列](https://mp.weixin.qq.com/s/Xytl05kX8LZZ1iWWqjMoHA)
72+
* [贪心算法：单调递增的数字](https://mp.weixin.qq.com/s/TAKO9qPYiv6KdMlqNq_ncg)
73+
74+
### 贪心解决股票问题
75+
76+
大家都知道股票系列问题是动规的专长，其实用贪心也可以解决，而且还不止就这两道题目，但这两道比较典型，我就拿来单独说一说
77+
78+
* [贪心算法：买卖股票的最佳时机II](https://mp.weixin.qq.com/s/VsTFA6U96l18Wntjcg3fcg)
79+
* [贪心算法：买卖股票的最佳时机含手续费](https://mp.weixin.qq.com/s/olWrUuDEYw2Jx5rMeG7XAg)
80+
81+
### 两个维度权衡问题
82+
83+
在出现两个维度相互影响的情况时，两边一起考虑一定会顾此失彼，要先确定一个维度，再确定另一个一个维度。
84+
85+
* [贪心算法：分发糖果](https://mp.weixin.qq.com/s/8MwlgFfvaNYmjGwjuMlETQ)
86+
* [贪心算法：根据身高重建队列](https://mp.weixin.qq.com/s/-2TgZVdOwS-DvtbjjDEbfw)
87+
88+
在讲解本题的过程中，还强调了编程语言的重要性，模拟插队的时候，使用C++中的list（链表）替代了vector(动态数组)，效率会高很多。
89+
90+
所以在[贪心算法：根据身高重建队列（续集）](https://mp.weixin.qq.com/s/K-pRN0lzR-iZhoi-1FgbSQ)详细讲解了，为什么用list（链表）更快！
91+
92+
**大家也要掌握自己所用的编程语言，理解其内部实现机制，这样才能写出高效的算法！**
93+
94+
## 贪心难题
95+
96+
这里的题目如果没有接触过，其实是很难想到的，甚至接触过，也一时想不出来，所以题目不要做一遍，要多练！
97+
98+
### 贪心解决区间问题
99+
100+
关于区间问题，大家应该印象深刻，有一周我们专门讲解的区间问题，各种覆盖各种去重。
101+
102+
* [贪心算法：跳跃游戏](https://mp.weixin.qq.com/s/606_N9j8ACKCODoCbV1lSA)
103+
* [贪心算法：跳跃游戏II](https://mp.weixin.qq.com/s/kJBcsJ46DKCSjT19pxrNYg)
104+
* [贪心算法：用最少数量的箭引爆气球](https://mp.weixin.qq.com/s/HxVAJ6INMfNKiGwI88-RFw)
105+
* [贪心算法：无重叠区间](https://mp.weixin.qq.com/s/oFOEoW-13Bm4mik-aqAOmw)
106+
* [贪心算法：划分字母区间](https://mp.weixin.qq.com/s/pdX4JwV1AOpc_m90EcO2Hw)
107+
* [贪心算法：合并区间](https://mp.weixin.qq.com/s/royhzEM5tOkUFwUGrNStpw)
108+
109+
### 其他难题
110+
111+
[贪心算法：最大子序和](https://mp.weixin.qq.com/s/DrjIQy6ouKbpletQr0g1Fg) 其实是动态规划的题目，但贪心性能更优，很多同学也是第一次发现贪心能比动规更优的题目。
112+
113+
114+
[贪心算法：加油站](https://mp.weixin.qq.com/s/aDbiNuEZIhy6YKgQXvKELw)可能以为是一道模拟题，但就算模拟其实也不简单，需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。
115+
116+
最后贪心系列压轴题目[贪心算法：我要监控二叉树！](https://mp.weixin.qq.com/s/kCxlLLjWKaE6nifHC3UL2Q)，不仅贪心的思路不好想，而且需要对二叉树的操作特别娴熟，这就是典型的交叉类难题了。
117+
118+
119+
## 贪心每周总结
120+
121+
周总结里会对每周的题目中大家的疑问、相关难点或者笔误之类的进行复盘和总结。
122+
123+
如果大家发现文章哪里有问题，那么在周总结里或者文章评论区一定进行了修正，保证不会因为我的笔误或者理解问题而误导大家，哈哈。
124+
125+
所以周总结一定要看！
126+
127+
* [本周小结！（贪心算法系列一）](https://mp.weixin.qq.com/s/KQ2caT9GoVXgB1t2ExPncQ)
128+
* [本周小结！（贪心算法系列二）](https://mp.weixin.qq.com/s/RiQri-4rP9abFmq_mlXNiQ)
129+
* [本周小结！（贪心算法系列三）](https://mp.weixin.qq.com/s/JfeuK6KgmifscXdpEyIm-g)
130+
* [本周小结！（贪心算法系列四）](https://mp.weixin.qq.com/s/zAMHT6JfB19ZSJNP713CAQ)
131+
132+
## 总结
133+
134+
很多没有接触过贪心的同学都会感觉贪心有啥可学的，但只要跟着「代码随想录」坚持下来之后，就会发现，贪心是一种很重要的算法思维而且并不简单，贪心往往妙的出其不意，触不及防！
135+
136+
**回想一下我们刚刚开始讲解贪心的时候，大家会发现自己在坚持中进步了很多！**
137+
138+
这也是「代码随想录」的初衷，只要一路坚持下来，不仅基础扎实，而且进步也是飞速的。
139+
140+
**在这十八道贪心经典题目中，大家可以发现在每一道题目的讲解中，我都是把什么是局部最优，和什么是全局最优说清楚**。
141+
142+
这也是我认为判断这是一道贪心题目的依据，如果找不出局部最优，那可能就是一道模拟题。
143+
144+
不知不觉又一个系列结束了，同时也是2020年的结束。
145+
146+
**一个系列的结束，又是一个新系列的开始，我们将在明年第一个工作日正式开始动态规划，来不及解释了，录友们上车别掉队，我们又要开始新的征程！**
147+
148+
> **相信很多小伙伴刷题的时候面对力扣上近两千道题目，感觉无从下手，我花费半年时间整理了Github项目：「力扣刷题攻略」[https://github.com/youngyangyang04/leetcode-master](https://github.com/youngyangyang04/leetcode-master)。 里面有100多道经典算法题目刷题顺序、配有40w字的详细图解，常用算法模板总结，以及难点视频讲解，按照list一道一道刷就可以了！star支持一波吧！**
149+
150+
* 公众号：[代码随想录](https://img-blog.csdnimg.cn/20210210152223466.png)
151+
* B站：[代码随想录](https://space.bilibili.com/525438321)
152+
* Github：[leetcode-master](https://github.com/youngyangyang04/leetcode-master)
153+
* 知乎：[代码随想录](https://www.zhihu.com/people/sun-xiu-yang-64)
154+
155+
![](https://img-blog.csdnimg.cn/20210205113044152.png)
156+
157+

‎problems/贪心算法理论基础.md

Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
2+
<p align='center'>
3+
<img src="https://img-blog.csdnimg.cn/20201215214102642.png" width=400 >
4+
</p>
5+
<p align="center">
6+
<a href="https://github.com/youngyangyang04/leetcode-master"><img src="https://img.shields.io/badge/Github-leetcode--master-lightgrey" alt=""></a>
7+
<a href="https://img-blog.csdnimg.cn/20201115103410182.png"><img src="https://img.shields.io/badge/刷题-微信群-green" alt=""></a>
8+
<a href="https://img-blog.csdnimg.cn/20201210231711160.png"><img src="https://img.shields.io/badge/公众号-代码随想录-brightgreen" alt=""></a>
9+
<a href="https://space.bilibili.com/525438321"><img src="https://img.shields.io/badge/B站-代码随想录-orange" alt=""></a>
10+
<a href="https://www.zhihu.com/people/sun-xiu-yang-64"><img src="https://img.shields.io/badge/知乎-代码随想录-blue" alt=""></a>
11+
<a href="https://www.toutiao.com/c/user/60356270818/#mid=1633692776932365"><img src="https://img.shields.io/badge/头条-代码随想录-red" alt=""></a>
12+
</p>
13+
14+
# 关于贪心算法，你该了解这些！
15+
16+
> 正式开始新的系列了，贪心算法！
17+
通知：一些录友表示经常看不到每天的文章，现在公众号已经不按照发送时间推荐了，而是根据一些规则乱序推送，所以可能关注了「代码随想录」也一直看不到文章，建议把「代码随想录」设置星标哈，设置星标之后，每天就按发文时间推送了，我每天都是定时8:35发送的，嗷嗷准时，哈哈。
18+
19+
## 什么是贪心
20+
21+
**贪心的本质是选择每一阶段的局部最优，从而达到全局最优**。
22+
23+
这么说有点抽象，来举一个例子：
24+
25+
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
26+
27+
指定每次拿最大的，最终结果就是拿走最大数额的钱。
28+
29+
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
30+
31+
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。动态规划的问题在下一个系列会详细讲解。
32+
33+
## 贪心的套路（什么时候用贪心）
34+
35+
很多同学做贪心的题目的时候，想不出来是贪心，想知道有没有什么套路可以一看就看出来是贪心。
36+
37+
**说实话贪心算法并没有固定的套路**。
38+
39+
所以唯一的难点就是如何通过局部最优，推出整体最优。
40+
41+
那么如何能看出局部最优是否能推出整体最优呢？有没有什么固定策略或者套路呢？
42+
43+
**不好意思，也没有！** 靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
44+
45+
有同学问了如何验证可不可以用贪心算法呢？
46+
47+
**最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧**。
48+
49+
可有有同学认为手动模拟，举例子得出的结论不靠谱，想要严格的数学证明。
50+
51+
一般数学证明有如下两种方法：
52+
53+
* 数学归纳法
54+
* 反证法
55+
56+
看教课书上讲解贪心可以是一堆公式，估计大家连看都不想看，所以数学证明就不在我要讲解的范围内了，大家感兴趣可以自行查找资料。
57+
58+
**面试中基本不会让面试者现场证明贪心的合理性，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了**。
59+
60+
举一个不太恰当的例子：我要用一下1+1 = 2，但我要先证明1+1 为什么等于2。严谨是严谨了，但没必要。
61+
62+
虽然这个例子很极端，但可以表达这么个意思：**刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心**。
63+
64+
**例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！**
65+
66+
所以这也是为什么很多同学通过（accept）了贪心的题目，但都不知道自己用了贪心算法，**因为贪心有时候就是常识性的推导，所以会认为本应该就这么做！**
67+
68+
**那么刷题的时候什么时候真的需要数学推导呢？**
69+
70+
例如这道题目：[链表：环找到了，那入口呢？](https://mp.weixin.qq.com/s/_QVP3IkRZWx9zIpQRgajzA)，这道题不用数学推导一下，就找不出环的起始位置，想试一下就不知道怎么试，这种题目确实需要数学简单推导一下。
71+
72+
## 贪心一般解题步骤
73+
74+
贪心算法一般分为如下四步：
75+
76+
* 将问题分解为若干个子问题
77+
* 找出适合的贪心策略
78+
* 求解每一个子问题的最优解
79+
* 将局部最优解堆叠成全局最优解
80+
81+
其实这个分的有点细了，真正做题的时候很难分出这么详细的解题步骤，可能就是因为贪心的题目往往还和其他方面的知识混在一起。
82+
83+
## 总结
84+
85+
本篇给出了什么是贪心以及大家关心的贪心算法固定套路。
86+
87+
**不好意思了，贪心没有套路，说白了就是常识性推导加上举反例**。
88+
89+
最后给出贪心的一般解题步骤，大家可以发现这个解题步骤也是比较抽象的，不像是二叉树，回溯算法，给出了那么具体的解题套路和模板。
90+
91+
本篇没有配图，其实可以找一些动漫周边或者搞笑的图配一配（符合大多数公众号文章的作风），但这不是我的风格，所以本篇文字描述足以！
92+
93+
> **相信很多小伙伴刷题的时候面对力扣上近两千道题目，感觉无从下手，我花费半年时间整理了Github项目：「力扣刷题攻略」[https://github.com/youngyangyang04/leetcode-master](https://github.com/youngyangyang04/leetcode-master)。 里面有100多道经典算法题目刷题顺序、配有40w字的详细图解，常用算法模板总结，以及难点视频讲解，按照list一道一道刷就可以了！star支持一波吧！**
94+
95+
* 公众号：[代码随想录](https://img-blog.csdnimg.cn/20210210152223466.png)
96+
* B站：[代码随想录](https://space.bilibili.com/525438321)
97+
* Github：[leetcode-master](https://github.com/youngyangyang04/leetcode-master)
98+
* 知乎：[代码随想录](https://www.zhihu.com/people/sun-xiu-yang-64)
99+
100+
![](https://img-blog.csdnimg.cn/20210205113044152.png)
101+
102+

0 commit comments

Comments
 (0)