🍋情境模擬: 檸檬水小舖 Lemonade Change_Leetcode #860

🍋情境模擬: 檸檬水小舖 Lemonade Change_Leetcode #860

更新於 發佈於 閱讀時間約 4 分鐘

題目敘述 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)常數級別。


Reference

[1] Lemonade Change - LeetCode

avatar-img
小松鼠的演算法樂園
95會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言
avatar-img
留言分享你的想法!
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。
題目敘述 Rank Transform of an Array 給定一個陣列arr,請根據數字的大小給予序號,序號值介於1~len( set(arr) )之間。 最大的數字給予最大的序號。 次大的數字給予次大的序號。 ...依此類推 最小的數字給予最小的序號1。
題目敘述 Check If Array Pairs Are Divisible by k 給定一個長度為偶數的整數陣列arr,和一個整數k 。 我們想把陣列元素兩兩一組組成pair,使得每個pair的總和可以被k整除。 如果做得到,返回True。 如果不行,返回False。
My Calendar II 給定一個行事曆的class定義和行程安排的介面。 請完成下列function 1.建構子MyCalendarTwo() 2.boolean book(int start, int end) 在行事曆加入一項新行程,起始時間為start, 結束時間為end。