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

Francesca Hotchin on Unsplash

題目敘述 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