https://leetcode-cn.com/problems/jump-game-ii/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-tan-x-yh58/

image.png

简单贪心

455. 分发饼干

思路

  • 用最小的饼干满足胃口最小的孩子，最小化浪费
  • 排序+贪心

  • 这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

    1005. K 次取反后最大化的数组和（多练）

    自己第一遍没做出来
    思路

  • 当K>0时，每次取数组最小的取反，然后重新插入

  • 这样子，全为非负时代价最小，有负数时，获利最大

    860. 柠檬水找零

    比较符合常识

  • 如果要找零5元，直接看5元够不够

  • 如果要找零15元，

  • 排序

  • 能+1就+1

    376. 摆动序列（32.78%，不做）

  • 最长子序列长度：子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。


  • 738. 单调递增的数字（31.1%, 不做）

股票问题

122. 买卖股票的最佳时机 II

因为交易次数不受限，如果可以把所有的上坡全部收集到，一定是利益最大化的

714. 买卖股票的最佳时机含手续费（43.13%）

和122类似，只不过需要考虑手续费。当我们卖出一支股票时，我们就立即获得了以相同价格并且免除手续费买入一支股票的权利。在遍历完整个数组 prices之后，我们就得到了最大的总收益。

两个维度权衡问题

135. 分发糖果

我们可以将「相邻的孩子中，评分高的孩子必须获得更多的糖果」这句话拆分为两个规则，分别处理。
之后，选择两个规则中的较大值为分配糖果的数量则是同时满足两个规则的最小糖果分配量。Screen Shot 2021-08-24 at 12.50.14 pm.png

406. 根据身高重建队列

一句话解释答案：高个子的人是看不到低个子人的, 先排序，再插队。
算法

  • 按照 h_i为第一关键字升序，k_i 为第二关键字降序进行排序
  • 将第 i 个人放入队列中的从左往右第 k_i +1 个空位置，即可得到原始的队列。

跳跃游戏

55. 跳跃游戏

依次遍历+记录最远可到达的距离+如果大于终点，则返回true
原理：因为只要是最远距离内，每个点我们都可以走到的，所以更新最远到达距离就行。【覆盖范围】

45. 跳跃游戏 II(不熟练)

  • 最少的步伐，最快更新【覆盖范围】到达满足条件。
  • 在上一个【覆盖范围】内，找出一步能增加的最长距离，并且更新新的【覆盖范围】
  • 在遍历数组时，我们不访问最后一个元素，这是因为在访问最后一个元素之前，我们的边界一定大于等于最后一个位置，否则就无法跳到最后一个位置了。如果访问最后一个元素，在边界正好为最后一个位置的情况下，我们会增加一次「不必要的跳跃次数」，因此我们不必访问最后一个元素。
  1. for (int i = 0; i < nums.length - 1; i++){
  2.     longest = Math.max(longest, nums[i] + i);
  4.     if (end == i){
  5.         // 在上一个【覆盖范围】内，找出一步能增加的最长距离，并且更新新的【覆盖范围】
  6.         end = longest;
  7.         step++;
  8.     }
  9. }

区间问题

452. 用最少数量的箭引爆气球（48.62%）

  • 注意：排序写comparator的时候，用a-b的话会overflow，之间大于 小于 号比较即可。

    435. 无重叠区间（62.84%）

    思路：

  • 最少要移除几个区间才会是无重叠区间 === 最多可以组合出多少个区间是无重叠的

  • 然后就变成了任务调度问题，使用排序+贪心算法，之后可以得到最多满足条件的区间是几个

任务调度问题贪心的证明

  • 每次选最早结束的，就会是全局最优解

  • 证明：首先去掉结果集中的第一个活动A，那么在剩下的活动中，结束时间最早的活动B的结束时间一定不早于A,那么A活动在最优解中一定合理。再用同样的方式判断活动B,依次类推，则结果集就是最优解。

    763. 划分字母区间（64.50%）

    算法：

  • 预处理：每个字符的last 出现的index

  • 贪心求：每个字符在last index会break

    56. 合并区间（85.93%）

    算法：排序+贪心

    Tricky

    134. 加油站（难题，不好想）

  • 算法：暴力算法的优化 -> 如果x到不了y，那么x和y之间的任何点都到不了y，所以可以跳过这些点，从而优化暴力算法。

    968. 监控二叉树（36.4%, 不做）