设计一个 ATM 机器

难度: Medium

一个 ATM 机器，存有 5 种面值的钞票：20 ，50 ，100 ，200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。

取款时，机器会优先取较大数额的钱。

比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票，1 张 $100 的钞票和1 张 $200 的钞票，那么机器会取出 $100 和 $200 的钞票。
但是，如果你想取 $600 ，机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝，因为机器会先取出 $500 的钞票，然后无法取出剩余的 $100 。注意，因为有 $500 钞票的存在，机器不能取 $200 的钞票。

请你实现 ATM 类：

ATM() 初始化 ATM 对象。
void deposit(int[] banknotesCount) 分别存入 $20 ，$50，$100，$200 和 $500 钞票的数目。
int[] withdraw(int amount) 返回一个长度为 5 的数组，分别表示 $20 ，$50，$100 ，$200 和 $500 钞票的数目，并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱，请返回 [-1] （这种情况下不取出任何钞票）。

示例 1：

输入：
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
输出：
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]

解释：
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // 存入 1 张 $100 ，2 张 $200 和 1 张 $500 的钞票。
atm.withdraw(600);        // 返回 [0,0,1,0,1] 。机器返回 1 张 $100 和 1 张 $500 的钞票。机器里剩余钞票的数量为 [0,0,0,2,0] 。
atm.deposit([0,1,0,1,1]); // 存入 1 张 $50 ，1 张 $200 和 1 张 $500 的钞票。
                          // 机器中剩余钞票数量为 [0,1,0,3,1] 。
atm.withdraw(600);        // 返回 [-1] 。机器会尝试取出 $500 的钞票，然后无法得到剩余的 $100 ，所以取款请求会被拒绝。
                          // 由于请求被拒绝，机器中钞票的数量不会发生改变。
atm.withdraw(550);        // 返回 [0,1,0,0,1] ，机器会返回 1 张 $50 的钞票和 1 张 $500 的钞票。

提示：

banknotesCount.length == 5
0 <= banknotesCount[i] <= 10⁹
1 <= amount <= 10⁹
总共最多有 5000 次 withdraw 和 deposit 的调用。
函数 withdraw 和 deposit 至少各有一次调用。

Submission

运行时间: 77 ms

内存: 18.7 MB

