d> 贪心算法的核心思想就是由局部最优解推出全局最优解,所以每一次指用考虑局部最优即可,如果要想证明局部最优可以推出全局最优可以使用数学归纳法或者反证法

  1. 分发饼干 此时的贪心策略就是尽量把小饼干发放给胃口小的孩子,这样就可以找到局部最优算法,此时只需要利用两个指针,一个指针指向孩子另外一个指针指向饼干,在遍历的过程中不断找到小的饼干喂给孩子即可 分发饼干.cpp
  2. 摆动序列 可以画图理解,此时局部最优算法就是把单调坡上面的所有数字删除,只是留下局部峰值中的数据,例如此时使用preDiff记录前面两个数字的差值,curDiff记录当前数字和后面数字的差值,当preDiff与curDiff异号的时候就表示遇到了局部峰,此时就可以把结果进行自增操作了,但是注意这里的细节比较多,比如:
    • 遇到平坡并且最有一个元素出现峰值的情况,所以此时要想要把记录平坡中的最后一个元素,允许preDiff = 0
    • 对于第一个元素,可以默认是一个局部峰(一定包含在最终的结果中,可以证明),所以可以把preDiff设置为0 从而得到这一个局部峰并且把result初始化为1表示第一个元素是一个局部峰
    • 对于平坡并且单调的情况,注意此时只有早出现波动的时候才可以更新preDiff = curDiff 代码 摆动序列.cpp
  3. 最大子数组和 非常经典的一个题目,贪心策略: 当当前的总和小与0的时候还不如从下面一个元素重新开始加,但是注意这里有一个小坑,也就是不可以在当前元素和最大元素进行比较的时候设置count = 0,否则就会导致最大值可能为0,所以智能在最后把总和设置为 0(代码随想录的做法) ,当然也可以直接把总和设置为当前数字并且进行比较也是一样的 最大子数组和 1.cpp
  4. 买卖股票的最佳时间II 贪心策略有两种:
    • 由于利润是累加的,所以可以只要后面一天的利润大于前面一天的利润就可以卖出股票了
    • 或者把数组想象成一个山峰,在谷底买入股票,在山顶卖出股票,但是代码实现可能较为困难 另外注意写代码的时候不要害怕对于双指针的移动,可以看一个例子,并且根据这一个例子找出指针移动的规律,对于边界条件注意在每一次改变变量的时候添加即可,如果出错大不了直接改 代码: 买卖股票的最佳时间II.cpp
  5. 跳跃游戏 局部最优: 获取到最大覆盖的索引的位置,每一次不断更新最大索引的位置,并且遍历当前位置到最大索引的所有元素,如果遇到当前元素可以覆盖到数组末尾就可以返回true了,当然也可以使用一个范围 [startIndex,endIndex] ,每一次计算这一个范围可以到达的下一个索引范围即可 代码: 跳跃游戏.cpp
  6. 跳跃游戏II 此时还是需要基于范围,每一次范围就表示走一步了,还是采用两种方法:
    • 自己自创的方法,范围扩散,每一次利用一个startIndex记录当前位置开始的索引,endIndex用于记录最大索引范围,每一次遍历这一个范围内的数字并且更新这两个值即可
    • 代码随想录的方法,利用一个变量记录当前可以遍历到的范围,利用一个索引记录下一步可以到达的索引,当走到当前索引的位置的时候就可以更新步数了,更加接近实际 代码 跳跃游戏II.cpp
  7. K次去反之后最大化的整数和 这里还是两种贪心的思路: 第一种就是不断找到最小的元素并且把最小的元素反转即可,另外一种思路就是首先按照绝对值排序,对于绝对值大的元素如果小与0就可以反转,如果最终反转此时没有使用完毕,就可以堆对这其中某一个元素多次反转,如果最后还剩下一次就可以反转绝对值最小的以一个元素 K次取反之后的最大化的整数和.cpp
  8. 加油站 三种方法: 暴力解法(写出来了,但是测试用例中二十万个0 ... ) , 贪心算法:
    • 全局最优: 从0 出发计算所有的差值总和,如果得到所有的差值总和大小小与0说明不可能找到对应的索引,同时在这一个过程中记录累加值的最小量,之后从后面向前面遍历直到找到可以完全填补min的位置就可以返回了(这一个位置一定可以填补最小值)
    • 局部最优: 局部最优的特点就是不断调整策略,所以局部最优的方法就是如果遇到当前的累加值<0 说明这一个区间的前面一个区间的任意一个位置开始都不可以(注意此时前面的累积值都是大于0的),所以此时需要把当前总和设置为0重新开始从新的索引位置开始对于元素执行相加操作 代码: 加油站.cpp
  9. 分发糖果 一道hard,解法就是由于这里事物有两面性,所以此时需要考虑左边和右边的情况,考虑右边孩子大于左边孩子的情况从左边向右边遍历,考虑左边孩子大于右边孩子的情况需要从右边向左边遍历,遍历的过程中注意后面一个遍历的过程中每一个孩子糖果数量的确定方式就是只用满足比两边的孩子的糖果数量多即可,所以此时的递归公式为 : candyVec[i] = max(candyVec[i] , candyVec[i + 1] + 1) 代码: 分发糖果.cpp
  10. 柠檬水找零 经典的贪心算法,这里注意对于10元只可以使用一个5元进行找零,对于20元可以使用一个10元和一个5元或者3个5元,所以需要尽可能多的保留5 元,遇到不同的情况具体处理即可 柠檬水找零.cpp
  11. 根据身高重建队列 这里还是有两个维度,首先考虑身高维度按照身高排序,之后按照次数把相应的元素插入到队列中的相应位置即可(注意此时前面的元素已经插入好了),此时需要使用list进行元素的插入减少插入元素的时间复杂度 根据身高重建队列.cpp
  12. 用最少的箭引爆气球 这里一定需要站在局部性的角度考虑问题,首先可以考虑如果前后两个气球可以被同一个箭击破,那么需要满足的条件就是 points[i][0] <= points[i-1][1],在考虑三支箭,那么就需要求解前面两支箭的最小的一个右边边界值,之后判断第三支箭的头部位置和这一个边界值之间的关系即可 用最少的箭引爆气球.cpp
  13. 无重叠区间 注意这里还是考虑局部性,对于两个区间,如果重叠,那么一定是第二个区间的第一个元素小与第一个区间的最后一个元素,所以此时需要删除一个区间,这里选择删除哪一个区间可以根据哪一个区间的右边边界最小,这样 就可以尽量避免空位 无重叠区间.cpp
  14. 划分字母区间 这里给出两种思路:
    • 第一种: 首先记录每一个元素出现的次数,之后利用一个集合unordered_set在遍历的过程中记录遍历到的元素,如果某一个元素遍历到就可以把它出现的次数减少,当次数减少为 0 的时候就可以把元素从集合中移除了,此时就可以此时结果了
    • 第二种: 首先记录每一个元素出现的最远索引的位置,之后在便利的过程中不断更新右边边界为最远索引,当遍历到右边边界的位置的时候就可以记录结果了 代码: 划分字母区间.cpp
  15. 合并区间 一定需要总结区间相关问题的套路:
    • 对于区间相关的问题,首先需要对于左边边界进行排序,排序之后考虑局部性,也就是对于两个区间,区间重叠的判断条件就是: intervals[i][0] <= end,之后根据区间是否重叠两种情况分别对于end进行不同的更新并且记录结果即可 代码: 合并区间.cpp
  16. 单调递增的数字 还是需要不断模拟,这里还是提供两种思路:
    • 从前向后面遍历,比如 344521中,一旦遇到第一个递减的位置,这里也就是2的位置,此时就需要找到最前面的一个 5,把这一个位置减少一,之后把这一个位置之后的位置全部都设置为9 即可
    • 从后面遍历到前面,记录最前面的一个递增的位置,此时只需要把此时突然递增的位置减少一并且把后面的位置都设置为9即可,注意这里的条件是strNum[i - 1] > strNum[i] 没有相等 代码: 单调递增的数字.cpp
  17. 监控二叉树 一道名副其实的hard,如果第一次做基本上做不出来(其实第二次做也可能做不出来) 注意到每一个节点有三种状态并且注意根节点的处理方式即可,三种状态 0 --> 没有覆盖 1 --> 有摄像头 2 --> 被覆盖了 ,这里空节点不需要被覆盖所以可以返回2 ,所以此时需要利用后序遍历的方式遍历二叉树,并且根据返回结果的状态来确定当前节点的状态,但是注意根节点的覆盖方式! 代码: 监控二叉树.cpp