2241-设计一个 ATM 机器

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:27 2023-09-13 16:06:27 Updated    

一个 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 至少各有 **一次 **调用。

方法一：维护每种钞票的剩余数目

思路与算法

首先我们尝试分析各个方法对应的需求：

  • 对于 deposit}() 方法，我们需要更新每张钞票的数目；

  • 对于 withdraw}() 方法，我们需要模拟机器从高面额至低面额尝试取钱的过程，判断是否可行，并尝试更新每张钞票的数目，以及返回取出各种面额钞票的数目。

我们可以用一个数组 cnt 来维护每种钞票的剩余数目，同时用数组 value 来维护 cnt 数组对应下标钞票的面额。为了方便起见，我们需要让 value 数组保持升序。

那么，对于 deposit}() 方法，我们只需要遍历输入数组，并将每个元素的值加在 cnt 中的对应元素上即可。

而对于 withdraw}() 方法，我们需要倒序（即从高面额至低面额）遍历 cnt 数组，并模拟取钱操作。

具体而言，我们用数组 res 表示（如果可行）取出各种钞票的数目，同时倒序遍历 cnt 数组，并更新还需要取的金额数目 amount。当遍历到下标 i 时，我们首先计算该面额钞票需要取出的数量 res}[i]。对应钞票的数量不能多余取款机中该种钞票的数量，且总面额不能高于还需取出的金额数目。因此我们有 res}[i] = \min(\textit{cnt}[i], \lfloor \textit{amount} / \min(\textit{value}[i] \rfloor)（其中 \lfloor \dots \rfloor 代表向下取整）。同时，我们需要对应地将 amount 减去 res}[i] \times \textit{value}[i]。

当遍历完成后，如果 amount} = 0，即代表可以进行该取出操作，我们将 cnt 数组地每个元素减去 res 数组的对应元素，并返回 res 作为答案；而如果 amount} > 0，则说明无法进行取出操作，我们应当不进行任何操作，直接返回 [-1]。

细节

在操作过程中，cnt 数组的元素数值有可能超过 32 位有符号整数的上限，因此对于 C++ 等语言，我们需要用 64 位整数存储每种钞票的剩余数目。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class ATM {
private:
    vector<long long> cnt;   // 每张钞票剩余数量
    vector<long long> value;   // 每张钞票面额
    
public:
    ATM() {
        cnt = {0, 0, 0, 0, 0};
        value = {20, 50, 100, 200, 500};
    }
    
    void deposit(vector<int> banknotesCount) {
        for (int i = 0; i < 5; ++i) {
            cnt[i] += banknotesCount[i];
        }
    }
    
    vector<int> withdraw(int amount) {
        vector<int> res(5);
        // 模拟尝试取出钞票的过程
        for (int i = 4; i >= 0; --i) {
            res[i] = min(cnt[i], amount / value[i]);
            amount -= res[i] * value[i];
        }
        if (amount) {
            // 无法完成该操作
            return {-1};
        } else {
            // 可以完成该操作
            for (int i = 0; i < 5; ++i) {
                cnt[i] -= res[i];
            }
            return res;
        }
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class ATM:

    def __init__(self):
        self.cnt = [0] * 5   # 每张钞票剩余数量
        self.value = [20, 50, 100, 200, 500]   # 每张钞票面额


    def deposit(self, banknotesCount: List[int]) -> None:
        for i in range(5):
            self.cnt[i] += banknotesCount[i]


    def withdraw(self, amount: int) -> List[int]:
        res = [0] * 5
        # 模拟尝试取出钞票的过程
        for i in range(4, -1, -1):
            res[i] = min(self.cnt[i], amount // self.value[i])
            amount -= res[i] * self.value[i]
        if amount:
            # 无法完成该操作
            return [-1]
        else:
            # 可以完成该操作
            for i in range(5):
                self.cnt[i] -= res[i]
            return res

复杂度分析

  • 时间复杂度：O(nk)，其中 n 为 withdraw}() 和 deposit}() 操作的次数，k = 5 为不同面值钞票的数量。每一次 withdraw}() 或 deposit}() 操作的时间复杂度为 O(k)。

  • 空间复杂度：O(k)，即为存储每种钞票面额和剩余数量数组的空间开销。

 Comments
On this page
2241-设计一个 ATM 机器