贪心算法学习随笔这段时间刷算法题最先上手的就是贪心。比起DP、回溯要考虑各种状态、记录大量中间数据贪心写起来明显轻松很多。一开始我以为贪心万能随便一道题都套“每次选最好的”思路踩了好几次坑才明白它有很明确的使用限制不能凭直觉乱写。下面结合我做题时的真实思路和代码记录一下。一、贪心到底是什么它的核心逻辑很简单处理问题时每一步只选当下看起来最优的方案选定之后不会回头修改一路做到结束。生活里找零钱、安排时间都自带这种思维。但这里有个关键前提一步步的局部最优最后合在一起必须是整体最优不满足这个前提答案一定会错。二、入门例题活动安排题目要求同一时间只能参加一个活动给出所有活动的起止时间算出最多能参加几场。我一开始试了两种思路先按开始时间排序结果安排到后面很容易被长活动占住时间换成按结束时间从小到大排序后每次挑结束最早的剩下的空闲时间最多能塞下更多活动这才是正确局部策略。importjava.util.*;classActivity{intstart,end;Activity(ints,inte){starts;ende;}}publicclassTest{publicstaticvoidmain(String[]args){ListActivityactsnewArrayList();acts.add(newActivity(1,3));acts.add(newActivity(2,4));acts.add(newActivity(3,5));acts.add(newActivity(6,7));// 按结束时间升序acts.sort((a1,a2)-a1.end-a2.end);intcount0;intlastEnd-1;for(Activitya:acts){if(a.startlastEnd){count;lastEnda.end;}}System.out.println(count);}}这段代码跑出来结果是3是这组数据下能参加的最大数量。三、零钱兑换看清贪心的局限标准人民币面额50、20、10、5、1凑金额优先选大额完全没问题。publicclassCoin{publicstaticvoidmain(String[]args){int[]coins{50,20,10,5,1};inttarget63;intcnt0;intresttarget;for(intc:coins){if(restc){cntrest/c;restrest%c;}}System.out.println(cnt);}}但如果换一组特殊面额比如只有1、3、4凑6块钱。按照贪心思路先拿4剩下两个1一共3张但最优解是两张3只用两张。这里贪心就失效了。做完这道题我才记牢不是所有求最值的题都能用贪心得先手动模拟小数据验证策略是否成立。四、能用贪心的两个条件贪心选择性每一步最优的选择最终能导向全局最优最优子结构整个问题的最优解包含子问题的最优解。两个条件缺一个贪心都不适用要换成动态规划。五、平时刷题常遇到的贪心题型区间类活动安排、区间覆盖统一思路是排序后依次筛选分配类分饼干、分糖果两边排序后一一匹配数字构造拼接数字求最大或最小值自定义排序规则行程类跳跃游戏、加油站每一步选最远可到达位置。六、贪心的优缺点优点很明显只需要一次排序加单层循环运行速度快代码量少不用开数组存大量中间状态调试起来简单。缺点也很突出适用场景窄很多复杂问题满足不了贪心条件而且正确性很难一眼看出来必须手动举例验证不能直接写代码。学习小结贪心算是入门最简单的算法但也是最容易误用的。我之前做题总懒得验证策略直接上手写代码经常出现样例过了、测试数据出错的情况。现在我自己固定一套做题流程先想一种局部最优策略手动用简单数字试一遍确认能得到全局最优再动手写代码如果模拟后结果不对直接放弃贪心改用动态规划或者暴力枚举。对比其他算法能明显感觉到贪心不需要记录过往所有状态走一步定一步逻辑直白但能不能用全看题目本身的特性。
