算法通关村第十七关|青铜|贪心：无招胜有招

贪心常见的经典应用场景：

● 排序问题：选择排序，拓扑排序
● 优先队列：堆排序
● 赫夫曼压缩编码
● 图：Prim Fruskal Dijkstra 算法
● 硬币找零问题
● 分数背包问题
● 并查集：按大小或者高度合并问题或者排名
● 任务调度部分场景
● 一些复杂问题的近似算法

1.分发饼干

原题：力扣455.

贪心策略就是将两个数组排序，然后遍历小孩数组，优先用大饼干喂给胃口大的小孩。

这里的 g 是胃口数组， s 是饼干数组

public int findContentChildren(int[] g, int[] s) {
	Arrays.sort(g);
    Arrays.sort(s);
    int count = 0;
    int start = s.length - 1;
    for (int index = g.length - 1; index >= 0; index--) {
        if (start >= 0 && g[index] <= s[start]) {
            start--;
            count++;
        }
    }
    return count;
}

2.柠檬水找零

原题：力扣860.

分析收钱情况：

● 如果给 5 元，直接收下
● 如果给 10 元，收下 10 元，找零 5 元
● 如果给 20 元，收下 20 元，找零 10 元和 5 元或者三个 5 元

第二种情况下必须有 5 元才能找零。

第三种情况下优先找零 10 元，然后再找零 5 元，因为 5 元可以用在第二种和第三种情况，而 10 元只能用在第三种情况下。

代码直接列举情况就好了。

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;
}

3.分发糖果

原题：力扣135.

需要注意，相邻的两个孩子的评分相同的时候，就不存在一个比另一个大的情况了，那么就不需要考虑糖果分配，只需给其中一个孩子分配 1 个基本糖果即可。

public int candy(int[] ratings) {
	int[] candyVec = new int[ratings.length];
    candyVec[0] = 1;
    // 先从左到右遍历一次
    for (int i = 1; i < ratings.length; i++) {
        if (rating[i] > ratings[i - 1]) {
            candyVec[i] = candyVec[i - 1] + 1;
        } else {
            // 相等的时候也赋值 1
            candyVec[i] = 1;
        }
    }
    // 再从右向左遍历一次
    for (int i = ratings.length - 2; i >= 0; i--) {
        if (ratings[i] > ratings[i + 1]) {
            candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
        }
    }
    int ans = 0;
    for (int s : candyVec) {
        ans += s;
    }
    return ans;
}

如果对您有帮助，请点赞关注支持我，谢谢！?
如有错误或者不足之处，敬请指正！?
个人主页：星不易 ?
算法通关村专栏：不易|算法通关村 ?