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 美团的钞票数量, 然后遍历一遍根据上述条件分别判断即可。
代码 #
|
|