柠檬水找零

发表于
本文字数： 1.6k 阅读时长 ≈ 1 分钟

LeetCode每日一题，860. Lemonade Change

先看题目描述

rPODOS.png

题目大意就是给定一个数组 bills 代表顾客来购买柠檬水所会支付的钱的面额，一杯柠檬水的价格是 5 美元，商家一开始是没有零钱的，顾客支付的钱的面额有 5 美元，10 美元和 20 美元，让我们根据数组 bills 判断商家是否对于每个顾客都有足够的零钱来找零

算法和思路

模拟+贪心

这题很简单，对于顾客支付的钱的面额的三种情况进行不同处理即可，定义两个变量 count5 和 count10 来维护商家目前手上有的 5 美元零钱和 10 美元零钱数量即可，初始化 count5 和 count10 等于 0

  • 若顾客支付 5 美元，则不用找零，直接将 count5 加 1 即可
  • 若顾客支付 10 美元，则要找零 5 美元，若此时 count5 等于 0，说明商家的钱不够找零，返回 false；若 count5 大于 0，则能够找零，将 count5 - 1，count10 + 1
  • 若顾客支付 20 美元，则要找零 15 美元，此时有两种组合方式，一种是一张 10 美元和 5 美元的钞票，另一种是三张 5 美元的钞票。此处采用贪心算法，贪心策略是优先采用第二种组合方式，第二种组合方式不行的话才考虑第一种组合方式。若 cout10 和 count5 均大于 0，说明可以采用第二种组合方式，将 count5 - 1，count10 - 1；若第二种组合方式不行的话，则考虑第一种组合方式，此时 count5 大于 2 的话就可以采用第一种组合方式，将 count5 - 3；否则，说明两种组合方式都不行，商家的钱不够找零，返回 false

若遍历完 bills 后，商家都可以找零，则返回 true

算法源码

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
class Solution {
    public boolean lemonadeChange(int[] bills) {
        int count5 = 0;
        int count10 = 0;
        for (int bill : bills) {
            if (bill == 5) {
                count5++;
            } else if (bill == 10) {
                if (count5 == 0) {
                    return false;
                }
                count10++;
                count5--;
            } else {
                if (count10 > 0 && count5 > 0) {
                    count5--;
                    count10--;
                } else if (count5 >= 3) {
                    count5 = count5 - 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}