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 == 50 <= banknotesCount[i] <= 1091 <= amount <= 1095000 次 withdraw 和 deposit 的调用。withdraw 和 deposit 至少各有 一次 调用。原站题解
java 解法, 执行用时: 139 ms, 内存消耗: 53.8 MB, 提交时间: 2023-09-11 09:56:53
class ATM {
private long[] cnt;
private int[] nums;
public ATM() {
this.cnt = new long[5];
this.nums = new int[]{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[] res = new int[5];
for (int i = 4; i >= 0; i--) {
if (amount >= nums[i] && cnt[i] > 0) {
int num = (amount / nums[i]) > cnt[i] ? (int) cnt[i] : (amount / nums[i]);
res[i] = num;
amount -= nums[i] * num;
}
}
// 如果能取出来，再对cnt真正操作
if (amount == 0) {
for (int i = 0; i < 5; i++) {
cnt[i] -= res[i];
}
return res;
}
return new int[]{-1};
}
}
/**
* Your ATM object will be instantiated and called as such:
* ATM obj = new ATM();
* obj.deposit(banknotesCount);
* int[] param_2 = obj.withdraw(amount);
*/
python3 解法, 执行用时: 232 ms, 内存消耗: 19.8 MB, 提交时间: 2023-09-11 09:45:42
class ATM:
def __init__(self):
self.atm = [0] * 5 # 0: 20, 1: 50, 2: 100, 3: 200, 4: 500
def deposit(self, banknotesCount: List[int]) -> None:
for i, cnt in enumerate(banknotesCount):
self.atm[i] += cnt
def withdraw(self, amount: int) -> List[int]:
res = [0] * 5
money = [20, 50, 100, 200, 500]
for i in range(4, -1, -1):
res[i] = min(amount // money[i], self.atm[i])
amount -= res[i] * money[i]
if amount > 0:
return [-1]
for i, cnt in enumerate(res):
self.atm[i] -= cnt
return res
# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)
php 解法, 执行用时: 380 ms, 内存消耗: 25.9 MB, 提交时间: 2023-09-11 09:45:06
class ATM {
public $money = [20, 50, 100, 200, 500];
/**
*/
function __construct() {
$this->atm = array_fill(0, 5, 0);
}
/**
* @param Integer[] $banknotesCount
* @return NULL
*/
function deposit($banknotesCount) {
foreach ( $banknotesCount as $i => $cnt ) {
$this->atm[$i] += $cnt;
}
}
/**
* @param Integer $amount
* @return Integer[]
*/
function withdraw($amount) {
$ans = array_fill(0, 5, 0);
for ( $i = 4; $i >= 0; $i-- ) {
$ans[$i] = min(intval($amount/$this->money[$i]), $this->atm[$i]);
$amount -= $ans[$i] * $this->money[$i];
}
if ( $amount > 0 ) { // 没法取恰好 amount
return [-1];
}
foreach ( $ans as $i => $c ) {
$this->atm[$i] -= $c;
}
return $ans;
}
}
/**
* Your ATM object will be instantiated and called as such:
* $obj = ATM();
* $obj->deposit($banknotesCount);
* $ret_2 = $obj->withdraw($amount);
*/
golang 解法, 执行用时: 196 ms, 内存消耗: 8.1 MB, 提交时间: 2023-09-11 09:35:57
var a = [5]int{20, 50, 100, 200, 500}
type ATM [5]int
func Constructor() ATM { return ATM{} }
// 存钱
func (left *ATM) Deposit(banknotesCount []int) {
for i, count := range banknotesCount {
left[i] += count
}
}
// 取钱
func (left *ATM) Withdraw(amount int) []int {
ans := make([]int, 5)
for i := 4; i >= 0; i-- {
ans[i] = min(amount/a[i], left[i])
amount -= ans[i] * a[i]
}
if amount > 0 { // 没法取恰好 amount
return []int{-1}
}
for i, count := range ans {
left[i] -= count
}
return ans
}
func min(a, b int) int { if a > b { return b }; return a }
/**
* Your ATM object will be instantiated and called as such:
* obj := Constructor();
* obj.Deposit(banknotesCount);
* param_2 := obj.Withdraw(amount);
*/