ETH官方钱包

前往
大廳
主題

LeetCode - 2241. Design an ATM Machine 解題心得

Not In My Back Yard | 2022-12-28 12:00:06 | 巴幣 100 | 人氣 210

題目連結:


題目意譯:
現在有一臺 ATM 其可以儲存五種紙鈔面額: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 元的面額各自將會有多少數量會被交到使用者手上。如果無法提款,則回傳 [-1](這此例中請勿提出任何紙鈔)。

限制:
banknotesCount.length == 5
0 ≦ banknotesCount[i] ≦ 10 ^ 9
1 ≦ amount ≦ 10 ^ 9
最多呼叫 5000 次 withdraw 和 deposit。
至少各呼叫一次 withdraw 和 deposit。



範例測資:
範例 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]); // 存入 50 、 200 和 500 元各 1 張。
                          // 機器中所剩的紙鈔為 [0,1,0,3,1]。
atm.withdraw(600);        // 回傳 [-1]。機器試圖使用一張 500 元,但無法處理剩下的 300 元。
                          // 所以提款請求將被拒絕。由於請求被拒絕了,因此機器中的紙鈔數量不變。
atm.withdraw(550);        // 回傳 [0,1,0,0,1]。機器使用掉 1 張 50 元和 1 張 500 元。


解題思維:
模擬即可。

用一個大小為 5 的陣列 money 來儲存現在 ATM 中各個面額的紙鈔數量。

所以 deposit 這個函式就單純地把 money 和傳入的 banknotesCount 陣列對應位置相加即可。

而 withdraw 就是先檢查這個提款金額可不可行——可以用一個陣列來複製當前 money 的狀態,然後試著從最大面額的紙鈔(如果有存貨的話)提提看一路到較小的面額,如果中間有某面額紙鈔無法完成剩餘的提款金額,則不要把複製後的陣列的狀態放回到 money;反之,則我們可以將其套用回去到 money 中。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

相關創作

更多創作