LeetCode——贪心算法总结

贪心算法的主要的解题目的思路是：

 

860. 柠檬水找零

这道题算是生活中很常见的一道题，对于每一个顾客如果我们都有足够的零钱给他找零，那么就返回true，只要有一个顾客没有足够的零钱找给他就返回false。顾客只能有3种纸币，5元，10元，20元。我们要统计5元和10元的数量，20元的不需要统计，因为20元没法找给别人。

顾客给5元，5元的数量加1

顾客给10元，5元的数量减1（减完之后再判断5元的数量，如果小于0，说明5元的不够了，没法给顾客找零了，直接返回false)

顾客给20元，根据生活常识，如果有10元的，应该先找他10元的，然后再找他一个5元的。如果没有10元的就找他3个5元的，然后再判断5元的数量，如果小于0直接返回false。

package 计算机程序算法分类.贪心算法问题;

/**
 * @Classname 柠檬水找零
 * @Description TODO
 * @Date 2021/5/17 10:04
 * @Created by xjl
 */
public class 柠檬水找零 {
    public boolean lemonadeChange(int[] biils){
        //停机的店员拥有的5和10的数据量 不用统计的20的 因为不会需要找人家20的元 就是的没有比20大的钱
        int five=0,ten=0;
        for (int bill:biils){
            if (bill==5){
                //如果顾客使用的是5块的不需要找零 数量加1就行
                five++;
            }else if (bill==10){
                //如果是10需要找5块 所以是的5的数量减1 10的数量加1
                five--;
                ten++;
            }else if (ten>0){
                //否则是的我们需要的是减少10 和5块的各一个
                ten--;
                five--;
            }else {
                //否则是的如果两个都没有的话的 那就是的减少三个的5块的
                five-=3;
            }
            
            if (five= 0 && res < min) {
                min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
            }
        }
        memo[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);
        return memo[amount - 1];
    }
}

另一种实现：memo[i]有两种实现的方式，去两者的最小值，包含当前的 coins[i]，那么剩余钱就是 i−coins[i]，这种操作要兑换的硬币数是 memo[i−coins[j]]+1，不包含，要兑换的硬币数是 memo[i]。

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }

        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount+1];
        // 给memo赋初值，最多的硬币数就是全部使用面值1的硬币进行换
        // amount + 1 是不可能达到的换取数量，于是使用其进行填充
        Arrays.fill(memo,amount+1);
        memo[0] = 0;
        for(int i = 1; i = 0){
                    // memo[i]有两种实现的方式，
                    // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
                    // 另一种就是不包含，要兑换的硬币数是memo[i]
                    memo[i] = Math.min(memo[i],memo[i-coins[j]] + 1);
                }
            }
        }

        return memo[amount] == (amount+1) ? -1 : memo[amount];
    }
}

518. 零钱兑换 II

这里就是的一个完全的背包问题的。请一定要去的理解的背包问题的相关的解答和变式。背包问题的视频：https://www.bilibili.com/video/BV1K4411X766?from=search&seid=11709794381262748318，https://www.cnblogs.com/mfrank/p/10803417.html

416. 分割等和子集

494. 目标和

322. 零钱兑换

518. 零钱兑换 II

377. 组合总和 Ⅳ

class Solution {

    public int change(int amount, int[] coins) {

        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];

        for (int i=0;i