贪心算法

  1. 贪心算法理论基础
    1. 贪心的本质是选择每一阶段的局部最优，从而达到全局最优
    2. 如何确定可以选择用贪心算法？—>手动模拟一下，感觉可以局部最优退出整体最优，并且举不出反例，那就可以用贪心算法。
    3. 一般解题步骤
      1. 将问题分解为若干个子问题
      2. 找出适合的贪心策略
      3. 求解每一个子问题的最优解
      4. 将局部最优解堆叠成全局最优解
  2. 分发饼干
    1. 局部最优解就是大饼干先分给胃口大的，充分利用饼干尺寸喂饱一个，全局最优解就是喂饱尽可能多的小孩。
  3. 摆动序列
    1. 局部最优：删除单调坡度上的节点，那么这个坡度就会有两个局部峰值（贪心所贪的地方：让峰值尽可能的保持峰值，然后删除单一坡度上的节点）
    2. 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列
    3. 最后只需要统计数组的峰值数量即可，什么时候才能被判定为峰值？
      1. 计算prediff和curdiff，如果两者异号，说明有波动，i为峰值
    4. 需要额外考虑的情况
      1. 上下坡中有平坡
        1. 需要统一规则，删掉平坡中的左边几个还是右边几个
      2. 数组首尾两端
        1. 需要考虑当数组中只有两个不同元素是，摆动序列也为2，但是这种情况下无法计算prediff和curdiff
      3. 单调坡中有平坡
        1. 只需要在坡度发生摆动变化时，更新prediff，这样prediff在单调区间有平坡时不会发生变化
  4. 最大子序和
    1. 局部最优：当前连续和为负数时，立刻放弃，从下一个元素重新计算连续和，因为负数加上一个元素，连续和只会越来越小。
    2. 整体最优：选取最大连续和
    3. 遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。
  5. 买卖股票的最佳时机II
    1. 把利润分解为每天为单位的维度，假如第0天买入，第3天卖出，那么利润为prices[3]-prices[0]，即(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])，可以得到一个每天利润（prices[i]-prices[i-1]）的数组
    2. 局部最优：收集每天的正利润
    3. 整体最优：求得最大利润
  6. 跳跃游戏

    1. 转换思维，跳几步是不重要的，但是可以转换为本次跳跃的覆盖范围，如果能够覆盖到终点，那么就可以跳跃到终点。

    2. 一定是在现在的覆盖范围内更新更大的范围，不要漏解，要在覆盖范围内依次遍历

  7. 跳跃游戏II

    1. 局部最优：当前可移动距离尽可能多走（每次都选择最大步数），如果还没到终点，步数再加一

    2. 整体最优：一步尽可能多走，从而达到最少步数

    3. 统计：当前这一步的最大覆盖和下一步最大覆盖

  8. K次取反后最大化的数组和

    1. 第一步：序列中有负数，则需要将绝对值大的负数转化为正数

      1. 局部最优：让绝对值大的负数变为正数

      2. 整体最优：让整个数组和最大

    2. 第二步：此时数组中都变成了正整数数组，但是K还是>0，那么就需要转变K次正负，让数组和达到最大

      1. 局部最优：找数组中数值小的数进行反转
      2. 整体最优：让整个数组和最大

    3. 步骤

      1. 将数组按照绝对值从大到小排序（如果不按绝对值大小排序的话，可以先处理负数，然后再做其他处理）
      2. 从前向后遍历，遇到负数，变为正数，同时k–
      3. 如果遍历结束后，k>0，那么反复转变数值最小的元素，将k用完
      4. 求和返回
  9. 加油站
    1. 贪心算法1：从全局进行贪心选择，分析三种情况：
      1. 情况1：gas总和如果小于cost总和，那么不管从哪个加油站出发，都会断油
      2. 情况2：rest[i] = gas[i]-cost[i]，为当天剩下的油，如果累加到最后一站都为正，那么可以从第0个加油站开始行动。
      3. 情况3：当这个累加值的最小值为负数时，则可以从后向前遍历加油站的gas[i]，什么时候能够填平这个最小值，那么这个i就是可以出发的加油站编号。
    2. 贪心算法2：局部最优退出整体最优
      1. 局部最优：计算rest[i] = gas[i]-cost[i]，累积rest[i],当累计值小于0时，开始出发的加油站编号肯定不会是i，需要更新，从i+1开始找
      2. 整体最优：找到这个i。
  10. 分发糖果
    1. 对于一个i，有两个维度去确定，一个是左边，一个是右边，需要确定一边之后，再确定另一边，比较完每一个孩子的左边，然后再比较每一个孩子的右边
    2. 先从前向后遍历，比较每一个孩子的右边评分大于左边的情况。
    3. 然后从后向前遍历，比较每一个孩子左边评分大于右边的情况。细节：不是简单的+1，要看哪一个数更大一些。
  11. 柠檬水找零
    1. 只会遇到三种情况：
      1. 情况1：遇到5，收下5。
      2. 情况2：遇到10，找5。
      3. 情况3：遇到20，优先找5+10，如果找不到，再找3个5。
    2. 贪心体现在第三种情况的策略选择上。
  12. 根据身高重建队列
    1. 有两个维度，先确定一个维度，然后再按照另一个维度重新排列。如何选择？
      1. 如果按照K排列，最后会发现两个维度都不能确定；但是如果按照身高H排列，身高一定能确定下来。然后按照K为下标重新插入队列
    2. 局部最优：优先按照身高高的people的k来插入，后序插入的点不会影响前面已经插入的节点，也就是后面身高矮的节点插入后前面一定是身高高的。
    3. 整体最优：插入结束后，整个队列满足题目属性
    4. 注意容器的选择 & 比较器
  13. 用最少数量的箭引爆气球

    1. 局部最优：当气球出现重叠时，一起射，所用的弓箭个数最少。

    2. 全局最优：把所有气球射爆所用弓箭越少。

    3. 对气球进行排序，按照起始位置排序

      1. 判断气球是否重叠，如果两个气球不挨着，开射
      2. 如果两个气球挨着，更新重叠的最小右边界。

    4. 注意溢出

      1
      2
      3
      4
      5
      6
      7
      //不会溢出
      Arrays.sort(points, (a, b) -> Integer.compare(a[0], b[0]));
      //会溢出
      Arrays.sort(points,(a,b)->{
                  return a[0]-b[0];
              });

  14. 无重叠区间
    1. 按照右边界排序，从左向右记录非交叉区间的个数，最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了
    2. 如何去找非交叉区间的个数？
      1. 找重叠的最小右边界，判断下一个区间的左边是否大于这个区间，如果大于，说明这个是非交叉区间，count++
  15. 划分字母区间
    1. 遍历的过程相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是就是分割点
      1. 统计每一个字符的最后出现的位置
      2. 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
  16. 合并区间
    1. 先排序，让所有相邻区间尽可能重叠在一起，然后分别处理重叠（挨着也算）和不重叠
    2. 注意，这个时候并不是这一个interval数组元素和上一个数组元素比较了，而是要跟result中新加的作比较
  17. 单调递增的数字
    1. 一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]–，然后strNum[i]给为9，得到暂时的一个最大的整数
    2. 但是需要注意确定从前向后遍历还是从后向前遍历
      1. 从前向后，更改了中间数字的大小后，容易打破已经遍历过去的与上一个数字的关系
      2. 从后向前，可以确保，更改之后，再次审判，最终是正确的。
  18. 监控二叉树
    1. 局部最优：让叶子节点的父节点安摄像头，所用摄像头最少。
    2. 整体最优：全部摄像头数量所用最少
    3. 思路：从底到上，先给叶子结点父节点放个摄像头，然后每隔两个节点放一个摄像头，直至二叉树头节点。
      1. 二叉树的遍历：后序遍历
      2. 如何隔两个节点放一个摄像头

        1. 节点的状态：0-本节点无覆盖；1-本节点有摄像头；2-本节点有覆盖

        2. 空节点应该是什么状态？–>应该是有覆盖的状态

          1. 如果该节点状态为无覆盖–>那么它的父节点也就是叶子结点就要放摄像头，不符合我们局部最优的策略。
          2. 如果该节点状态为有摄像头–>那么它的父节点也就是叶子结点就要放摄像头，但此时叶子结点的父节点就覆盖不到了，也不符合我们局部最优的策略

        3. 单层逻辑处理，根据从下层递归得到的左右孩子，判断本层节点的状态：

          1. 左右孩子都有覆盖，那么该节点应该是无覆盖的状态-0；
          2. 左右节点至少有一个无覆盖的情况，那么该节点就应该放摄像头-1；
          3. 左右节点至少有一个有摄像头，那么该节点状态就应该为有覆盖-2；
          4. 递归处理完后，如果头结点没有覆盖，那么最后的result++
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

本站由 Xylumina 使用 Stellar 1.30.0 主题创建。
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。

本"页面"访问 次 | 总访问 次 | 总访客 人