鏈接
https://leetcode-cn.com/problems/lemonade-change/description/
要求
在檸檬水?dāng)偵系旁牛恳槐瓩幟仕氖蹆r為 5 美元吩抓。
顧客排隊購買你的產(chǎn)品均函，（按賬單 bills 支付的順序）一次購買一杯氏义。
每位顧客只買一杯檸檬水杜顺，然后向你付 5 美元垢粮、10 美元或 20 美元。
你必須給每個顧客正確找零劲够，也就是說凈交易是每位顧客向你支付 5 美元震桶。
注意，一開始你手頭沒有任何零錢征绎。
如果你能給每位顧客正確找零蹲姐，返回 true ，否則返回 false 人柿。
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里柴墩，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里凫岖，我們收取一張 10 美元的鈔票江咳，并返還 5 美元。
第 5 位顧客那里隘截，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票扎阶。
由于所有客戶都得到了正確的找零，所以我們輸出 true婶芭。
輸入：[5,5,10]
輸出：true
輸入：[10,10]
輸出：false
輸入：[5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那里东臀，我們按順序收取 2 張 5 美元的鈔票。
對于接下來的 2 位顧客犀农，我們收取一張 10 美元的鈔票惰赋，然后返還 5 美元。
對于最后一位顧客呵哨，我們無法退回 15 美元赁濒，因為我們現(xiàn)在只有兩張 10 美元的鈔票。
由于不是每位顧客都得到了正確的找零孟害，所以答案是 false拒炎。
思路
方法1：遍歷列表并用append,remove在新的列表中統(tǒng)計手中剩下的錢數(shù)。找不開則返回False挨务。
方法2：和方法1類似击你，但是改用Dict統(tǒng)計。
實踐證明Dict的效率要高出很多谎柄。
代碼
方法1：892 ms
class Solution(object):
def lemonadeChange(self, bills):
bills_list = []
while bills:
bills_pop = bills.pop(0)
if bills_pop == 5:
bills_list.append(5)
elif bills_pop == 10:
if 5 in bills_list:
bills_list.remove(5)
bills_list.append(10)
else:
return False
elif bills_pop == 20:
if 5 in bills_list and 10 in bills_list:
bills_list.remove(5)
bills_list.remove(10)
bills_list.append(20)
elif bills_list.count(5) > 2:
bills_list.remove(5)
bills_list.remove(5)
bills_list.remove(5)
bills_list.append(20)
else:
return False
else:
return True
方法2：40 ms
class Solution(object):
def lemonadeChange(self, bills):
bills_dict = {'bills5': 0, 'bills10': 0, 'bills20': 0}
for bill in bills:
if bill == 5:
bills_dict['bills5'] += 1
elif bill == 10:
if bills_dict['bills5'] > 0:
bills_dict['bills5'] -= 1
bills_dict['bills10'] += 1
else:
return False
elif bill == 20:
if bills_dict['bills5'] > 0 and bills_dict['bills10'] > 0:
bills_dict['bills5'] -= 1
bills_dict['bills10'] -= 1
bills_dict['bills20'] += 1
elif bills_dict['bills5'] > 2:
bills_dict['bills5'] -= 3
bills_dict['bills20'] += 1
else:
return False
else:
return True
