2241. Design an ATM Machine

2025-01-06

字数统计: 1.1k字 | 阅读时长: 5min

QUESTION：

2241. Design an ATM Machine.md
There is an ATM machine that stores banknotes of 5 denominations: 20, 50, 100, 200, and 500 dollars. Initially the ATM is empty. The user can use the machine to deposit or withdraw any amount of money.

When withdrawing, the machine prioritizes using banknotes of larger values.

For example, if you want to withdraw $300 and there are 2 $50 banknotes, 1 $100 banknote, and 1 $200 banknote, then the machine will use the $100 and $200 banknotes.
However, if you try to withdraw $600 and there are 3 $200 banknotes and 1 $500 banknote, then the withdraw request will be rejected because the machine will first try to use the $500 banknote and then be unable to use banknotes to complete the remaining $100. Note that the machine is not allowed to use the $200 banknotes instead of the $500 banknote.
Implement the ATM class:

ATM() Initializes the ATM object.
void deposit(int[] banknotesCount) Deposits new banknotes in the order $20, $50, $100, $200, and $500.
int[] withdraw(int amount) Returns an array of length 5 of the number of banknotes that will be handed to the user in the order $20, $50, $100, $200, and $500, and update the number of banknotes in the ATM after withdrawing. Returns [-1] if it is not possible (do not withdraw any banknotes in this case).

My Think：

The purpose of this question is to simulate an ATM machine, which returns the amount of money you withdraw, no more and no less. I am greedy, because the second sentence “There are 3 $200 bills and 1 $500 bill in the machine, so the withdrawal request will be rejected”
This shows that we can skip thinking about the knapsack problem in complex dynamic programming and directly consider simple greed.

Because the denominations of the deposited money are only 20, 50, 100, 200, 500, we can store them in the list in advance and wait for traversal.

Then we create a defaultdict() to create a hash table for each denomination in the ATM machine.

deposit() creates a reverse traversal dictionary. Because we need to traverse the dictionary from large denominations to small denominations, the reverse dictionary is very convenient at this time.

Assuming the initial amount is 600, the first denomination traversed is 500, It fits the logic of the question very well

For the withdraw() function, I created a temporary dictionary deep copy storage so that the initial array will not be changed when [-1] is returned. Otherwise, it will be troublesome to backtrack.

Here, Sylvia and I used two different traversal methods. She traversed the list of denominations, while I traversed the dictionary directly (actually traversed the key directly).

If the current denomination (600) is greater than the current denomination (500), then try to deduct it. If the bank money is withdrawn directly, then look at the next denomination.
If it is not withdrawn, then amount deducts the deductible share and then continues to look at the next denomination.
If there is still amount left at the end, return [-1], otherwise calculate how many bills have been consumed in total, which is the answer.

这道题的目的是模拟一台ATM机器, 让你取多少钱, 就返回多少钱, 不能多也不能少. 我是贪心的思想, 因为第二句”机器里有 3 张 $200 的钞票和1 张 $500 的钞票，那么取款请求会被拒绝”
这就说明我们可以跳过思考复杂的动态规划中的背包问题, 而直接考虑简单的贪心.

因为存的钱的面额只有20, 50, 100, 200, 500 这五种面额, 于是我们提前存在列表里面等待遍历即可.
然后我们创建一个defaultdict(), 为ATM机器里面的每种面额创建哈希表.

deposit()创建了一个反向遍历的字典. 因为我们需要从大面额到小面额遍历字典, 在这个时候反向的字典就很方便.

假设初始`amount`为`600`, 遍历到的第一个面额就是`500`, 就很符合题目的逻辑

withdraw()函数, 我之所以创建了一个临时字典深拷贝储存是在返回[-1]的情况下不更改初始数组. 否则还要回溯挺麻烦的.

这里我和Sylvia用了两种不同的遍历方式, 她遍历了面额的列表, 而我是直接遍历的字典(实际上直接遍历的key).

如果当前面额(600)大于了当前面额(500), 那就尝试扣除, 如果直接把银行钱取完了, 那再看下一个面值.
如果没有取完, 那么amount扣除掉能扣除的份额, 再继续看下一个面额即可.
到最后amount还有剩余则返回[-1], 否则计算一共消耗了多少张钞票, 即是答案了.

Code：

import copy
from typing import List

from collections import defaultdict


class ATM:

    def __init__(self):
        self.sd = defaultdict(int)
        self.amount = ['20', '50', '100', '200', '500']

    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(len(banknotesCount) - 1, -1, -1):
            self.sd[self.amount[i]] += banknotesCount[i]



    def withdraw(self, amount: int) -> List[int]:
        tempSd = copy.deepcopy(self.sd)
        # key = 面值, value = 张数
        for key, value in tempSd.items():
            if amount >= int(key) and value > 0:
                # 需要多少张钞票
                howManyPiece = amount // int(key)
                if howManyPiece >= value:
                    # 全部取出来
                    tempSd[key] = 0
                    amount -= value * int(key)
                else:
                    # 取出这么多钞票
                    tempSd[key] -= howManyPiece
                    amount -= int(key) * howManyPiece
        else:
            if amount > 0:
                return [-1]
            else:
                ans = []
                for i in self.sd.keys():
                    ans.append(self.sd[i] - tempSd[i])
                self.sd = copy.deepcopy(tempSd)
                return ans[::-1]