LeetCode 题解工作台
设计一个 ATM 机器
一个 ATM 机器，存有 5 种面值的钞票： 20 ， 50 ， 100 ， 200 和 500 美元。初始时，ATM 机是空的。用户可以用它存或者取任意数目的钱。 取款时，机器会优先取 较大 数额的钱。 比方说，你想取 $300 ，并且机器里有 2 张 $50 的钞票， 1 张 $100 的钞票和…
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 贪心·invariant
答案摘要
我们用一个数组 记录钞票面额，用一个数组 记录每种面额的钞票数量。 对于 `deposit` 操作，我们只需要将对应面额的钞票数量加上即可。时间复杂度 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 贪心·invariant 题型思路
题目描述
一个 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 == 50 <= banknotesCount[i] <= 1091 <= amount <= 109- 总共 最多有
5000次withdraw和deposit的调用。 - 函数
withdraw和deposit至少各有 一次 调用。
解题思路
方法一：模拟
我们用一个数组 记录钞票面额，用一个数组 记录每种面额的钞票数量。
对于 deposit 操作，我们只需要将对应面额的钞票数量加上即可。时间复杂度 。
对于 withdraw 操作，我们从大到小枚举每种面额的钞票，取出尽可能多且不超过 的钞票，然后将 减去取出的钞票面额之和，如果最后 仍大于 ，说明无法取出 的钞票，返回 即可。否则，返回取出的钞票数量即可。时间复杂度 。
class ATM:
def __init__(self):
self.d = [20, 50, 100, 200, 500]
self.m = len(self.d)
self.cnt = [0] * self.m
def deposit(self, banknotesCount: List[int]) -> None:
for i, x in enumerate(banknotesCount):
self.cnt[i] += x
def withdraw(self, amount: int) -> List[int]:
ans = [0] * self.m
for i in reversed(range(self.m)):
ans[i] = min(amount // self.d[i], self.cnt[i])
amount -= ans[i] * self.d[i]
if amount > 0:
return [-1]
for i, x in enumerate(ans):
self.cnt[i] -= x
return ans
# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate handle greedy algorithms effectively?
- question_mark
Does the candidate consider edge cases for failed withdrawals?
- question_mark
How efficiently does the candidate track and update the banknotes?
常见陷阱
外企场景- error
Failing to reject a withdrawal when the exact amount cannot be made with the available banknotes.
- error
Not prioritizing larger denominations, resulting in using more banknotes than necessary.
- error
Incorrectly managing the banknote counts after multiple deposits and withdrawals, leading to errors in future transactions.
进阶变体
外企场景- arrow_right_alt
Modify the ATM to handle additional banknote denominations.
- arrow_right_alt
Implement a version where withdrawal requests prioritize minimizing the number of banknotes rather than using larger denominations.
- arrow_right_alt
Extend the problem to handle scenarios where multiple users are interacting with the ATM simultaneously.