class ATM:

    def __init__(self):
        self.dic = {500:0, 200:0, 100:0, 50:0, 20:0}

    def deposit(self, banknotesCount: List[int]) -> None:
        self.dic[500] += banknotesCount[4]
        self.dic[200] += banknotesCount[3]
        self.dic[100] += banknotesCount[2]
        self.dic[50] += banknotesCount[1]
        self.dic[20] += banknotesCount[0]

    def withdraw(self, amount: int) -> List[int]:
        ans = [0,0,0,0,0]
        while amount > 0:
            if self.dic[500] > ans[4] and amount >= 500:
                ans[4] += min(amount // 500, self.dic[500])
                amount -= 500 * ans[4]
            elif self.dic[200] > ans[3] and amount >= 200:
                ans[3] += min(amount // 200, self.dic[200])
                amount -= 200 * ans[3]
            elif self.dic[100] > ans[2] and amount >= 100:
                ans[2] += min(amount // 100, self.dic[100])
                amount -= 100 * ans[2]
            elif self.dic[50] > ans[1] and amount >= 50:
                ans[1] += min(amount // 50, self.dic[50])
                amount -= 50 * ans[1]
            elif self.dic[20] > ans[0] and amount >= 20:
                ans[0] += min(amount // 20, self.dic[20])
                amount -= 20 * ans[0]
            else:
                break
        if amount == 0:
            self.dic[500] -= ans[4]
            self.dic[200] -= ans[3]
            self.dic[100] -= ans[2]
            self.dic[50] -= ans[1]
            self.dic[20] -= ans[0]
            return ans
        else:
            return [-1]

# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)

Explain

这个题解使用了贪心算法的思想。存款操作直接将对应面值的钞票数量加到字典中。取款操作先尝试从面值最大的钞票开始取，每次取尽量多的张数，直到不能再取为止，然后依次尝试更小面值的钞票。如果最后成功取出了指定金额，就更新字典中的钞票数量并返回取出的钞票数；如果无法取出指定金额，就返回[-1]。

时间复杂度: O(1)

空间复杂度: O(1)

class ATM:

    def __init__(self):
        # 初始化一个字典，用于存储每种面值钞票的数量
        self.dic = {500:0, 200:0, 100:0, 50:0, 20:0}

    def deposit(self, banknotesCount: List[int]) -> None:
        # 存款操作，更新字典中每种面值钞票的数量
        self.dic[500] += banknotesCount[4]
        self.dic[200] += banknotesCount[3]
        self.dic[100] += banknotesCount[2]
        self.dic[50] += banknotesCount[1]
        self.dic[20] += banknotesCount[0]

    def withdraw(self, amount: int) -> List[int]:
        # 初始化一个长度为5的答案数组，表示每种面值取出的钞票数
        ans = [0,0,0,0,0]
        # 从面值最大的钞票开始尝试取款
        while amount > 0:
            if self.dic[500] > ans[4] and amount >= 500:
                ans[4] += min(amount // 500, self.dic[500])
                amount -= 500 * ans[4]
            elif self.dic[200] > ans[3] and amount >= 200:
                ans[3] += min(amount // 200, self.dic[200])
                amount -= 200 * ans[3]
            elif self.dic[100] > ans[2] and amount >= 100:
                ans[2] += min(amount // 100, self.dic[100])
                amount -= 100 * ans[2]
            elif self.dic[50] > ans[1] and amount >= 50:
                ans[1] += min(amount // 50, self.dic[50])
                amount -= 50 * ans[1]
            elif self.dic[20] > ans[0] and amount >= 20:
                ans[0] += min(amount // 20, self.dic[20])
                amount -= 20 * ans[0]
            else:
                break
        # 如果成功取出指定金额，更新字典中的钞票数量并返回答案数组
        if amount == 0:
            self.dic[500] -= ans[4]
            self.dic[200] -= ans[3]
            self.dic[100] -= ans[2]
            self.dic[50] -= ans[1]
            self.dic[20] -= ans[0]
            return ans
        # 如果无法取出指定金额，返回[-1]
        else:
            return [-1]

Explore

在取款函数中，如果最大面额的钞票无法完全满足取款金额，算法会自动尝试使用下一个较小的面额。这个过程是通过一个循环实现的，循环中会依次检查每种面额的钞票。如果当前面额无法满足或无法完全满足剩余的取款金额，就会继续检查更小的面额，直到找到足够的组合或检查完所有面额。

使用字典来存储各面值钞票的数量可以方便地通过钞票面额直接访问其数量，使得代码更加直观和易于理解。字典提供了键值对的存储方式，其中键是钞票面额，值是该面额钞票的数量。这种方式比使用列表或数组更灵活，因为它允许直接通过面额来增减钞票数量，而无需记住面额在列表中的具体位置。

代码中在尝试从某一面额取钱前会检查该面额的钞票数量是否大于零。这通过条件判断 `self.dic[denomination] > 0` 来实现，其中 `denomination` 是当前面额。如果钞票数量为零，则该条件为假，因此代码不会执行取钱操作，并会继续检查下一个较小的面额。这样确保了不会尝试从数量为零的面额中取钱。

直接返回[-1]是因为采用了贪心算法的策略，该策略优先使用大面额钞票以减少交易中钞票的总张数。一旦尝试了所有面额后仍有剩余金额，这意味着在当前的钞票配置下无法组合出所需的金额。尝试其他组合会大幅增加算法的复杂度，并可能导致性能问题，尤其是在钞票种类和数量较多的情况下。因此，为了保持算法的效率和简洁性，选择在无法满足条件时直接返回[-1]。