力扣860题python解法

题目描述

柠檬水找零：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一个。

每位顾客只买一杯柠檬水，然后向你支付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false

示例 1：

输入：[5,5,5,10,20]

输出：true

解释：

前 3 位顾客那里分别支付了 5 美元。

第 4 位顾客那里支付了 10 美元，接下来是两个 5 美元。

第 5 位顾客那里支付了 20 美元，接下来是 15 美元， 无法提供且返回false。

示例 2：

输入：[5,5,10]

输出：true

示例 3：

输入：[10,10]

输出：false

示例 4：

输入：[5,5,10,10,20]

输出：false

解题思路

使用两个变量 five 和 ten 分别表示手头上的 5 美元钞票和 10 美元钞票的数量。从前往后遍历数组，根据顾客支付的钞票进行分类讨论：

如果顾客支付 5 美元，收入 5 美元钞票一个。
如果顾客支付 10 美元，需要找回一张 5 美元钞票，收入 10 美元钞票一张和减去一张 5 美元钞票。
如果顾客支付 20 美元，优先找回一张 10 美元和一张 5 美元，如果没有再找回三张 5 美元，否则收入不够减，返回 false。

算法流程

遍历 bills，记当前手上拥有的 5 美元张数 five 和 10 美元张数 ten 的数量，初始值为 0。
判断 bills[i] 的大小+0、+5 还是+15，并更新 five 和 ten 的数量。

代码实现

class Solution(object):
def lemonadeChange(self, bills):
"""
:type bills: List[int]
:rtype: bool
"""
five, ten = 0, 0
for bill in bills:
if bill == 5:
five += 1
elif bill == 10:
if not five:
return False
five -= 1
ten += 1
else:
if ten and five:
ten -= 1
five -= 1
elif five >= 3:
five -= 3
else:
return False
return True