算法通关村——原来贪心如此简单

贪心问题举例

贪心不一定能够达到最效的解法，但是一般情况下可以到达最优解法。

更多的情况下，我们不需要太过于考虑所谓的贪心解法。

零钱兑换

入手解决问题，我们可以通过这个案例来了解一下，所谓的「贪心」到底是怎么回事。

    /* 零钱兑换：贪心 */
    int coinChangeGreedy(int[] coins, int amt) {
        // 假设 coins 列表有序
        int i = coins.length - 1;
        int count = 0;
        // 循环进行贪心选择，直到无剩余金额
        while (amt > 0) {
            // 找到小于且最接近剩余金额的硬币
            while (i > 0 && coins[i] > amt) {
                i--;
            }
            // 选择 coins[i]
            amt -= coins[i];
            count++;
        }
        // 若未找到可行方案，则返回 -1
        return amt == 0 ? count : -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

分发饼干

455. 分发饼干 Easy

为什么要遍历学生的胃口 ？

因为我们需要找到最合适的分给合适的学生，更主要的就是因为我们学生的窗口可以进行遍历到对应的说需要的值

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int count = 0;
        int start = s.length - 1;
        // 遍历学生的胃口 
        for (int idnex = g.length - 1; idnex >= 0; idnex--) {
            if (start >= 0 && g[idnex] <= s[start]) {
                start--;
                count++;
            }
        }
        return count;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

柠檬水找零

柠檬水找零 Easy

1. 当我们收到的是 5 那么可以没什么问题
2. 如果我们收入到的是 10 那么需要返还 5
3. 如果我们收入到的是 20 那么我们需要返回 15 这个可以有两种构成 10 + 5 和 三个 5

通过上面的分析，我们发现 5 可以应用的常见比 10 多那么 5 就是优先被保存的那个

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int cash_5 = 0;
        int cash_10 = 0;
        for (int i = 0; i < bills.length; i++) {
            if (bills[i] == 5) {
                cash_5++;
            } else if (bills[i] == 10) {
                cash_5--;
                cash_10++;
            } else if (bills[i] == 20) {
                if (cash_10 > 0) {
                    cash_10--;
                    cash_5--;
                } else {
                    cash_5 -= 3;
                }
            }
            if (cash_5 < 0 || cash_10 < 0) return false;
        }    
        return true;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23