2241.设计一个 ATM 机器

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

解题方法：模拟

使用一个数组分别存放每种面值数量的个数，一个数组存放每种面值的大小。

对于一个取款请求amout，从后向前遍历面值，并取款min(剩余数量, amount/面值)张。

如果最后amout为0，则说明能完成取款请求，每种面值减去取款数量；否则说明不能完成取款，返回-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 List

class 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] * 5
        for 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 main

type 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