教程文檔【免費(fèi)下載鏈接】LogicStack-LeetCode公眾號(hào)「宮水三葉的刷題日記」刷穿 LeetCode 系列文章源碼項(xiàng)目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode點(diǎn)擊查看免費(fèi)下載本篇以 LogicStack-LeetCode 倉(cāng)庫(kù)中 LeetCode/2041-2050/2043. 簡(jiǎn)易銀行系統(tǒng)中等.md 的官方題解為骨架?chē)@「模擬」這一核心 Tag 展開(kāi)。你將掌握這類(lèi)「設(shè)計(jì)類(lèi) 規(guī)則模擬」題目的通用解題套路如何把題面中的交易規(guī)則翻譯成精確的代碼判斷如何做賬戶(hù)編號(hào)到數(shù)組下標(biāo)的映射以及為什么余額必須使用long而非int。讀完即可獨(dú)立復(fù)現(xiàn)并提交本題并能在后續(xù)同類(lèi)模擬題中復(fù)用這套方法論。題目描述這是 LeetCode 第 2043 題《簡(jiǎn)易銀行系統(tǒng)》Simple Bank System難度為中等Tag 為「模擬」。任務(wù)是為一款銀行設(shè)計(jì)程序自動(dòng)化執(zhí)行所有傳入的交易轉(zhuǎn)賬、存款和取款。銀行共有 $n$ 個(gè)賬戶(hù)編號(hào)從 $1$ 到 $n$。每個(gè)賬戶(hù)的初始余額存儲(chǔ)在一個(gè)下標(biāo)從 $0$ 開(kāi)始的整數(shù)數(shù)組balance中其中第 $(i 1)$ 個(gè)賬戶(hù)的初始余額是balance[i]。所有交易必須有效才會(huì)被執(zhí)行。交易有效需要同時(shí)滿(mǎn)足下面兩個(gè)條件指定的賬戶(hù)數(shù)量在 $1$ 和 $n$ 之間取款或者轉(zhuǎn)賬所需的錢(qián)的總數(shù)小于等于賬戶(hù)余額。需要實(shí)現(xiàn)Bank類(lèi)共四個(gè)方法方法簽名行為Bank(long[] balance)使用下標(biāo)從 $0$ 開(kāi)始的整數(shù)數(shù)組balance初始化該對(duì)象boolean transfer(int account1, int account2, long money)從編號(hào)account1的賬戶(hù)向編號(hào)account2的賬戶(hù)轉(zhuǎn)賬money美元成功返回true否則返回falseboolean deposit(int account, long money)向編號(hào)account的賬戶(hù)存款money美元成功返回true否則返回falseboolean withdraw(int account, long money)從編號(hào)account的賬戶(hù)取款money美元成功返回true否則返回false示例解析與數(shù)據(jù)范圍題目給出的示例輸入 [Bank, withdraw, transfer, deposit, transfer, withdraw] [[[10, 100, 20, 50, 30]], [3, 10], [5, 1, 20], [5, 20], [3, 4, 15], [10, 50]] 輸出 [null, true, true, true, false, false]逐步推演如下Bank bank new Bank([10, 100, 20, 50, 30])初始化 5 個(gè)賬戶(hù)余額分別為 $10、100、20、50、30$。bank.withdraw(3, 10)返回true。賬戶(hù) 3 余額為 $20 \ge 10$可以取款 $10$余額變?yōu)?$20 - 10 10$。bank.transfer(5, 1, 20)返回true。賬戶(hù) 5 余額為 $30 \ge 20$可以轉(zhuǎn)賬。賬戶(hù) 5 余額變?yōu)?$30 - 20 10$賬戶(hù) 1 余額變?yōu)?$10 20 30$。bank.deposit(5, 20)返回true。賬戶(hù) 5 存款 $20$余額變?yōu)?$10 20 30$。bank.transfer(3, 4, 15)返回false。賬戶(hù) 3 當(dāng)前余額只有 $10 15$余額不足無(wú)法轉(zhuǎn)賬 $15$。bank.withdraw(10, 50)返回false。賬戶(hù) 10 不存在$n 5$交易無(wú)效。數(shù)據(jù)范圍提示是本題選擇數(shù)據(jù)結(jié)構(gòu)與數(shù)值類(lèi)型的關(guān)鍵依據(jù)$n balance.length$$1 \le n,\ account,\ account_1,\ account_2 \le 10^5$$0 \le balance[i],\ money \le 10^{12}$transfer、deposit、withdraw三個(gè)函數(shù)各自最多被調(diào)用 $10^4$ 次思路分析把「規(guī)則」翻譯成代碼本題沒(méi)有任何隱藏技巧題解給出的核心思路只有一句話根據(jù)題意進(jìn)行模擬即可。真正考驗(yàn)的是兩點(diǎn)第一正確拆解「有效交易」的兩條規(guī)則。規(guī)則一針對(duì)賬戶(hù)編號(hào)規(guī)則二針對(duì)金額。注意兩條規(guī)則的適用對(duì)象并不完全相同deposit存款只涉及一個(gè)賬戶(hù)因此只需校驗(yàn)「賬戶(hù)存在」這一條規(guī)則不需要校驗(yàn)余額——存款不存在余額不足的問(wèn)題withdraw取款需要同時(shí)校驗(yàn)「賬戶(hù)存在」和「余額充足」transfer轉(zhuǎn)賬涉及兩個(gè)賬戶(hù)需要兩個(gè)賬戶(hù)都存在缺一不可并且轉(zhuǎn)出方余額充足。第二正確建立「賬戶(hù)編號(hào)」與「數(shù)組下標(biāo)」的映射。題面規(guī)定賬戶(hù)編號(hào)從 $1$ 開(kāi)始而balance數(shù)組下標(biāo)從 $0$ 開(kāi)始因此編號(hào)為account的賬戶(hù)對(duì)應(yīng)數(shù)組下標(biāo)account - 1。這是最容易寫(xiě)錯(cuò)的地方若直接使用val[account]訪問(wèn)編號(hào) $1$ 號(hào)賬戶(hù)會(huì)被錯(cuò)誤地映射到下標(biāo) $1$即第 $2$ 個(gè)賬戶(hù)而編號(hào) $n$ 的賬戶(hù)訪問(wèn)val[n]會(huì)直接越界。在原題解中這兩點(diǎn)被濃縮為一個(gè)check(int account)輔助函數(shù)boolean check(int account) { return 1 account account val.length; }check一次性完成了「編號(hào)下限 $1$」和「編號(hào)上限 $n$」的雙重校驗(yàn)三個(gè)交易方法都能復(fù)用。Java 參考實(shí)現(xiàn)含逐行注釋以下是原題解中給出的 Java 參考代碼保留了其簡(jiǎn)潔風(fēng)格并補(bǔ)充了注釋class Bank { long[] val; // 賬戶(hù)余額數(shù)組val[i] 表示編號(hào)為 (i 1) 的賬戶(hù)余額 // 初始化直接持有 balance 數(shù)組的引用不額外拷貝 public Bank(long[] balance) { val balance; } // 校驗(yàn)賬戶(hù)編號(hào)是否合法編號(hào)范圍 [1, val.length] boolean check(int account) { return 1 account account val.length; } // 轉(zhuǎn)賬從賬戶(hù) a 向賬戶(hù) b 轉(zhuǎn) c 美元 public boolean transfer(int a, int b, long c) { // 規(guī)則一兩個(gè)賬戶(hù)都必須存在 if (!check(a) || !check(b)) return false; // 規(guī)則二轉(zhuǎn)出方余額必須充足余額恰好等于金額時(shí)也允許 if (val[a - 1] c) { val[a - 1] - c; // 轉(zhuǎn)出方扣款 val[b - 1] c; // 轉(zhuǎn)入方入賬 return true; } return false; } // 存款向賬戶(hù) a 存入 c 美元只校驗(yàn)賬戶(hù)存在無(wú)需校驗(yàn)余額 public boolean deposit(int a, long c) { if (!check(a)) return false; val[a - 1] c; return true; } // 取款從賬戶(hù) a 取出 c 美元 public boolean withdraw(int a, long c) { if (!check(a)) return false; // 余額必須充足 if (val[a - 1] c) { val[a - 1] - c; return true; } return false; } }實(shí)現(xiàn)細(xì)節(jié)與邊界情況剖析這一節(jié)把參考實(shí)現(xiàn)中容易被忽略的細(xì)節(jié)逐個(gè)拆開(kāi)它們是本題通過(guò)率的關(guān)鍵。1. 為什么要用long而不是int這是本題最重要的數(shù)據(jù)范圍陷阱。balance[i]和money的上限都是 $10^{12}$而int的最大值約為 $2.1 \times 10^9$單筆金額就已經(jīng)超出int范圍更不用說(shuō)累加后的余額。用long之后是否仍然安全可以做一次上界估算單個(gè)賬戶(hù)的最大余額初始 $10^{12}$之后每次操作最多增加 $10^{12}$存款或轉(zhuǎn)入操作次數(shù)上限 $10^4$ 次因此單賬戶(hù)余額上界約為 $10^{12} 10^4 \times 10^{12} \approx 10^{16}$全部賬戶(hù)余額總和不變轉(zhuǎn)賬只是余額在兩賬戶(hù)間流動(dòng)上界為 $n \times 10^{12} \le 10^5 \times 10^{12} 10^{17}$。兩者都遠(yuǎn)小于long的上限 $2^{63} - 1 \approx 9.2 \times 10^{18}$因此使用long在整個(gè)數(shù)據(jù)范圍內(nèi)都不會(huì)溢出。這也解釋了題解中所有方法簽名都使用long的原因。2.transfer的校驗(yàn)順序先查賬戶(hù)再查余額。參考實(shí)現(xiàn)嚴(yán)格遵循「先check(a) || check(b)再判斷val[a-1] c」的順序。這個(gè)順序很重要如果先訪問(wèn)val[a-1]再校驗(yàn)編號(hào)遇到非法賬戶(hù)如示例中的賬戶(hù) 10就會(huì)產(chǎn)生數(shù)組越界。先做存在性校驗(yàn)可以同時(shí)保證訪問(wèn)安全性這也是check被設(shè)計(jì)為獨(dú)立函數(shù)的原因。3. 余額比較用而非。題面規(guī)定「取款或者轉(zhuǎn)賬需要的錢(qián)的總數(shù)小于或者等于賬戶(hù)余額」即為有效因此余額恰好等于金額時(shí)也允許交易代碼中使用。4. 存款為何不需要余額判斷存款只會(huì)增加余額不存在「余額不足」的可能因此deposit只需通過(guò)check校驗(yàn)賬戶(hù)存在性即可這也是它與withdraw在結(jié)構(gòu)上對(duì)稱(chēng)、在判斷上不對(duì)稱(chēng)的原因。5. 自轉(zhuǎn)賬account1 account2的邊界。若兩個(gè)參數(shù)傳入同一賬戶(hù)邏輯上「先扣款再入賬」會(huì)先減后加、凈額為零只要余額充足即可返回true實(shí)現(xiàn)無(wú)需特判。當(dāng)然在實(shí)際銀行系統(tǒng)中自轉(zhuǎn)賬通常會(huì)被業(yè)務(wù)層攔截但按本題規(guī)則它是允許的。6. 初始化時(shí)直接持有引用。Bank(long[] balance)直接把數(shù)組引用賦給成員變量val沒(méi)有拷貝。因?yàn)楹罄m(xù)所有操作都發(fā)生在val上這樣既簡(jiǎn)潔又不影響正確性若擔(dān)心外部修改可以復(fù)制一份balance.clone()但按題目約定傳入的數(shù)組只用于初始化直接持有引用即可。其他語(yǔ)言的等價(jià)實(shí)現(xiàn)原題解僅給出 Java 代碼。按照同一套模擬邏輯可以給出以下等價(jià)實(shí)現(xiàn)與 38. 外觀數(shù)列、2069. 模擬行走機(jī)器人 II 等文章的多語(yǔ)言風(fēng)格保持一致供不同語(yǔ)言棧的讀者提交參考。C 實(shí)現(xiàn)class Bank { public: vectorlong long val; Bank(vectorlong long balance) { val balance; } bool check(int account) { return 1 account account (int)val.size(); } bool transfer(int a, int b, long long c) { if (!check(a) || !check(b)) return false; if (val[a - 1] c) { val[a - 1] - c; val[b - 1] c; return true; } return false; } bool deposit(int a, long long c) { if (!check(a)) return false; val[a - 1] c; return true; } bool withdraw(int a, long long c) { if (!check(a)) return false; if (val[a - 1] c) { val[a - 1] - c; return true; } return false; } };Python 實(shí)現(xiàn)class Bank: def __init__(self, balance: List[int]): self.val balance def check(self, account: int) - bool: return 1 account len(self.val) def transfer(self, account1: int, account2: int, money: int) - bool: if not self.check(account1) or not self.check(account2): return False if self.val[account1 - 1] money: self.val[account1 - 1] - money self.val[account2 - 1] money return True return False def deposit(self, account: int, money: int) - bool: if not self.check(account): return False self.val[account - 1] money return True def withdraw(self, account: int, money: int) - bool: if not self.check(account): return False if self.val[account - 1] money: self.val[account - 1] - money return True return FalsePython 的整數(shù)是任意精度類(lèi)型天然不存在溢出問(wèn)題直接使用int即可。TypeScript 實(shí)現(xiàn)class Bank { private val: number[]; constructor(balance: number[]) { this.val balance; } private check(account: number): boolean { return 1 account account this.val.length; } transfer(account1: number, account2: number, money: number): boolean { if (!this.check(account1) || !this.check(account2)) return false; if (this.val[account1 - 1] money) { this.val[account1 - 1] - money; this.val[account2 - 1] money; return true; } return false; } deposit(account: number, money: number): boolean { if (!this.check(account)) return false; this.val[account - 1] money; return true; } withdraw(account: number, money: number): boolean { if (!this.check(account)) return false; if (this.val[account - 1] money) { this.val[account - 1] - money; return true; } return false; } }需要說(shuō)明的是TypeScript / JavaScript 的number是 IEEE 754 雙精度浮點(diǎn)其安全整數(shù)上限為 $2^{53} \approx 9.0 \times 10^{15}$而本題單賬戶(hù)余額在極端數(shù)據(jù)下可逼近 $10^{16}$理論上存在精度風(fēng)險(xiǎn)常規(guī)測(cè)試數(shù)據(jù)下number即可通過(guò)若追求絕對(duì)安全可以改用BigInt。復(fù)雜度分析時(shí)間復(fù)雜度$O(1)$。transfer、deposit、withdraw三個(gè)方法均只涉及常數(shù)次數(shù)組讀寫(xiě)與比較不隨賬戶(hù)數(shù) $n$ 或操作次數(shù)增長(zhǎng)。初始化Bank構(gòu)造器為 $O(n)$數(shù)組引用賦值本身是 $O(1)$但傳入的數(shù)組本身長(zhǎng)度為 $n$?？臻g復(fù)雜度$O(n)$。需要存儲(chǔ)長(zhǎng)度為 $n$ 的余額數(shù)組val。綜合來(lái)看三類(lèi)操作各最多調(diào)用 $10^4$ 次總時(shí)間復(fù)雜度為 $O(10^4)$ 級(jí)別遠(yuǎn)在題目限制之內(nèi)。倉(cāng)庫(kù)中的延伸閱讀模擬題方法論本題在 LogicStack-LeetCode 倉(cāng)庫(kù)中被歸類(lèi)為「模擬」可以在 Index/模擬.md 中找到完整的模擬題索引倉(cāng)庫(kù) README.md 對(duì)該系列的整體定位是「日更」的算法刷題倉(cāng)庫(kù)每篇題解按 Tag 分類(lèi)歸檔。在模擬索引中本題No.2043的推薦指數(shù)為 屬于值得反復(fù)練習(xí)的經(jīng)典模擬題。把本題與倉(cāng)庫(kù)中的其他模擬題對(duì)照可以提煉出模擬類(lèi)題目的通用方法論精讀題面逐條列出規(guī)則。本題的規(guī)則只有「賬戶(hù)存在」和「余額充足」兩條很多同學(xué)出錯(cuò)是因?yàn)榘岩?guī)則想復(fù)雜了比如給存款也加了余額判斷。先做存在性/合法性校驗(yàn)再訪問(wèn)數(shù)據(jù)。本題的check函數(shù)先于一切數(shù)組訪問(wèn)執(zhí)行杜絕越界66. 加一 中則表現(xiàn)為對(duì)進(jìn)位t的循環(huán)終止條件i 0 || t ! 0的兜底處理。把狀態(tài)維護(hù)在簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)里。本題直接用數(shù)組存余額即可無(wú)需哈希表2069. 模擬行走機(jī)器人 II 則用單個(gè)步數(shù)變量loc加取模維護(hù)外圈位置同樣是「最簡(jiǎn)單結(jié)構(gòu) 規(guī)則分情況」的組合。對(duì)數(shù)據(jù)范圍保持敏感選對(duì)數(shù)值類(lèi)型。本題long的選用、38. 外觀數(shù)列 中對(duì) $n \le 30$ 使用打表優(yōu)化都是「數(shù)據(jù)范圍決定實(shí)現(xiàn)策略」的體現(xiàn)。此外轉(zhuǎn)賬的「先扣款后入賬」與 2. 兩數(shù)相加 中「逐位相加并維護(hù)進(jìn)位」同屬對(duì)運(yùn)算過(guò)程的忠實(shí)模擬——區(qū)別僅在于本題的運(yùn)算發(fā)生在賬戶(hù)余額上而后者發(fā)生在十進(jìn)制數(shù)位上。掌握本題后遇到任何「按規(guī)則執(zhí)行交易/操作并返回結(jié)果」的設(shè)計(jì)題都可以沿用「合法性校驗(yàn) → 狀態(tài)更新 → 返回結(jié)果」三段式結(jié)構(gòu)快速求解。贊分享教程文檔【免費(fèi)下載鏈接】LogicStack-LeetCode公眾號(hào)「宮水三葉的刷題日記」刷穿 LeetCode 系列文章源碼項(xiàng)目地址https://gitcode.com/gh_mirrors/lo/LogicStack-LeetCode點(diǎn)擊查看免費(fèi)下載相關(guān)推薦LeetCode 1773 統(tǒng)計(jì)匹配檢索規(guī)則的物品數(shù)量模擬解法與多語(yǔ)言實(shí)現(xiàn)LogicStack-LeetCode 刷題筆記LeetCode 1773 統(tǒng)計(jì)匹配檢索規(guī)則的物品數(shù)量模擬解法與多語(yǔ)言實(shí)現(xiàn)LogicStack LeetCode 刷題筆記 本篇技術(shù)指南以 LogicSt教程文檔LeetCode 1047 題解刪除字符串中的所有相鄰重復(fù)項(xiàng)——棧與數(shù)組模擬的多種實(shí)現(xiàn)LogicStack-LeetCode 刷題筆記LeetCode 1047 題解刪除字符串中的所有相鄰重復(fù)項(xiàng)——棧與數(shù)組模擬的多種實(shí)現(xiàn)LogicStack LeetCode 刷題筆記 導(dǎo)讀 本文圍繞 L教程文檔LeetCode 1669 合并兩個(gè)鏈表中等題解區(qū)間斷鏈與整鏈拼接的鏈表模擬實(shí)戰(zhàn)LogicStack-LeetCode 刷題日記LeetCode 1669 合并兩個(gè)鏈表中等題解區(qū)間斷鏈與整鏈拼接的鏈表模擬實(shí)戰(zhàn)LogicStack LeetCode 刷題日記 本篇技術(shù)指南以「宮水教程文檔上一篇APISIX Stream 代理TCP/UDP 動(dòng)態(tài)代理實(shí)戰(zhàn)指南配置、路由匹配與 TLS/PROXY 協(xié)議下一篇如何控制 OpenSRE 的 Token 成本/cost 每會(huì)話成本追蹤實(shí)用指南創(chuàng)作聲明：本文部分內(nèi)容由AI輔助生成（AIGC），僅供參考