解題說明
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)和一致性?