算法通关村第十七关—贪心其实很简单(青铜)

??贪心其实很简单

一、贪心问题举例

1.1 分发饼干

?LeetCode455,分发饼干：假设你要给孩子们一些小饼干。但是每个孩子最多只能给一块饼干。每个孩子的饭量不同，对每个孩子ⅰ，都有一个胃口值9[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干j,都有一个尺寸s[j]。如果s[j]>=g[i]，我们可以将这个饼干j分配给孩子ⅰ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。示例：
其中g是胃口，s是拥有的饼干。

输入：g=[1,2,3],s=[1,1]
输出：1
解释：
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

?首先对g和s进行排序。然后从小到大遍历g中的每一个元素，对于每个元素找到能满足该元素的s中的最小元素。整个过程只需要对数组 g 和 s 各遍历一次。当两个数组之一遍历结束时，说明所有的孩子都被分配到了饼干，或者所有的饼干都已经被分配或被尝试分配（可能有些饼干无法分配给任何孩子），此时被分配到饼干的孩子数量即为可以满足的最多数量。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int p1 = 0,p2 = 0;
        for(p1 =0; p1 < g.length; p1++){
            while(p2 < s.length && g[p1] > s[p2]){
                p2++;
            }
            if(p2 >= s.length) break;
            p2++;
        }
        return p1;
    }
}

1.2 柠檬水找零

?LeetCode860,在柠檬水摊上，每一杯柠檬水的售价为5美元。顾客排队购买你的产品，（按账单s支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付5美元、10美元或20美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付5美元。
?注意，一开始你手头没有任何零钱。给你一个整数数组bils,其中bils[i]是第ⅰ位顾客付的账。如果你能给每位顾客正确找零，返回true,否则返回false。

?这个题描述有点啰嗦，但是根据示例，不难看懂。这个题给小学生是不是也会做呢？然后当我们分析如何用代码实现时会有点懵，其实主要有三种情况：
1.如果给的是5，那么直接收下。
2.如果给的是10元，那么收下一个10，给出一个5，此时必须要有一个5才行。
3.如果给的是20，那么优先消耗一个10元，再给一个5元。假如没有10元，则给出3个5元。
?上面的情况3里，有10就先给10，没有才给多个5，这就是贪心选择的过程。为什么要优先消耗一个10和一个5呢？小学生都知道因为10只能给账单20找零，而5可以给账单10和账单20找零，5更万能！所以这里的局部最优就是遇到账单20，优先消耗美元10，完成本次找零。
这就是局部最优可以推出全局最优，题解代码如下：

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0, ten = 0;
        for (int bill : bills) {
            if (bill == 5) {
                five++;
            } else if (bill == 10) {
                if (five == 0) {
                    return false;
                }
                five--;
                ten++;
            } else {
                if (five > 0 && ten > 0) {
                    five--;
                    ten--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

自己写的代码如下

class Solution {
    public boolean lemonadeChange(int[] bills) {
        Map<Integer, Integer> map = new HashMap<>();
        map.put(5, 0);
        map.put(10, 0);
        for(int i = 0; i < bills.length; i++){
            if(bills[i] == 5) map.put(5, map.get(5) + 1);
            if(bills[i] == 10){
                map.put(10, map.get(10) + 1);
                map.put(5, map.get(5) - 1);
                if(map.get(5) < 0) return false;
            }
            if(bills[i] == 20){
                map.put(5, map.get(5) - 1);
                if(map.get(10) == 0) map.put(5, map.get(5) - 2);
                else map.put(10, map.get(10) - 1);
                if(map.get(5) < 0 || map.get(10) < 0) return false;
            }
        }
        return true;
    }
}

1.3 分发糖果

?LeetCode135：n个孩子站成一排。给你一个整数数组ratings表示每个孩子的评分。你需要按照以下要求，给这些孩子分发糖果，并返回需要准备的最少糖果数目：
1.每个孩子至少分配到1个糖果。
2.相邻两个孩子评分更高的孩子会获得更多的糖果。

示例1：
输入：ratings=[1,0,2]
输出：5
解释：
你可以分别给第一个、第二个、第三个孩子分发2、1、2颗糖果。
示例2：
输入：ratings=[1,2,2]
输出：4
解释：
你可以分别给第一个、第二个、第三个孩子分发1、2、1颗糖果。
第三个孩子只得到1颗糖果，这满足题面中的两个条件。

代码如下

class Solution {
    public int candy(int[] ratings) {
        int sum = 0;
        int[] nums = new int[ratings.length];
        for(int i = 0; i < ratings.length; i++){ //从左往右遍历
            if(i == 0) nums[0] = 1;
            else if(ratings[i - 1] < ratings[i]){
                nums[i] = nums[i - 1] + 1;
            }
            else nums[i] = 1;
        }
        for(int i = ratings.length - 2; i >= 0; i--){ //从右往左遍历，每次取两次遍历的最大值
            if(ratings[i] > ratings[i + 1]){
                nums[i] = Math.max(nums[i], nums[i + 1] + 1);
            }
        }
        for(int num : nums){ //计算总数
            sum += num;
        }
        return sum;
    }
}