Leetcode打卡：设计一个ATM机器

执行结果：通过

---

题目 2241 设计一个ATM机器

一个 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] <= 109
• 1 <= amount <= 109
• 总共 最多有 5000 次 withdraw 和 deposit 的调用。
• 函数 withdraw 和 deposit 至少各有 一次 调用。

代码以及解题思路

代码

class ATM:def __init__(self):self.d = [20, 50, 100, 200, 500]self.m = len(self.d)self.cnt = [0] * self.mdef deposit(self, banknotesCount: List[int]) -> None:for i, x in enumerate(banknotesCount):self.cnt[i] += xdef withdraw(self, amount: int) -> List[int]:ans = [0] * self.mfor 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] -= xreturn ans

解题思路：

类定义和初始化

• ATM 类有三个属性：
  • d：一个列表，存储ATM机支持的钞票面额，按从小到大的顺序排列。
  • m：钞票面额的数量。
  • cnt：一个列表，存储每种面额的钞票数量，初始化为0。

存款方法 deposit

• 输入参数 banknotesCount 是一个列表，表示用户存入的每种面额钞票的数量。
• 方法遍历 banknotesCount 列表，将每种面额的钞票数量加到 cnt 列表的对应位置。

取款方法 withdraw

• 输入参数 amount 是一个整数，表示用户希望取出的总金额。
• 方法返回一个列表，表示为了凑出 amount 金额，ATM机应该支付的每种面额的钞票数量。如果无法凑出 amount 金额，则返回 [-1]。

取款方法的实现步骤如下：

1. 初始化一个与 cnt 列表长度相同的列表 ans，用于存储每种面额钞票的支付数量，初始化为0。
2. 从最大面额的钞票开始遍历（使用 reversed(range(self.m))），对于每种面额：
   • 计算可以支付的最大数量，即用户请求的金额 amount 除以当前面额 self.d[i]，与当前面额钞票的库存数量 self.cnt[i] 中的较小值。
   • 更新 ans[i] 为计算出的支付数量。
   • 更新 amount 为剩余需要支付的金额，即 amount 减去已支付的金额 ans[i] * self.d[i]。
3. 如果遍历完所有面额后，amount 仍然大于0，表示无法凑出用户请求的金额，返回 [-1]。
4. 如果可以凑出用户请求的金额，遍历 ans 列表，更新 cnt 列表，减去已支付的每种面额钞票的数量。
5. 返回 ans 列表，表示支付的每种面额钞票的数量。

总结

这段代码通过维护一个钞票面额列表和一个每种面额钞票数量的列表，实现了存款和取款的基本功能。取款功能通过从最大面额开始尝试支付，确保尽可能使用较少种类的钞票来满足用户的请求。如果无法完全满足用户的取款请求，则返回 [-1]。