贪心算法小结-Toy模板网

这篇具有很好参考价值的文章主要介绍了贪心算法小结。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、分发饼干

1.注意判断条件的短路效应，先判断下标，防止出现下标越界的情况；

2.优先将大饼干先给胃口大的吃。

2、摆动序列

相当于寻找极值点的过程，predif和curdif分别记录前一点和当前点与前一元素的差值，两者异号的话，result++

删除单调坡度上的节点

贪心算法小结

3、最大子数组和

贪心：当连续和出现负数的时候立马放弃。

DP：dp[j]表示到下标j为止，连续子数组的最大和；有两种情况来：1.加在上一个上面 2.从这个数开始另起山头。

4.跳跃游戏

贪心：跳跃覆盖范围能否覆盖终点

注意 for循环里 i<=cover，cover为目前可覆盖的最大范围

5.跳跃游戏II

贪心：当前覆盖范围与下一步的覆盖范围，如果达到当前覆盖范围的最远位置但还没到终点，就需要再走一步，同时判断下一步的最大覆盖范围能不能到达终点。

6、按K次取反后最大化的数组和

将数组按绝对值大小排序，优先取反负数；如果还有次数剩余，就取反最小的数。

（当时用的方法是：每次都翻转最小的值，每次都得更新，k*n的时间复杂度，每次都得找一下当前最小的值）

7、加油站

判断当前站点的剩余油量和是否<0

8、分发糖果

从两个方向进行比较，从左到右而言，找到右边比左边大的情况，就在i-1的情况上多分一个糖果；从右往左，出现左边比右边大的情况，则取i+1的情况下+1和i的最大值。

9、柠檬水找零

记录每次收钱后，5元与10元的个数，在收入20需要找零15时，有10元优先使用10元，因为10元只能在此时找零，而5元的用处更多；此外20元的个数无需记录，因为它不参与找零。文章来源地址https://www.toymoban.com/news/detail-427931.html

到了这里，关于贪心算法小结的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

贪心算法小结