柠檬水找钱-lemonadeChange

本文主要是介绍柠檬水找钱-lemonadeChange，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例 1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例 2：

输入：[5,5,10]
输出：true

示例 3：

输入：[10,10]
输出：false

示例 4：

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

提示：

0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20

Related Topics 贪心算法

解题思路

算法思路：
收录钱的时候，对当前的数字-5进行判断！
1、剩下的数字和大于该数字-5
2、且有5，10，20这样的数字组成才可以

代码：

class Solution {public boolean lemonadeChange(int[] bills) {//根据题意，营业员没有零钱，第一位顾客的钱如果大于5则直接返回falseif(bills[0]>5)return false;//营业员处金额int totalmoney=0;//用于存放营业员处 5、10、20 的个数Map<Integer,Integer> map=new HashMap<>();int num=5;//将5，10，20录入到map中for (int i = 0; i < 3; i++) {map.put(num,0);num=num*2;}int k,n;//判断当前顾客金额是否可以找开for(int i=0;i<bills.length;i++){//条件一如果不满足，直接返回falseif(totalmoney<bills[i]-5)return false;//条件二的判断//如果是5元，直接收入if(bills[i]==5){k=map.get(5);++k;map.put(bills[i],k);}else if(bills[i]==10){if(map.get(5)==0)return false;k=map.get(10);map.put(10,++k);n=map.get(5);map.put(5,--n);}else{if(map.get(10)>0&&map.get(5)>0){k=map.get(10);map.put(10,--k);n=map.get(5);map.put(5,--n);}else if(map.get(5)>2){n=map.get(5)-3;map.put(5,n);}elsereturn false;}totalmoney+=5;}return true;}
}

这篇关于柠檬水找钱-lemonadeChange的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---