Easy
Related Topics: Array / Greedy
LeetCode Source

解題想法

題目主要是希望透過 5 10 20 來交易價值為 5 的 lemonade

如果有錢可以找回傳 true 反之回傳 false

比較需要注意的是在 20 的時候

觀察有無 10 可以找

如果沒有需要考慮 3 個 5 是否可以找

過程中只需要紀錄 5 跟 10 的個數即可

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Python

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        dict = {5: 0, 10: 0}

        for i in range(len(bills)):
            if bills[i] == 5:
                dict[5] += 1
            elif bills[i] == 10:
                if dict[5] == 0:
                    return False
                dict[5] -= 1
                dict[10] += 1
            else:
                if dict[10] == 0:
                    if dict[5] < 3:
                        return False
                    dict[5] -= 3
                else:
                    if dict[5] == 0:
                        return False
                    dict[5] -= 1
                    dict[10] -= 1

        return True

C++

class Solution {
public:
    bool lemonadeChange(vector<int>& bills) {
        unordered_map<int, int> mp;

        mp[5] = 0;
        mp[10] = 0;

        for (int i = 0; i < bills.size(); i++) {
            if (bills[i] == 5)
                mp[5] += 1;
            else if (bills[i] == 10) {
                if (mp[5] == 0)
                    return false;
                mp[5] -= 1;
                mp[10] += 1;
            } else {
                if (mp[10] == 0) {
                    if (mp[5] < 3)
                        return false;
                    mp[5] -= 3;
                } else {
                    if (mp[5] == 0)
                        return false;
                    mp[5] -= 1;
                    mp[10] -= 1;
                }
            }
        }

        return true;
    }
};