[1006]贪心刷题思路
贪心
本篇博客只记录刷题思路不记录具体代码,用于本人快速回顾
题目来源代码随想录
刷完感想:连刷三个小时头都要晕了,去吃牛肉饭了🤤
:::tip 和贪心题相关的提示
局部最优得到全局最优
:::
分发饼干
非常标准的贪心
先满足胃口小的,注意这种情况是for饼干if胃口,因为无论是否满足,饼干一定会后移动,胃口不一定会后移(和先满足胃口的思路不一样,这种是胃口一定会前移,饼干不一定前移)
第二tips就是用if优化for循环,做一个自减
摆动序列
笑死感觉不算贪心算模拟,思路上有难度
比较[当前差值]和[上一个差值]
相同不算,不同算一个
最大子序和
贪心的点在于:碰到连续和为负数的情况就舍弃,不要影响后续的最大和
买股票的最佳时间Ⅱ
非常简单:求差,正数就算上利益
(不用担心连续正数,这种情况也考虑到了)
跳跃游戏
思路:不能从后往前,因为除了要判断能否往后到达,还要考虑前面能不能到这里
==》考虑最远范围 + 能不能到达(从前考虑就比较容易,刚好是之前的最大值)
跳跃游戏Ⅱ
比较有难度,难度在于找到更新maxReach的时机,是到了当前跳跃边界才更新cnt,而不是更新了maxReach就更新cnt
k次取反求最大值
思路easy,从小到大排序
一次贪心:先把最小的负数更新成正数
二次贪心:如果还有次数,偶直接抵消,奇就找到最小的正数为负
加油站
初步思路想到了根据gas和cost的差判断找起始点
但是以为找到最大值就行了
nono,应该用前缀和找到负数和的下一个
而且有个证明:有解就是唯一解
还需要判断一下sum<0的话无解
分发糖果
[老师怎么是hard,我是废物先溜了]
柠檬水找零
easy,更新5r、10r的张数能否满足就行
贪心的点在于20可以换3*5,也可以10+5,这个时候应该有限10+5
but第一反应怎么是用数组存?肯定是int存啊,奇怪脑子
身高重建队列
太妙了
初步思路想到了先根据身高排列,再根据人数调整位置
但是应该从大到小排(妙!!!!!),然后直接插入到对应的位置
而且注意用LinkedList的add(index,value)
方法更快,后续再toArray(new int[size][])
最少数量箭引爆气球
服了没读懂题目
思路就是找排序 + 是否交集(前一个气球的末值和后一个气球的初值)
没有交集多加一支箭
有交集就更新后一个气球的末值为前后气球末值的最小值,不用加箭