解題說明
Simple Bank System
題目描述： 設計一個簡易銀行系統，支援 n 個帳戶。實作三個操作：轉帳（transfer）、存款（deposit）、提款（withdraw）。帳戶編號從 1 到 n，每個操作須驗證帳戶是否存在以及餘額是否足夠。
解題思路： 直接模擬即可。用陣列存儲每個帳戶的餘額。
- 帳戶驗證：檢查帳號是否在 [1, n] 範圍內。
transfer(acc1, acc2, money)：驗證兩個帳戶都有效且 acc1 餘額足夠，然後扣除 acc1、增加 acc2。deposit(acc, money)：驗證帳戶有效，增加餘額。withdraw(acc, money)：驗證帳戶有效且餘額足夠，扣除餘額。
所有操作成功回傳 true，失敗回傳 false。
C++ 解法
複雜度分析
時間複雜度：O(1)（每次操作）— 每個操作只涉及常數次陣列存取和算術運算。建構子 O(n) 複製餘額陣列。
空間複雜度：O(n) — 存儲 n 個帳戶的餘額。
虛擬碼
1. Store balances in an array indexed 0 to n-1. 2. VALID(account): return 1 <= account <= n. 3. TRANSFER(acc1, acc2, money): a. If not valid(acc1) or not valid(acc2), return false. b. If balance[acc1-1] < money, return false. c. balance[acc1-1] -= money, balance[acc2-1] += money, return true. 4. DEPOSIT(acc, money): if valid, balance[acc-1] += money, return true. 5. WITHDRAW(acc, money): if valid and sufficient balance, balance[acc-1] -= money, return true.
其他解法
-
HashMap 實作：使用 unordered_map<int, long long> 存儲帳戶餘額，適用於帳號稀疏的情境。查找和更新仍為 O(1)，但有額外的哈希開銷。
-
附帶交易紀錄的設計：除了維護餘額，同時記錄每筆交易的歷史（時間戳、類型、金額）。這樣可以支援撤銷操作或審計功能，空間複雜度增加為 O(T)，T 為交易次數。
延伸思考
- 若需要支援批量轉帳（一次從一個帳戶轉到多個帳戶），如何修改 transfer 介面？
- 如何加入交易回滾（rollback）功能，讓最近的 K 筆操作可以撤銷？
- 在多執行緒環境下，如何確保銀行操作的原子性（atomicity）和一致性？