1. question: 柠檬水找零(简单)
在柠檬水摊上,每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品,(按账单 bills 支付的顺序)一次购买一杯。
每位顾客只买一杯柠檬水,然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零,也就是说净交易是每位顾客向你支付 5 美元。
注意,一开始你手头没有任何零钱。
给你一个整数数组 bills ,其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零,返回 true ,否则返回 false 。
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/lemonade-change
示例 1:
1 2 3 4 5 6 7
| 输入:bills = [5,5,5,10,20] 输出:true 解释: 前 3 位顾客那里,我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里,我们收取一张 10 美元的钞票,并返还 5 美元。 第 5 位顾客那里,我们找还一张 10 美元的钞票和一张 5 美元的钞票。 由于所有客户都得到了正确的找零,所以我们输出 true。
|
示例 2:
1 2 3 4 5 6 7
| 输入:bills = [5,5,10,10,20] 输出:false 解释: 前 2 位顾客那里,我们按顺序收取 2 张 5 美元的钞票。 对于接下来的 2 位顾客,我们收取一张 10 美元的钞票,然后返还 5 美元。 对于最后一位顾客,我们无法退回 15 美元,因为我们现在只有两张 10 美元的钞票。 由于不是每位顾客都得到了正确的找零,所以答案是 false。
|
提示:
1 2
| 1 <= bills.length <= 105 bills[i] 不是 5 就是 10 或是 20
|
2. answers
这道题还是比较简单的,需要注意的是:
- 题目中只有三种面值,需要记录收入这三种金额的数量,方便后续使用。
- 金额越小的值,越能够找零,即作用越大。因为5无论是15还是5,都能找零。而10只能对15找零。因此,我们应该保留更多的金额小的值,也就是说,每次找零都优先选择大的。
遍历数组,模拟找零即可。代码如下所示:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51
| public class Solution_0102 {
public boolean lemonadeChange(int[] bills) {
Map<Integer, Integer> map = new HashMap<>(); map.put(5, 0); map.put(10, 0); map.put(20, 0);
for (int bill : bills) {
map.put(bill, map.get(bill) + 1);
int remain = bill - 5;
while (remain >= 10) {
if (map.get(10) < 1) break; map.put(10, map.get(10) - 1); remain -= 10; }
while (remain > 0) {
if (map.get(5) < 1) return false; map.put(5, map.get(5) - 1); remain -= 5; }
}
return true; }
public static void main(String[] args) { System.out.println();
Solution_0102 s = new Solution_0102();
int[] bills = {5, 5, 10, 10, 20};
System.out.println(s.lemonadeChange(bills)); } }
|
3. 备注
参考力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com),代码随想录 (programmercarl.com)。