本科专业建设网站,工程认证网站的建设,通过模版做网站,网站做的一般怎么评价文章转自代码随想录
贪心算法总结篇
我刚刚开始讲解贪心系列的时候就说了#xff0c;贪心系列并不打算严格的从简单到困难这么个顺序来讲解。
因为贪心的简单题可能往往过于简单甚至感觉不到贪心#xff0c;如果我连续几天讲解简单的贪心#xff0c;估计录友们一定会不耐…文章转自代码随想录
贪心算法总结篇
我刚刚开始讲解贪心系列的时候就说了贪心系列并不打算严格的从简单到困难这么个顺序来讲解。
因为贪心的简单题可能往往过于简单甚至感觉不到贪心如果我连续几天讲解简单的贪心估计录友们一定会不耐烦了会感觉贪心有啥好学的。
但贪心的难题又真的有点难所以我是简单困难交错着讲的这样大家就感觉难度适中而且贪心也没有什么框架和套路所以对刷题顺序要求没有那么高。
但在贪心系列我发的题目难度会整体呈现一个阶梯状上升细心的录友们应该有所体会。
在刚刚讲过的回溯系列中大家可以发现我是严格按照框架难度顺序循序渐进讲解的和贪心又不一样因为回溯法如果题目顺序没选好刷题效果会非常差
同样回溯系列也不允许简单困难交替着来因为前后题目都是有因果关系的相信跟着刷过回溯系列的录友们都会明白我的良苦用心哈哈。
每个系列都有每个系列的特点我都会根据特点有所调整大家看我每天的推送的题目都不是随便找一个到就推送的都是先有整体规划然后反复斟酌具体题目的结果。
那么在贪心总结篇里我按难易程度以及题目类型大体归个类。
贪心大总结正式开始
# 贪心理论基础
在贪心系列开篇词关于贪心算法你该了解这些
(opens new window)中我们就讲解了大家对贪心的普遍疑惑。
贪心很简单就是常识
跟着一起刷题的录友们就会发现贪心思路往往很巧妙并不简单。
贪心有没有固定的套路
贪心无套路也没有框架之类的需要多看多练培养感觉才能想到贪心的思路。
究竟什么题目是贪心呢
Carl个人认为如果找出局部最优并可以推出全局最优就是贪心如果局部最优都没找出来就不是贪心可能是单纯的模拟。并不是权威解读一家之辞哈
但我们也不用过于强调什么题目是贪心什么不是贪心那就太学术了毕竟学会解题就行了。
如何知道局部最优推出全局最优有数学证明么
在做贪心题的过程中如果再来一个数据证明其实没有必要手动模拟一下如果找不出反例就试试贪心。面试中代码写出来跑过测试用例即可或者自己能自圆其说理由就行了
就像是 要用一下 1 1 2没有必要再证明一下 1 1 究竟为什么等于 2。例子极端了点但是这个道理
相信大家读完关于贪心算法你该了解这些
(opens new window)就对贪心有了一个基本的认识了。
# 贪心简单题
以下三道题目就是简单题大家会发现贪心感觉就是常识。是的如下三道题目就是靠常识但我都具体分析了局部最优是什么全局最优是什么贪心也要贪的有理有据
贪心算法分发饼干
(opens new window)贪心算法K次取反后最大化的数组和(opens new window)贪心算法柠檬水找零
(opens new window)
# 贪心中等题
贪心中等题靠常识可能就有点想不出来了。开始初现贪心算法的难度与巧妙之处。
贪心算法摆动序列
(opens new window)贪心算法单调递增的数字
(opens new window)
# 贪心解决股票问题
大家都知道股票系列问题是动规的专长其实用贪心也可以解决而且还不止就这两道题目但这两道比较典型我就拿来单独说一说
贪心算法买卖股票的最佳时机II
(opens new window)贪心算法买卖股票的最佳时机含手续费
(opens new window) 本题使用贪心算法比较绕建议后面学习动态规划章节的时候理解动规就好
# 两个维度权衡问题
在出现两个维度相互影响的情况时两边一起考虑一定会顾此失彼要先确定一个维度再确定另一个一个维度。
贪心算法分发糖果
(opens new window)贪心算法根据身高重建队列
(opens new window)
在讲解本题的过程中还强调了编程语言的重要性模拟插队的时候使用C中的list链表替代了vector(动态数组)效率会高很多。
所以在贪心算法根据身高重建队列续集
(opens new window)详细讲解了为什么用list链表更快
大家也要掌握自己所用的编程语言理解其内部实现机制这样才能写出高效的算法
# 贪心难题
这里的题目如果没有接触过其实是很难想到的甚至接触过也一时想不出来所以题目不要做一遍要多练
# 贪心解决区间问题
关于区间问题大家应该印象深刻有一周我们专门讲解的区间问题各种覆盖各种去重。
贪心算法跳跃游戏
(opens new window)贪心算法跳跃游戏II(opens new window)贪心算法用最少数量的箭引爆气球(opens new window)贪心算法无重叠区间(opens new window)贪心算法划分字母区间(opens new window)贪心算法合并区间
(opens new window)
# 其他难题
贪心算法最大子序和
(opens new window) 其实是动态规划的题目但贪心性能更优很多同学也是第一次发现贪心能比动规更优的题目。
贪心算法加油站
(opens new window)可能以为是一道模拟题但就算模拟其实也不简单需要把while用的很娴熟。但其实是可以使用贪心给时间复杂度降低一个数量级。
最后贪心系列压轴题目贪心算法我要监控二叉树
(opens new window)不仅贪心的思路不好想而且需要对二叉树的操作特别娴熟这就是典型的交叉类难题了。
# 贪心每周总结
周总结里会对每周的题目中大家的疑问、相关难点或者笔误之类的进行复盘和总结。
如果大家发现文章哪里有问题那么在周总结里或者文章评论区一定进行了修正保证不会因为我的笔误或者理解问题而误导大家哈哈。
所以周总结一定要看
本周小结贪心算法系列一
(opens new window)本周小结贪心算法系列二(opens new window)本周小结贪心算法系列三(opens new window)本周小结贪心算法系列四
(opens new window)
# 总结
贪心专题汇聚为一张图
这个图是 代码随想录知识星球
(opens new window) 成员海螺人
(opens new window)所画总结的非常好分享给大家。
很多没有接触过贪心的同学都会感觉贪心有啥可学的但只要跟着「代码随想录」坚持下来之后就会发现贪心是一种很重要的算法思维而且并不简单贪心往往妙的出其不意触不及防
回想一下我们刚刚开始讲解贪心的时候大家会发现自己在坚持中进步了很多
这也是「代码随想录」的初衷只要一路坚持下来不仅基础扎实而且进步也是飞速的。
在这十八道贪心经典题目中大家可以发现在每一道题目的讲解中我都是把什么是局部最优和什么是全局最优说清楚。
这也是我认为判断这是一道贪心题目的依据如果找不出局部最优那可能就是一道模拟题。
不知不觉又一个系列结束了
