0860. 柠檬水找零

0860. 柠檬水找零 #

  • 标签:贪心、数组
  • 难度:简单

题目大意 #

一杯柠檬水的售价是 5 美元。现在有 N 个顾客排队购买柠檬水,每人只能购买一杯。顾客支付的钱面额有 5 美元、10 美元、20 美元。必须给每个顾客正确找零(就是每位顾客需要向你支付 5 美元,多出的钱要找还回顾客)。

现在给定 N 个顾客支付的钱币面额数组 bills,如果能给每位顾客正确找零,则返回 True,否则返回 False。

注意:一开始的时候手头没有任何零钱。

解题思路 #

由于顾客只能给我们 5、10、20 三种面额的钞票,且一开始我们手头没有任何钞票,所以我们手中所能拥有的钞票面额只能是 5、10、20。因此可以采取下面的策略。

  • 如果顾客支付 5 美元,直接收下。
  • 如果顾客支付 10 美元,如果我们手头有 5 美元面额的钞票,则找给顾客,否则无法正确找零,返回 False。
  • 如果顾客支付 20 美元,如果我们手头有 1 张 10 美元和 1 张 5 美元的钞票,或者有 3 张 5 美元的钞票,则可以找给顾客。如果两种组合方式同时存在,倾向于第 1 种方式找零,因为使用 5 美元的场景比使用 10 美元的场景多,要尽可能的保留 5 美元的钞票。如果这两种组合方式都不通知,则无法正确找零,返回 False。

所以,我们使用 five 和 ten 来维护手中 5 美元、10 美团的钞票数量, 然后遍历一遍根据上述条件分别判断即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five, ten, twenty = 0, 0, 0
        for bill in bills:
            if bill == 5:
                five += 1
            if bill == 10:
                if five <= 0:
                    return False
                ten += 1
                five -= 1
            if bill == 20:
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                    twenty += 1
                elif five >= 3:
                    five -= 3
                    twenty += 1
                else:
                    return False

        return True
本站总访问量  次  |  您是本站第  位访问者