贪心---柠檬水找零 Posted on 2021-08-13 00:00:00 2021-08-13 00:00:00 by Author 摘要 夏天太阳很大，你要忍一下，隔壁小摊的老板在卖冰镇 柠檬水，大家快去买杯冰镇柠檬水吧，不过去的时候记得带上现金啊，因为老板只收现金，不支持电子支付哦！！！ # 贪心---柠檬水找零 1. 题目描述 - 在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。 - 每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。注意，一开始你手头没有任何零钱。给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。 - **提示：** - `1 <= bills.length <= 105` - `bills[i]` 不是 `5` 就是 `10` 或是 `20` 2. 示例描述 - 示例一 ```java 输入：bills = [5,5,5,10,20] 输出：true 解释： 前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。 第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零，所以我们输出 true。 ``` - 示例二 ```java 输入：bills = [5,5,10,10,20] 输出：false 解释： 前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。 对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零，所以答案是 false。 ``` 3. 解题思路 - 这道题是一道非常简单的题目，只要逻辑与思路清楚，解决这道题完全没有问题。 - 这里思路基本上都是，遇到一个顾客如果他/她付款5美元，那么不用找零，存下5美元，直接下一位顾客，如果该为客户付款10美元，那么看看之前有没有5美元的现金，如果有找零5美元，存下10美元。如果没有10美元，那么就不能正确的找零了，返回false。这两种情况大家都能想到。但是如果顾客付了20美元的话，我们找零有两种选择，一种就是找3张5美元的，还有一张就是找一张10美元的还有一张5美元的(前提是10美元和5美元的数量能够找零的情况下)。那么这里如何选择尼，那当然是选择一张10美元和一张5美元的啊，为什么这么选尼，因为5美元数量越多，到后面更容易找零，而且5美元在本题中是万能的。 - 其实这道题能够很容易解决，当解决之后，可以仔细反过来想想，这道题有贪心思想在里面，局部最优：遇到账单20，优先消耗美元10，留着更多的5美元数量，以便后期的找零。全局最优：争取留着更多的5美元，使全部顾客都能够正确找零，完成全部账单的找零。 - 本题的实现思路如下，思想很简单，就是有太多的判断条件了，但是如果思路与逻辑很清楚，那么对于写代码来说，就非常容易了。 4. 代码示例 ```java public boolean lemonadeChange(int[] bills) { //下标0代表5美元数量 //下标1代表10美元数量 //下标2代表20美元数量 int sum[]=new int[3]; //如果没人买，就返回true if(bills.length<=0){ return true; } //如果第一个人付的不是5美元，返回false if(bills[0]!=5){ return false; } //初始化，5美元，10美元，20美元都没有 for(int i=0;i<sum.length;i++){ sum[i]=0; } //循环遍历整个账单数组 for(int i=0;i<bills.length;i++){ //如果该顾客付了5美元 if(bills[i]==5){ //5美元数量加一 sum[0]++; //继续下一个顾客 continue; } //如果付了10美元 if(bills[i]==10){ //有5美元的话，就支付5美元 if(sum[0]!=0){ //5美元个数减一， sum[0]--; //10美元数量加一 sum[1]++; continue; } //否则不能找零，直接返回false else { return false; } } //如果支付的是20美元 if(bills[i]==20){ //如果有19美元 if(sum[1]!=0){ //并且有5美元 if(sum[0]!=0) { //支付10美元 sum[1]--; //支付5美元 sum[0]--; //20美元数量加一 sum[2]++; continue; } //有10美元，美元5美元，就不能找零，直接返回false if(sum[0]==0){ return false; } } //如果美元10美元 if(sum[1]==0){ //如果有大于等于三张5美元的数量 if(sum[0]>=3){ //找零3张5美元的 sum[0]-=3; //20美元的数量加一 sum[2]++; } //5美元数量小于3，且没有一张10美元的，直接返回false else{ return false; } } } } //都能正确找零，返回true return true; } ```
{{ item.content }}
{{ child.content }}