題目敘述 860. Lemonade Change
假想一個經營檸檬水小舖的情境。
一杯檸檬水都賣$5顧客付錢時只有三種可能，$5, $10 或 $ 20
初始時，檸檬水小舖沒有零錢。
給定一個顧客買檸檬水的付錢陣列bills，請問能不能滿足每一筆交易，並且找開零錢。
如果可以，返回True。
如果不行，返回False。
測試範例
Example 1:
Input: bills = [5,5,5,10,20]
Output: true
Explanation:
店鋪收到$5
店鋪收到$5
店鋪收到$5
店鋪找錢$5
店鋪找錢$10 + $5
Example 2:
Input: bills = [5,5,10,10,20]
Output: false
Explanation:
店鋪收到$5
店鋪收到$5
店鋪找錢$5
店鋪找錢$5
店鋪已經沒有零錢可以找了。
演算法 情境模擬，盡可能用比較少數量的銅板去零錢。
因為題目要求是盡可能的滿足每一筆交易，並且找開零錢。
所以盡可能用比較少數量的銅板去零錢。
遇到顧客付$5，剛好不用找零。
遇到顧客付$10，找給顧客$5。
遇到顧客付$20，先試著找給顧客$10 + $5，假如不行才找給顧客$5 + $5 + $5。
假如某一回合，店鋪沒有零錢，則返回False。
如果可以滿足每一筆交易，並且找開零錢給顧客，則返回True。
程式碼 情境模擬，盡可能用比較少數量的銅板去零錢。
class Solution:
def lemonadeChange(self, bills: List[int]) -> bool:
counter_of_5, counter_of_10, counter_of_20 = 0, 0, 0
for cumstomer_payment in bills:
if cumstomer_payment == 5:
counter_of_5 += 1
else:
if cumstomer_payment == 10:
counter_of_10 += 1
# make change with $5
counter_of_5 -= 1
else:
counter_of_20 += 1
if counter_of_10:
# eco-greedy on $5 dollars.
# make change with $15 = $10 + $5
counter_of_10 -= 1
counter_of_5 -= 1
else:
# make change with $15 = 3 * $5
counter_of_5 -= 3
if counter_of_5 < 0:
# out of 5 dollars,
# therefore cannot make change to customer
return False
return True
複雜度分析
時間複雜度: O(n)
依序處理每一筆交易，每一筆交易可以在O(1)時間內完成找零，總共耗時O(n)。
空間複雜度: O(1)
所用到的變數都是臨時變數，所需空間為O(1)常數級別。
