【LetMeFly】2241.设计一个 ATM 机器：模拟
力扣题目链接：https://leetcode.cn/problems/design-an-atm-machine/
一个 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至少各有 一次 调用。
解题方法：模拟
使用一个数组分别存放每种面值数量的个数，一个数组存放每种面值的大小。
对于一个取款请求amout，从后向前遍历面值，并取款min(剩余数量, amount/面值)张。
如果最后amout为0，则说明能完成取款请求，每种面值减去取款数量；否则说明不能完成取款，返回-1。
- 时间复杂度：单次请求 O ( 1 ) O(1) O(1)
- 空间复杂度 O ( 1 ) O(1) O(1)
AC代码
C++
/** @Author: LetMeFly* @Date: 2025-01-05 19:01:19* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-05 19:07:46*/
class ATM {
private:int money[5] = {0, 0, 0, 0, 0};const int per[5] = {20, 50, 100, 200, 500};
public:ATM() {}void deposit(vector<int> banknotesCount) {for (int i = 0; i < 5; i++) {money[i] += banknotesCount[i];}}vector<int> withdraw(int amount) {vector<int> ans(5);for (int i = 4; i >= 0 && amount; i--) {ans[i] = min(money[i], amount / per[i]);amount -= ans[i] * per[i];}if (amount) {return {-1};}for (int i = 0; i < 5; i++) {money[i] -= ans[i];}return ans;}
};/*** Your ATM object will be instantiated and called as such:* ATM* obj = new ATM();* obj->deposit(banknotesCount);* vector<int> param_2 = obj->withdraw(amount);*/
Python
'''
Author: LetMeFly
Date: 2025-01-05 19:08:35
LastEditors: LetMeFly.xyz
LastEditTime: 2025-01-05 19:25:43
'''
from typing import Listclass ATM:def __init__(self):self.money = [0] * 5# self.per = [10, 20, 100, 200, 500] # 我说咋一直不对，原来面值写错了self.per = [20, 50, 100, 200, 500]def deposit(self, banknotesCount: List[int]) -> None:for i in range(5):self.money[i] += banknotesCount[i]def withdraw(self, amount: int) -> List[int]:# if amount == 550:# print('debug')ans = [0] * 5for i in range(4, -1, -1):ans[i] = min(self.money[i], amount // self.per[i])amount -= ans[i] * self.per[i]if amount:return [-1]for i in range(5):self.money[i] -= ans[i]return ans# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)# op = ["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
# val = [[], [[0, 0, 1, 2, 1]], [600], [[0, 1, 0, 1, 1]], [600], [550]]# atm = ATM()
# for i in range(1, len(op)):
# if op[i] == "deposit":
# atm.deposit(val[i][0])
# else:
# print(atm.withdraw(val[i][0]))Java
/** @Author: LetMeFly* @Date: 2025-01-05 19:28:31* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-05 19:33:23*/
class ATM {private long[] cnt, val;public ATM() {cnt = new long[5];val = new long[]{20, 50, 100, 200, 500};}public void deposit(int[] banknotesCount) {for (int i = 0; i < 5; i++) {cnt[i] += banknotesCount[i];}}public int[] withdraw(int amount) {int[] ans = new int[5];for (int i = 4; i >= 0; i--) {ans[i] = (int)Math.min(cnt[i], amount / val[i]);amount -= ans[i] * val[i];}if (amount > 0) {return new int[]{-1};}for (int i = 0; i < 5; i++) {cnt[i] -= ans[i];}return ans;}
}/*** Your ATM object will be instantiated and called as such:* ATM obj = new ATM();* obj.deposit(banknotesCount);* int[] param_2 = obj.withdraw(amount);*/
Go
/** @Author: LetMeFly* @Date: 2025-01-05 19:33:50* @LastEditors: LetMeFly.xyz* @LastEditTime: 2025-01-05 19:44:31*/
package maintype ATM struct { cnt, val []int64 }func Constructor() (ans ATM) {ans.cnt = make([]int64, 5)ans.val = []int64{20, 50, 100, 200, 500}return
}func (this *ATM) Deposit(banknotesCount []int) {for i := range banknotesCount {this.cnt[i] += (int64)(banknotesCount[i])}
}func (this *ATM) Withdraw(amount int) []int {ans := make([]int, 5)for i := 4; i >= 0; i-- {ans[i] = (int)(min(this.cnt[i], (int64)(amount) / this.val[i]))amount -= ans[i] * (int)(this.val[i])}if amount > 0 {return []int{-1}}for i := range this.cnt {this.cnt[i] -= (int64)(ans[i])}return ans
}/*** Your ATM object will be instantiated and called as such:* obj := Constructor();* obj.Deposit(banknotesCount);* param_2 := obj.Withdraw(amount);*/
同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/144951152
