算法训练营day28 | {455.分发饼干, 376.摆动序列, 53.最大子序和}

第八章贪心算法part01，想清楚贪在哪里，能否举出反例。

0. 理论基础

贪心算法没有固定的规律或套路，说白了就是常识性推导加上举反例。唯一的难点就是如何通过局部最优，推出整体最优。总之，刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。
题目分类

455. 分发饼干

1.1 解题分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 优先考虑胃口，先喂饱大胃口
        Arrays.sort(g);
        Arrays.sort(s);
        int cnt = 0;
        int start = s.length - 1;
        for (int i = g.length - 1; i >= 0; i--) {
            if (start >= 0 && s[start] >= g[i]) {
                start--;
                cnt++;
            }
        }
        return cnt;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        // 优先考虑饼干，小饼干先喂饱小胃口
        Arrays.sort(g);
        Arrays.sort(s);
        int cnt = 0;
        int start = 0;
        for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                cnt++;
                start++;
            }
        }
        return start;
    }
}

376. 摆动序列

2.1 解题分析

正常情况下判断有没有摆动：prediff < 0 && curdiff > 0 或者 prediff > 0 && curdiff < 0
正常情况

局部最优：删除单一坡度上的节点，让峰值尽可能的保持峰值。局部最优推出全局最优，并且举不出反例，试试贪心。但本题要考虑3种情况：

  1. 上下坡有平坡
  2. 数组只有首尾两个元素
  3. 单调坡中有平坡

  • 情况1：上下坡中平坡
    例如 [1,2,2,2,2,1]这样的数组
    如图，该数组的最长摆动序列是3，可以统一规则，删除左边的三个2，那么当 prediff = 0 && curdiff != 0时也要记录一个峰值，因此判断条件变为：

    • prediff <= 0 && curdiff > 0 或者 prediff >= 0 && curdiff < 0
    • result初始为1（默认数组的最右边的元素是一个峰值）。

  • 情况2：数组有首尾两个元素
    和情况一统一，假设第一个元素前还有一个一样的元素。

  • 情况3：单调坡中有平坡
    单调坡度有平坡
    这种情况下可以看出，我们不能实时更新prediff，只需要在这个坡度 摆动变化时才更新prediff。

2.2 解题小结

本题画出坡度图，分析出要计算prediff和curdiff之后，还需要进一步考虑有平坡的情况，包括上下中间有平坡、单调有平坡的情况。

  • 贪心算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    class Solution {
        public int wiggleMaxLength(int[] nums) {
            if (nums.length == 1) return 1;
            int result = 1;
            int preDiff = 0;
            int curDiff = 0;
            for (int i = 0; i < nums.length - 1; i++) {
                curDiff = nums[i + 1] - nums[i];
                if (preDiff >= 0 && curDiff < 0 || preDiff <= 0 && curDiff > 0) {
                    result++;
                    preDiff = curDiff;
                }
            }
            return result;
        }
    }

todo：动态规划解法

53. 最大子序和

3.1 解题分析

贪心算法，怎么想清楚贪的是哪里？局部最优在哪里？

  • 如果 -2 1 在一起，计算起点的时候，一定是从 1 开始计算，因为负数只会拉低总和，这就是贪心贪的地方！
  • 局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
  • 全局最优：选取最大“连续和”

3.2 解题小结

  • 贪心算法
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    class Solution {
        public int maxSubArray(int[] nums) {
            int count = 0;
            int result = Integer.MIN_VALUE;
            for (int i = 0; i < nums.length; i++) {
                count += nums[i];
                if (count > result) result = count;
                if (count < 0) count = 0;
            }
            return result;
        }
    }

todo：动态规划

4. 今日收获

  • 贪心算法难点在于想清楚怎么贪，贪在哪里，局部最优在哪里吧，经过53.最大子序和有一些感触了。
  • 学习时长：3小时