贪心算法理论基础

  • 贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
  • 解题步骤：
    • 将问题分解为若干个子问题
    • 找出适合的贪心策略
    • 求解每一个子问题的最优解
    • 将局部最优解堆叠成全局最优解

      Leetcode 455.分发饼干

      题目：455.分发饼干

初始思路

大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

代码

  1. var findContentChildren = function (g, s) {
  2.     // 从大到小排序
  3.     g = g.sort((a, b) => a - b)
  4.     s = s.sort((a, b) => a - b)
  5.     let res = 0
  6.     // 指向饼干数组的最后一个
  7.     let index = s.length - 1
  8.     // 从大到小遍历胃口
  9.     for (let i = g.length - 1; i >= 0; i--){
  10.         // 如果满足胃口
  11.         if (index >= 0 && s[index] >= g[i]) {
  12.             res++
  13.             index--
  14.         }
  15.     }
  16.     return res
  17. };

感想

  1. 简单题，贪心入门。

Leetcode 376.摆动序列

题目：376.摆动序列

初始思路

保持区间波动，只需要把单调区间上的元素移除就可以了。

代码

  1. var wiggleMaxLength = function (nums) {
  2.     if (nums.length <= 1) return nums.length
  3.     // 序列默认最右边有一个峰值
  4.     let res = 1
  5.     // 前一对的差值
  6.     let preDiff = 0
  7.     // 当前一对的差值
  8.     let curDiff = 0
  9.     for (let i = 0; i < nums.length - 1; i++){
  10.         curDiff = nums[i + 1] - nums[i]
  11.         if ((curDiff > 0 && preDiff <= 0) || (curDiff < 0 && preDiff >= 0)) {
  12.             // 如果出现一个峰值
  13.             res++
  14.             preDiff = curDiff
  15.         }
  16.     }
  17.     return res
  18. };

感想

  1. 局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
  2. 整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列
  3. 实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）

  4. image.png

Leetcode 53.最大子数组和

题目：53.最大子数组和

初始思路

代码

  1. var maxSubArray = function (nums) {
  2.     let res = -Infinity
  3.     let count = 0
  4.     for (let i = 0; i < nums.length; i++){
  5.         count += nums[i]
  6.         // 更新结果
  7.         if (count > res) {
  8.             res = count
  9.         }
  10.         // 一旦小于0就从新开始寻找区间
  11.         if (count < 0) {
  12.             count = 0
  13.         }
  14.     }
  15.     return res
  16. }

感想

  1. 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
  2. 全局最优：选取最大“连续和”
  3. 从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。
  4. 这相当于是暴力解法中的不断调整最大子序和区间的起始位置。