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

Commitf7771e6

Browse files
添加贪心算法
1 parent2fec084 commitf7771e6

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+
<palign='center'>
2+
<imgsrc="https://img-blog.csdnimg.cn/20201215214102642.png"width=400 >
3+
</p>
4+
<palign="center">
5+
<ahref="https://github.com/youngyangyang04/leetcode-master"><imgsrc="https://img.shields.io/badge/Github-leetcode--master-lightgrey"alt=""></a>
6+
<ahref="https://img-blog.csdnimg.cn/20201115103410182.png"><imgsrc="https://img.shields.io/badge/刷题-微信群-green"alt=""></a>
7+
<ahref="https://img-blog.csdnimg.cn/20201210231711160.png"><imgsrc="https://img.shields.io/badge/公众号-代码随想录-brightgreen"alt=""></a>
8+
<ahref="https://space.bilibili.com/525438321"><imgsrc="https://img.shields.io/badge/B站-代码随想录-orange"alt=""></a>
9+
<ahref="https://www.zhihu.com/people/sun-xiu-yang-64"><imgsrc="https://img.shields.io/badge/知乎-代码随想录-blue"alt=""></a>
10+
<ahref="https://www.toutiao.com/c/user/60356270818/#mid=1633692776932365"><imgsrc="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+
Lines changed: 102 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,102 @@
1+
2+
<palign='center'>
3+
<imgsrc="https://img-blog.csdnimg.cn/20201215214102642.png"width=400 >
4+
</p>
5+
<palign="center">
6+
<ahref="https://github.com/youngyangyang04/leetcode-master"><imgsrc="https://img.shields.io/badge/Github-leetcode--master-lightgrey"alt=""></a>
7+
<ahref="https://img-blog.csdnimg.cn/20201115103410182.png"><imgsrc="https://img.shields.io/badge/刷题-微信群-green"alt=""></a>
8+
<ahref="https://img-blog.csdnimg.cn/20201210231711160.png"><imgsrc="https://img.shields.io/badge/公众号-代码随想录-brightgreen"alt=""></a>
9+
<ahref="https://space.bilibili.com/525438321"><imgsrc="https://img.shields.io/badge/B站-代码随想录-orange"alt=""></a>
10+
<ahref="https://www.zhihu.com/people/sun-xiu-yang-64"><imgsrc="https://img.shields.io/badge/知乎-代码随想录-blue"alt=""></a>
11+
<ahref="https://www.toutiao.com/c/user/60356270818/#mid=1633692776932365"><imgsrc="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)
[8]ページ先頭
©2009-2025 Movatter.jp