devbox
数据流舞者
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

LeetCode——贪心算法总结_贪心算法 leetcode

作者：数据流舞者 | 2024-01-31 14:18:18

赞

踩

贪心算法 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。

  1. package 计算机程序算法分类.贪心算法问题;
  2.  
  3. /**
  4.  * @Classname 柠檬水找零
  5.  * @Description TODO
  6.  * @Date 2021/5/17 10:04
  7.  * @Created by xjl
  8.  */
  9. public class 柠檬水找零 {
  10.     public boolean lemonadeChange(int[] biils){
  11.         //停机的店员拥有的5和10的数据量 不用统计的20的 因为不会需要找人家20的元 就是的没有比20大的钱
  12.         int five=0,ten=0;
  13.         for (int bill:biils){
  14.             if (bill==5){
  15.                 //如果顾客使用的是5块的不需要找零 数量加1就行
  16.                 five++;
  17.             }else if (bill==10){
  18.                 //如果是10需要找5块 所以是的5的数量减1 10的数量加1
  19.                 five--;
  20.                 ten++;
  21.             }else if (ten>0){
  22.                 //否则是的我们需要的是减少10 和5块的各一个
  23.                 ten--;
  24.                 five--;
  25.             }else {
  26.                 //否则是的如果两个都没有的话的 那就是的减少三个的5块的
  27.                 five-=3;
  28.             }
  29.             
  30.             if (five<0){
  31.                 //直接判断的5元的数量的 如果是5元的数量是小于0 的话 那么就没法给顾客找零了那就是的返回是false 
  32.                 return false;
  33.             }
  34.         }
  35.         return true;
  36.     }
  37. }

455. 分发饼干

 

 

322. 零钱兑换

可以看出在进行递归的时候，有很多重复的节点要进行操作，这样会浪费很多的时间。使用数组 memo[ ] 来保存节点的值，memo[n]表示钱币 nnn 可以被换取的最少的硬币数，不能换取就为 −1，findWay 函数的目的是为了找到 amount 数量的零钱可以兑换的最少硬币数量，返回其值 int，在进行递归的时候，memo[n]被复制了，就不用继续递归了，可以直接的调用 。

  1. /**
  2.  * Copyright (C), 2018-2020
  3.  * FileName: 零钱兑换
  4.  * Author:   xjl
  5.  * Date:     2020/9/13 14:28
  6.  * Description:
  7.  */
  8. package 计算机程序算法分类.贪心算法问题;
  9.  
  10. public class 零钱兑换 {
  11.     int[] memo;//在进行递归的时候，memo[n]被复制了，就不用继续递归了，可以直接的调用
  12.  
  13.     public int coinChange(int[] coins, int amount) {
  14.         if (coins.length == 0) {
  15.             return -1;
  16.         }
  17.         memo = new int[amount];
  18.  
  19.         return findWay(coins, amount);
  20.     }
  21.  
  22.     // memo[n] 表示钱币n可以被换取的最少的硬币数，不能换取就为-1
  23.     // findWay函数的目的是为了找到 amount数量的零钱可以兑换的最少硬币数量，返回其值int
  24.     public int findWay(int[] coins, int amount) {
  25.         if (amount < 0) {
  26.             return -1;
  27.         }
  28.         if (amount == 0) {
  29.             return 0;
  30.         }
  31.         // 记忆化的处理，memo[n]用赋予了值，就不用继续下面的循环
  32.         // 直接的返回memo[n] 的最优值
  33.         if (memo[amount - 1] != 0) {
  34.             return memo[amount - 1];
  35.         }
  36.         int min = Integer.MAX_VALUE;
  37.         for (int i = 0; i < coins.length; i++) {
  38.             int res = findWay(coins, amount - coins[i]);
  39.             if (res >= 0 && res < min) {
  40.                 min = res + 1; // 加1，是为了加上得到res结果的那个步骤中，兑换的一个硬币
  41.             }
  42.         }
  43.         memo[amount - 1] = (min == Integer.MAX_VALUE ? -1 : min);
  44.         return memo[amount - 1];
  45.     }
  46. }

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

  1. class Solution {
  2.     public int coinChange(int[] coins, int amount) {
  3.         // 自底向上的动态规划
  4.         if(coins.length == 0){
  5.             return -1;
  6.         }
  7.  
  8.         // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
  9.         int[] memo = new int[amount+1];
  10.         // 给memo赋初值，最多的硬币数就是全部使用面值1的硬币进行换
  11.         // amount + 1 是不可能达到的换取数量，于是使用其进行填充
  12.         Arrays.fill(memo,amount+1);
  13.         memo[0] = 0;
  14.         for(int i = 1; i <= amount;i++){
  15.             for(int j = 0;j < coins.length;j++){
  16.                 if(i - coins[j] >= 0){
  17.                     // memo[i]有两种实现的方式，
  18.                     // 一种是包含当前的coins[i],那么剩余钱就是 i-coins[i],这种操作要兑换的硬币数是 memo[i-coins[j]] + 1
  19.                     // 另一种就是不包含，要兑换的硬币数是memo[i]
  20.                     memo[i] = Math.min(memo[i],memo[i-coins[j]] + 1);
  21.                 }
  22.             }
  23.         }
  24.  
  25.         return memo[amount] == (amount+1) ? -1 : memo[amount];
  26.     }
  27. }

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. 组合总和 Ⅳ

  1. class Solution {
  2.  
  3.     public int change(int amount, int[] coins) {
  4.  
  5.         int n = coins.length;
  6.         int[][] dp = new int[n + 1][amount + 1];
  7.  
  8.         for (int i=0;i<=n;i++) {
  9.  
  10.             dp[i][0] = 1;
  11.         }
  12.  
  13.         for (int i=1;i<=n;i++) {
  14.  
  15.             for (int j=1;j<=amount;j++) {
  16.  
  17.                 if (j < coins[i - 1]) {
  18.  
  19.                     dp[i][j] = dp[i - 1][j]; 
  20.                 } else {
  21.  
  22.                     dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]];
  23.                 }
  24.             }
  25.         }
  26.         return dp[n][amount];
  27.     }
  28. }

 330. 按要求补齐数组

 

 

 

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/article/detail/50736?site
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号