題目
難度：★★☆☆☆
類型：數(shù)學(xué)
在檸檬水?dāng)偵?，每一杯檸檬水的售價(jià)為 5 美元。
顧客排隊(duì)購(gòu)買(mǎi)你的產(chǎn)品，（按賬單 bills 支付的順序）一次購(gòu)買(mǎi)一杯。
每位顧客只買(mǎi)一杯檸檬水，然后向你付 5 美元、10 美元或 20 美元。你必須給每個(gè)顧客正確找零，也就是說(shuō)凈交易是每位顧客向你支付 5 美元。
注意，一開(kāi)始你手頭沒(méi)有任何零錢(qián)。
如果你能給每位顧客正確找零，返回 true ，否則返回 false 。
提示
0 <= bills.length <= 10000
bills[i] 不是 5 就是 10 或是 20
示例
示例 1
輸入：[5,5,5,10,20]
輸出：true
解釋：
前 3 位顧客那里，我們按順序收取 3 張 5 美元的鈔票。
第 4 位顧客那里，我們收取一張 10 美元的鈔票，并返還 5 美元。
第 5 位顧客那里，我們找還一張 10 美元的鈔票和一張 5 美元的鈔票。
由于所有客戶都得到了正確的找零，所以我們輸出 true。
示例 2
輸入：[5,5,10]
輸出：true
示例 3
輸入：[10,10]
輸出：false
示例 4
輸入：[5,5,10,10,20]
輸出：false
解釋：
前 2 位顧客那里，我們按順序收取 2 張 5 美元的鈔票。
對(duì)于接下來(lái)的 2 位顧客，我們收取一張 10 美元的鈔票，然后返還 5 美元。
對(duì)于最后一位顧客，我們無(wú)法退回 15 美元，因?yàn)槲覀儸F(xiàn)在只有兩張 10 美元的鈔票。
由于不是每位顧客都得到了正確的找零，所以答案是 false。
解答
這道題對(duì)邏輯分析能力要求比較高，各個(gè)情況都要考慮全面。我們構(gòu)建一個(gè)字典（wallet）用來(lái)存放鈔票，并初始化每種面額的鈔票數(shù)量為零：wallet = {5: 0, 10: 0, 20: 0}，用戶給的鈔票，無(wú)非以下三種情況：
如果客戶給了5元，那么無(wú)需找零，錢(qián)包中面額5的張數(shù)+1；
如果客戶給了10元，需要查看錢(qián)包中有沒(méi)有面額為5的鈔票，如果有，那么把這張鈔票找給用戶，如果沒(méi)有，說(shuō)明無(wú)法找零，返回False；
如果客戶給了20元，有兩種找零方式：
（1）錢(qián)包中有至少一張10元鈔票和至少一張5元鈔票，可以找給用戶；
（2）錢(qián)包中沒(méi)有10元鈔票，但是有至少三張5元鈔票，可以找給用戶；
如果不滿足上述條件，說(shuō)明無(wú)法找零。
每次找零時(shí)，需要更新字典中每張鈔票的數(shù)量。
class Solution:
def lemonadeChange(self, bills):
"""
:param bills: List[int]
:return: bool
"""
wallet = {5: 0, 10: 0, 20: 0} # 錢(qián)包
for bill in bills:
if bill == 5: # 如果收到5元鈔票
wallet[5] += 1
elif bill == 10: # 收到10元鈔票
if wallet[5] > 0:
wallet[5] -= 1
wallet[10] += 1
else:
return False
else: # 收到20元鈔票
if wallet[10] > 0 and wallet[5] > 0:
wallet[10] -= 1
wallet[5] -= 1
wallet[20] += 1
elif wallet[5] > 2:
wallet[5] -= 3
wallet[20] += 1
else:
return False
return True
如有疑問(wèn)或建議，歡迎評(píng)論區(qū)留言~
