贪心算法

理论基础

本质是：每一个阶段选择局部最优，从而打到所谓的全局最优，即为贪心

例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？

指定每次拿最大的，最终结果就是拿走最大数额的钱。

每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。

再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划

刷题或者面试的时候，手动模拟一下感觉可以局部最优推出整体最优，而且想不到反例，那么就试一试贪心。

例如刚刚举的拿钞票的例子，就是模拟一下每次拿做大的，最后就能拿到最多的钱，这还要数学证明的话，其实就不在算法面试的范围内了，可以看看专业的数学书籍！

贪心解题的一般步骤

  • 将问题分解为若干个子问题
  • 找出合适的贪心策略
  • 求解每一个问题的最优解
  • 将局部最优解堆叠成全局最优解

455.分发饼干

大饼干先满足大胃口的，局部最优解到全局最优解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int index = s.length - 1;
        for (int i = g.length - 1; i >= 0; i--) {
            if (index >= 0 && s[index] >= g[i]) {
                count++;
                index--;
            }
        }
        return count;
    }
}

注意的是，if (index >= 0 && s[index] >= g[i]) 这里，一定要是index在&& 的前面，因为要保证s[index]数组补不为null

376.摆动序列

贪心：局部最优：找到局部波动的峰值，结果++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int wiggleMaxLength(int[] nums) {
        int l = nums.length;
        int pre = 0;// 当前差值
        int post = 0;// 上一个差值
        int ans = 1;
        for (int i = 1; i < l; i++) {
            pre = nums[i] - nums[i - 1];
            if ((pre < 0 && post >= 0) || (pre > 0 && post <= 0)) {
                ans++;
                post = pre;
            }
        }
        return ans;
    }
}

if中的判断条件，为什么一定要是上一个差值包含等于0的情况？

我调试了好久

  1. (last >= 0 && pre < 0)：这部分判断条件表示上一个差值为非负（大于等于0），而当前差值为负（小于0）。这说明了当前差值由正数变为了负数，即发生了一次从上升到下降的转折点。
  2. (last <= 0 && pre > 0)：这部分判断条件表示上一个差值为非正（小于等于0），而当前差值为正（大于0）。这说明了当前差值由负数变为了正数，即发生了一次从下降到上升的转折点。

在摆动序列中，我们希望找到一系列交替出现的峰值和谷值，因此需要判断当前差值和上一个差值的符号是否发生了变化。取等号的目的是为了确保在连续相同差值时不计数，因为连续相同的差值并不会对序列的摆动性产生影响。

为什么不能是if ((last > 0 && pre <= 0) || (last < 0 && pre >= 0)) ？
我们初始last是＝0的，如果这样写，判断条件一直为false了