| comments | difficulty | edit_url | rating | source | tags | |||
|---|---|---|---|---|---|---|---|---|
true |
中等 |
1616 |
第 76 场双周赛 Q3 |
|
一个 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至少各有 一次 调用。
我们用一个数组
对于 deposit 操作，我们只需要将对应面额的钞票数量加上即可。时间复杂度
对于 withdraw 操作，我们从大到小枚举每种面额的钞票，取出尽可能多且不超过
class ATM:
def __init__(self):
self.d = [20, 50, 100, 200, 500]
self.m = len(self.d)
self.cnt = [0] * self.m
def deposit(self, banknotesCount: List[int]) -> None:
for i, x in enumerate(banknotesCount):
self.cnt[i] += x
def withdraw(self, amount: int) -> List[int]:
ans = [0] * self.m
for 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] -= x
return ans
# Your ATM object will be instantiated and called as such:
# obj = ATM()
# obj.deposit(banknotesCount)
# param_2 = obj.withdraw(amount)class ATM {
private int[] d = {20, 50, 100, 200, 500};
private int m = d.length;
private long[] cnt = new long[5];
public ATM() {
}
public void deposit(int[] banknotesCount) {
for (int i = 0; i < banknotesCount.length; ++i) {
cnt[i] += banknotesCount[i];
}
}
public int[] withdraw(int amount) {
int[] ans = new int[m];
for (int i = m - 1; i >= 0; --i) {
ans[i] = (int) Math.min(amount / d[i], cnt[i]);
amount -= ans[i] * d[i];
}
if (amount > 0) {
return new int[] {-1};
}
for (int i = 0; i < m; ++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);
*/class ATM {
public:
ATM() {
}
void deposit(vector<int> banknotesCount) {
for (int i = 0; i < banknotesCount.size(); ++i) {
cnt[i] += banknotesCount[i];
}
}
vector<int> withdraw(int amount) {
vector<int> ans(m);
for (int i = m - 1; ~i; --i) {
ans[i] = min(1ll * amount / d[i], cnt[i]);
amount -= ans[i] * d[i];
}
if (amount > 0) {
return {-1};
}
for (int i = 0; i < m; ++i) {
cnt[i] -= ans[i];
}
return ans;
}
private:
static constexpr int d[5] = {20, 50, 100, 200, 500};
static constexpr int m = size(d);
long long cnt[m] = {0};
};
/**
* Your ATM object will be instantiated and called as such:
* ATM* obj = new ATM();
* obj->deposit(banknotesCount);
* vector<int> param_2 = obj->withdraw(amount);
*/var d = [...]int{20, 50, 100, 200, 500}
const m = len(d)
type ATM [m]int
func Constructor() ATM {
return ATM{}
}
func (this *ATM) Deposit(banknotesCount []int) {
for i, x := range banknotesCount {
this[i] += x
}
}
func (this *ATM) Withdraw(amount int) []int {
ans := make([]int, m)
for i := m - 1; i >= 0; i-- {
ans[i] = min(amount/d[i], this[i])
amount -= ans[i] * d[i]
}
if amount > 0 {
return []int{-1}
}
for i, x := range ans {
this[i] -= x
}
return ans
}
/**
* Your ATM object will be instantiated and called as such:
* obj := Constructor();
* obj.Deposit(banknotesCount);
* param_2 := obj.Withdraw(amount);
*/const d: number[] = [20, 50, 100, 200, 500];
const m = d.length;
class ATM {
private cnt: number[];
constructor() {
this.cnt = Array(m).fill(0);
}
deposit(banknotesCount: number[]): void {
for (let i = 0; i < banknotesCount.length; ++i) {
this.cnt[i] += banknotesCount[i];
}
}
withdraw(amount: number): number[] {
const ans: number[] = Array(m).fill(0);
for (let i = m - 1; i >= 0; --i) {
ans[i] = Math.min(Math.floor(amount / d[i]), this.cnt[i]);
amount -= ans[i] * d[i];
}
if (amount > 0) {
return [-1];
}
for (let i = 0; i < m; ++i) {
this.cnt[i] -= ans[i];
}
return ans;
}
}
/**
* Your ATM object will be instantiated and called as such:
* var obj = new ATM()
* obj.deposit(banknotesCount)
* var param_2 = obj.withdraw(amount)
*/