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