簡(jiǎn)介《軟件設(shè)計(jì)師中級(jí)考試知識(shí)點(diǎn)整理》以 docx 筆記形式面向軟考軟件設(shè)計(jì)師中級(jí)考生兼顧需要系統(tǒng)復(fù)盤面向?qū)ο笈c數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)的開發(fā)者可用于考前梳理考點(diǎn)、定位薄弱環(huán)節(jié)。正文圍繞類與對(duì)象、繼承、多態(tài)、封裝、抽象化與組合展開逐條解釋單一職責(zé)、開閉、李氏替換、依賴倒置、接口隔離、迪米特和合成復(fù)用七大原則并按創(chuàng)建型、結(jié)構(gòu)型、行為型歸納常見設(shè)計(jì)模式同時(shí)整理 UML 圖及繼承、組合、關(guān)聯(lián)等關(guān)系樹與二叉樹特性、查找二叉樹、平衡二叉樹、AVL 樹與紅黑樹、排序算法情景對(duì)比、線性表和串等模塊目錄層級(jí)明確方便按知識(shí)點(diǎn)跳轉(zhuǎn)復(fù)習(xí)。資源包內(nèi)含 1 個(gè) docx 文件約 31.83MB已有 894 人學(xué)習(xí)。整體偏提綱式梳理對(duì)易混淆的設(shè)計(jì)原則、模式分類和樹結(jié)構(gòu)特性可作對(duì)照記憶適合沖刺階段配合真題逐項(xiàng)核對(duì)快速建立知識(shí)框架。1. 一份目錄先給出答案筆記的價(jià)值不在厚度在能不能定位打開目錄會(huì)先愣一下前面連續(xù)七八個(gè)標(biāo)題共用第 4 頁(yè)中間十幾個(gè)標(biāo)題擠在 9、10 頁(yè)整份目錄最后停在 40 多頁(yè)。這說(shuō)明它是按主題塊排的不是按頁(yè)排的。對(duì)備考軟考中級(jí)軟件設(shè)計(jì)師的人來(lái)說(shuō)這恰好是個(gè)信號(hào)——一份知識(shí)點(diǎn)整理能不能用不看排版看它有沒(méi)有把面向?qū)ο?、?shù)據(jù)結(jié)構(gòu)、算法、軟件工程、網(wǎng)絡(luò)、數(shù)據(jù)庫(kù)這幾條主線串成可檢索的骨架。這份 docx 覆蓋面基本貼著大綱走適合已有基礎(chǔ)、需要快速回歸和查漏的人零基礎(chǔ)拿它當(dāng)唯一教材會(huì)讀得很吃力因?yàn)楹芏鄺l目只有結(jié)論沒(méi)有推導(dǎo)。2. 面向?qū)ο笈c設(shè)計(jì)模式7 大原則在題干里怎么被認(rèn)出來(lái)面向?qū)ο筮@部分在下午題里出得不算多但上午題偏愛兩種問(wèn)法給一段場(chǎng)景問(wèn)體現(xiàn)了哪條原則給一個(gè)類圖問(wèn)屬于哪類模式。筆記把類、對(duì)象、繼承、多態(tài)、封裝、抽象、組合這七個(gè)基本概念放在最前面緊接著進(jìn)七大原則這個(gè)編排順序是對(duì)的——原則本身就是概念的組合應(yīng)用先背概念再背原則等于把同一件事記兩遍。2.1 七大原則的判定順序與題干信號(hào)詞同時(shí)出現(xiàn)多個(gè)信號(hào)時(shí)我一般按這個(gè)優(yōu)先級(jí)往下篩單一職責(zé) → 開閉 → 里氏替換 → 依賴倒置 → 接口隔離 → 迪米特 → 合成復(fù)用。排在前面的更結(jié)構(gòu)性出題人寫場(chǎng)景時(shí)往往就是沖著它去的排在后面的更實(shí)現(xiàn)性多數(shù)時(shí)候是干擾項(xiàng)。原則一句話內(nèi)核題干高頻信號(hào)詞典型反例單一職責(zé) SRP一個(gè)類只有一個(gè)引起變化的原因該類同時(shí)負(fù)責(zé)……和……一個(gè)類既管連接池又管報(bào)表渲染開閉 OCP對(duì)擴(kuò)展開放對(duì)修改關(guān)閉新增一種……時(shí)不修改原有代碼加一個(gè)支付渠道就要?jiǎng)?if-else里氏替換 LSP子類能替換父類且行為不變子類重寫后父類原有調(diào)用出錯(cuò)子類強(qiáng)化入?yún)⑿ｒ?yàn)、拋父類未聲明的異常依賴倒置 DIP高層與低層都依賴抽象高層模塊不應(yīng)依賴低層實(shí)現(xiàn)業(yè)務(wù)類里直接 new 具體驅(qū)動(dòng)接口隔離 ISP接口拆細(xì)不強(qiáng)迫依賴無(wú)用方法接口中存在大量空實(shí)現(xiàn)一個(gè)胖接口塞二十個(gè)方法迪米特 LoD只與直接朋友通信調(diào)用鏈過(guò)長(zhǎng)中間類轉(zhuǎn)手a.getB().getC().doWork()合成復(fù)用 CRP優(yōu)先組合而非繼承繼承層次過(guò)深難以維護(hù)為復(fù)用兩個(gè)方法繼承整個(gè)基類最容易混的兩組要單獨(dú)拎出來(lái)。第一組是里氏替換和依賴倒置里氏管的是子類型的行為契約判斷依據(jù)是替換后調(diào)用方有沒(méi)有感知到差異依賴倒置管的是依賴的方向判斷依據(jù)是代碼里有沒(méi)有出現(xiàn)具體類名。第二組是單一職責(zé)和接口隔離單一職責(zé)約束的是類接口隔離約束的是接口前者看變化原因有幾個(gè)后者看客戶端被迫實(shí)現(xiàn)了幾個(gè)用不上的方法。提示題干里出現(xiàn)子類不能替代父類時(shí)別急著選里氏替換。如果場(chǎng)景描述的是父類里塞了子類用不到的方法答案通常是接口隔離因?yàn)閱?wèn)題出在接口粒度而不是繼承契約。2.2 三種模式分類的記憶錨點(diǎn)原文對(duì)創(chuàng)建型、結(jié)構(gòu)型、行為型的描述用了工廠模式、抽象工廠模式、builder 模式這種中英混寫讀的時(shí)候要注意統(tǒng)一成中文名否則考場(chǎng)上看到建造者模式會(huì)反應(yīng)不過(guò)來(lái)。分類數(shù)量成員一句話錨點(diǎn)創(chuàng)建型5工廠方法、抽象工廠、建造者、原型、單例都在解決對(duì)象怎么造出來(lái)結(jié)構(gòu)型7適配器、橋接、組合、裝飾器、外觀、享元、代理都在解決對(duì)象怎么拼起來(lái)行為型11職責(zé)鏈、命令、解釋器、迭代器、中介者、備忘錄、觀察者、狀態(tài)、策略、模板方法、訪問(wèn)者都在解決職責(zé)怎么分、消息怎么傳按造、拼、分三個(gè)動(dòng)詞記比按字母順序背可靠得多。享元是最容易被歸錯(cuò)的一個(gè)很多人一看共享對(duì)象狀態(tài)就往行為型放其實(shí)它處理的是對(duì)象的結(jié)構(gòu)復(fù)用屬于結(jié)構(gòu)型。訪問(wèn)者放行為型也是同理——它變的是對(duì)元素的操作不是元素本身的結(jié)構(gòu)。2.3 用一段代碼把開閉與依賴倒置跑出來(lái)原則背得再熟不如自己寫一遍反例再改一遍。下面這段是加一個(gè)折扣類型就要改結(jié)算類的典型翻車寫法改造成策略之后兩個(gè)原則同時(shí)成立。from abc import ABC, abstractmethod class Discount(ABC): 折扣抽象高層只認(rèn)這個(gè)接口不認(rèn)具體實(shí)現(xiàn) abstractmethod def apply(self, amount: float) - float: ... class NoDiscount(Discount): def apply(self, amount: float) - float: return amount class PercentDiscount(Discount): def __init__(self, rate: float): self.rate rate # 0.9 表示九折1.0 表示原價(jià) def apply(self, amount: float) - float: return amount * self.rate class Checkout: def __init__(self, strategy: Discount): self._strategy strategy # 構(gòu)造注入依賴的是抽象 def total(self, amount: float) - float: return self._strategy.apply(amount) if __name__ __main__: print(Checkout(NoDiscount()).total(100.0)) # 100.0 print(Checkout(PercentDiscount(0.9)).total(100.0)) # 90.0邏輯說(shuō)明Checkout里沒(méi)有任何if 類型 ...的分支新增滿減階梯價(jià)只需要再寫一個(gè)Discount子類Checkout一行不動(dòng)這就是開閉原則的落地形態(tài)。Checkout.__init__的形參類型標(biāo)注是Discount而不是PercentDiscount高層模塊依賴抽象而非具體實(shí)現(xiàn)這就是依賴倒置。參數(shù)上要注意rate的取值范圍用小數(shù)表示若改成百分?jǐn)?shù)90 表示九折必須在文檔里寫清楚否則調(diào)用方傳 0.9 和傳 90 會(huì)得到完全不同的結(jié)果這類單位不一致在下午題里也常作為陷阱出現(xiàn)。再補(bǔ)一個(gè)反向驗(yàn)證把PercentDiscount.apply改成先校驗(yàn)amount 0負(fù)數(shù)直接拋異常。此時(shí)用子類替換父類的調(diào)用方原本傳 0 不報(bào)錯(cuò)的代碼開始報(bào)錯(cuò)行為契約被破壞這就是里氏替換的違反。自己動(dòng)手改一遍比看十遍定義管用。3. UML 關(guān)系與樹結(jié)構(gòu)兩種層次感考點(diǎn)的交叉審法UML 和數(shù)據(jù)結(jié)構(gòu)在筆記里是挨著放的看似不相關(guān)其實(shí)考的是同一種能力——判斷層次和強(qiáng)弱。UML 關(guān)系判斷的是類與類之間的耦合強(qiáng)度樹結(jié)構(gòu)判斷的是結(jié)點(diǎn)之間的層級(jí)約束。把這兩塊放在一起復(fù)習(xí)腦子里建立的是一套關(guān)系模型而不是兩堆散點(diǎn)。3.1 UML 關(guān)系的強(qiáng)度階梯原文只列了繼承、組合、關(guān)聯(lián)三種實(shí)際考綱要求區(qū)分六種缺了聚合、依賴和實(shí)現(xiàn)。按耦合從弱到強(qiáng)排成一條線判斷時(shí)從弱往強(qiáng)推比死記符號(hào)穩(wěn)。關(guān)系圖形符號(hào)耦合強(qiáng)度生命周期代碼里的常見形態(tài)依賴虛線箭頭最弱無(wú)關(guān)方法參數(shù)、局部變量、返回值關(guān)聯(lián)實(shí)線可帶箭頭弱各自獨(dú)立成員變量持有對(duì)方引用聚合空心菱形中部分可獨(dú)立存在成員變量構(gòu)造時(shí)傳入組合實(shí)心菱形強(qiáng)部分隨整體銷毀成員變量?jī)?nèi)部 new 出來(lái)泛化實(shí)線空心三角強(qiáng)繼承class B extends A實(shí)現(xiàn)虛線空心三角強(qiáng)契約class B implements I聚合和組合的區(qū)分只看一句整體銷毀時(shí)部分還能不能活。學(xué)校和學(xué)生是聚合學(xué)校撤銷了學(xué)生還在訂單和訂單明細(xì)是組合訂單刪了明細(xì)沒(méi)有獨(dú)立意義。圖上的菱形是空是實(shí)直接對(duì)應(yīng)這個(gè)語(yǔ)義記混的時(shí)候回到這句話就行。泛化與實(shí)現(xiàn)的區(qū)分也常被問(wèn)。泛化是is-a且?guī)?shí)現(xiàn)繼承子類直接拿到父類的方法體實(shí)現(xiàn)只是can-do接口里沒(méi)有方法體子類必須自己寫。題干里出現(xiàn)抽象類和接口二選一時(shí)看有沒(méi)有共享的默認(rèn)實(shí)現(xiàn)。3.2 二叉樹性質(zhì)與查找樹、平衡樹的判定樹這塊筆記里有個(gè)表述要注意原文寫二叉樹的重要特性左子樹和右子樹的高度不能超過(guò) 1。這句話描述的是平衡二叉樹AVL的約束不是普通二叉樹的特性。普通二叉樹只有下面這幾條硬性質(zhì)。性質(zhì)表達(dá)式適用對(duì)象第 i 層最多結(jié)點(diǎn)數(shù)2^(i-1)任意二叉樹深度為 k 最多結(jié)點(diǎn)數(shù)2^k - 1任意二叉樹葉子與度為 2 的結(jié)點(diǎn)關(guān)系n0 n2 1任意二叉樹n 個(gè)結(jié)點(diǎn)的完全二叉樹深度?log2 n? 1完全二叉樹編號(hào) i 的左右孩子、父結(jié)點(diǎn)2i、2i1、?i/2?順序存儲(chǔ)的完全二叉樹左右子樹高度差絕對(duì)值 ≤ 1平衡二叉樹n0 n2 1這條建議用代碼驗(yàn)證一遍比背公式記得住也順便把完全二叉樹的編號(hào)規(guī)則過(guò)一遍。import math def walk_complete_tree(n: int): 按完全二叉樹的順序編號(hào)規(guī)則統(tǒng)計(jì)各類結(jié)點(diǎn) n0 n1 n2 0 for i in range(1, n 1): children [c for c in (2 * i, 2 * i 1) if c n] if len(children) 0: n0 1 elif len(children) 1: n1 1 else: n2 1 return n0, n1, n2 for total in (10, 15, 31): n0, n1, n2 walk_complete_tree(total) depth math.floor(math.log2(total)) 1 print(fn{total} 深度{depth} 葉子{n0} 單分支{n1} 雙分支{n2} 校驗(yàn)n0n21 - {n0 n2 1})邏輯說(shuō)明2*i和2*i1是完全二叉樹順序存儲(chǔ)的編號(hào)規(guī)則超出n就說(shuō)明該孩子不存在據(jù)此可以反推每個(gè)結(jié)點(diǎn)的度數(shù)。math.floor(math.log2(total)) 1對(duì)應(yīng)深度公式注意total為 1 時(shí)結(jié)果是 1邊界正確。運(yùn)行結(jié)果里n10時(shí)葉子 5 個(gè)、雙分支 4 個(gè)5 4 1成立。參數(shù)上唯一要小心的是n必須是正整數(shù)傳 0 會(huì)導(dǎo)致log2報(bào)錯(cuò)。查找二叉樹BST的判定標(biāo)準(zhǔn)只有一條好用的中序遍歷序列單調(diào)遞增。平衡二叉樹則看每個(gè)結(jié)點(diǎn)的平衡因子左子樹高度減右子樹高度絕對(duì)值不超過(guò) 1。紅黑樹屬于近似平衡插入刪除時(shí)旋轉(zhuǎn)次數(shù)比 AVL 少適合寫操作頻繁的場(chǎng)景堆是完全二叉樹 堆序只保證父結(jié)點(diǎn)與子結(jié)點(diǎn)的大小關(guān)系兄弟之間無(wú)序這一點(diǎn)經(jīng)常被拿來(lái)出判斷題。3.3 排序?qū)Ρ缺硪B穩(wěn)定性一起背各種排序算法的復(fù)雜度表誰(shuí)都會(huì)背出錯(cuò)多半出在穩(wěn)定性那一列。算法平均最壞最好輔助空間穩(wěn)定性冒泡O(n2)O(n2)O(n)O(1)穩(wěn)定插入O(n2)O(n2)O(n)O(1)穩(wěn)定選擇O(n2)O(n2)O(n2)O(1)不穩(wěn)定希爾O(n^1.3)O(n2)O(n)O(1)不穩(wěn)定快速O(n log n)O(n2)O(n log n)O(log n)不穩(wěn)定歸并O(n log n)O(n log n)O(n log n)O(n)穩(wěn)定堆O(n log n)O(n log n)O(n log n)O(1)不穩(wěn)定基數(shù)O(d(nr))O(d(nr))O(d(nr))O(nr)穩(wěn)定穩(wěn)定的四個(gè)是冒泡、插入、歸并、基數(shù)其余都不穩(wěn)定。這個(gè)結(jié)論光背容易記反跑一遍記錄對(duì)key, tag的排序看相同 key 的相對(duì)次序有沒(méi)有變一分鐘就能確認(rèn)。def selection_sort_records(records): a records[:] n len(a) for i in range(n - 1): m i for j in range(i 1, n): if a[j][0] a[m][0]: # 只比較 key忽略 tag m j a[i], a[m] a[m], a[i] # 遠(yuǎn)距離交換會(huì)打亂相等元素的相對(duì)次序 return a def bubble_sort_records(records): a records[:] n len(a) for i in range(n - 1): swapped False for j in range(n - 1 - i): if a[j][0] a[j 1][0]: # 嚴(yán)格大于才交換相等時(shí)保持原位 a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: # 一趟無(wú)交換最好情況 O(n) break return a data [(2, a), (2, b), (1, c)] print(selection_sort_records(data)) # [(1,c), (2,b), (2,a)] a、b 次序被換不穩(wěn)定 print(bubble_sort_records(data)) # [(1,c), (2,a), (2,b)] a、b 次序保留穩(wěn)定邏輯說(shuō)明把每個(gè)元素寫成(排序鍵, 標(biāo)記)的二元組排序后只看標(biāo)記字母的順序就能判斷穩(wěn)定性。選擇排序不穩(wěn)定問(wèn)題出在最小值與首位遠(yuǎn)距離交換這一步它會(huì)把相等元素中靠前的那個(gè)甩到后面去。冒泡排序的交換條件是嚴(yán)格大于相等時(shí)不動(dòng)作所以穩(wěn)定。參數(shù)上records必須是可切片復(fù)制的序列函數(shù)內(nèi)部做了[:]拷貝不會(huì)污染原列表。4. 算法與開發(fā)模型復(fù)雜度估算、模型選型的落地判斷算法部分的難點(diǎn)不在寫代碼在給一個(gè)場(chǎng)景判斷該用哪種思想。軟件工程部分的難點(diǎn)不在背模型名字在給一個(gè)項(xiàng)目特征判斷該選哪個(gè)模型。這兩類題本質(zhì)上是同一種從特征反推方法。4.1 分治、回溯、貪心、動(dòng)態(tài)規(guī)劃怎么區(qū)分算法思想成立條件典型題目判斷關(guān)鍵句分治子問(wèn)題獨(dú)立、可合并二分查找、歸并排序、快速排序?qū)?wèn)題分成規(guī)模更小的同類子問(wèn)題回溯解空間可枚舉、能剪枝N 皇后、圖著色、迷宮求解嘗試、失敗則回退貪心每步局部最優(yōu)可推出全局最優(yōu)部分背包、哈夫曼編碼、Prim、Kruskal每次選當(dāng)前最好的動(dòng)態(tài)規(guī)劃最優(yōu)子結(jié)構(gòu) 重疊子問(wèn)題0-1 背包、最長(zhǎng)公共子序列、矩陣連乘子問(wèn)題被重復(fù)計(jì)算被問(wèn)得最多的對(duì)比是 0-1 背包和部分背包。物品不可分割時(shí)只能用動(dòng)態(tài)規(guī)劃因?yàn)樨澬臅?huì)翻車容量 10物品 A 重 6 值 10、B 重 5 值 9、C 重 5 值 9按單位價(jià)值貪心先拿 A剩下容量 4 什么也裝不下總價(jià)值 10最優(yōu)解是拿 B 和 C總價(jià)值 18。物品可分割時(shí)貪心就是最優(yōu)的因?yàn)槭Ｓ嗳萘磕苎b小數(shù)部分?；厮莺蛣?dòng)態(tài)規(guī)劃的邊界也常混?；厮菔亲叩降自倩赝藭?huì)訪問(wèn)同一個(gè)狀態(tài)很多次動(dòng)態(tài)規(guī)劃是把中間結(jié)果存起來(lái)同一狀態(tài)只算一次。題干里出現(xiàn)記憶化填表狀態(tài)轉(zhuǎn)移方程基本鎖定動(dòng)態(tài)規(guī)劃出現(xiàn)剪枝深度優(yōu)先遍歷解空間樹鎖定回溯。4.2 復(fù)雜度用實(shí)測(cè)驗(yàn)證別只背表O(n2) 和 O(n log n) 的分界點(diǎn)在哪里光看公式?jīng)]感覺。寫個(gè)小腳本統(tǒng)計(jì)比較次數(shù)拿比值看增長(zhǎng)趨勢(shì)比硬背結(jié)論直觀得多。import math, random def bubble_compare_count(arr): a arr[:] n len(a) cnt 0 for i in range(n - 1): swapped False for j in range(n - 1 - i): cnt 1 # 每比較一次計(jì)數(shù)一次 if a[j] a[j 1]: a[j], a[j 1] a[j 1], a[j] swapped True if not swapped: break return cnt random.seed(7) for n in (32, 64, 128, 256, 512): data [random.random() for _ in range(n)] # 隨機(jī)序列避開有序觸發(fā)提前退出 c bubble_compare_count(data) print(fn{n:4d} 比較次數(shù){c:7d} c/(n*logn){c / (n * math.log2(n)):.2f})邏輯說(shuō)明隨機(jī)輸入下冒泡排序不會(huì)提前退出比較次數(shù)接近n(n-1)/2。把結(jié)果除以n log n如果比值隨 n 線性增長(zhǎng)說(shuō)明分子是 n2 量級(jí)。這個(gè)方法的通用價(jià)值在于考場(chǎng)上一時(shí)想不起某個(gè)算法的時(shí)間復(fù)雜度用規(guī)模翻倍、耗時(shí)變幾倍的思路也能推出來(lái)——翻倍后耗時(shí)變 4 倍是 O(n2)變 2 倍多一點(diǎn)的通常是 O(n log n)。參數(shù)上random.seed固定隨機(jī)源保證多次運(yùn)行結(jié)果一致方便對(duì)照。常見算法的時(shí)間復(fù)雜度結(jié)論整理成一句話二分查找 O(log n)、歸并排序 O(n log n)、快速排序平均 O(n log n) 最壞 O(n2)、堆排序 O(n log n)、斐波那契遞歸樸素實(shí)現(xiàn) O(2^n)、矩陣連乘動(dòng)態(tài)規(guī)劃 O(n3)。4.3 開發(fā)模型選型對(duì)照筆記里排了瀑布、原型、增量、螺旋、V 模型、噴泉、敏捷七種容易的問(wèn)題是知道名字但選不出來(lái)。模型適用場(chǎng)景關(guān)鍵特征主要風(fēng)險(xiǎn)瀑布需求明確且穩(wěn)定階段嚴(yán)格串行、文檔驅(qū)動(dòng)后期變更代價(jià)大原型需求模糊、需快速確認(rèn)先做可運(yùn)行樣品原型被當(dāng)成成品交付增量可分批交付、核心先行按功能塊逐個(gè)發(fā)布需要良好的架構(gòu)規(guī)劃螺旋大型高風(fēng)險(xiǎn)項(xiàng)目每輪含風(fēng)險(xiǎn)分析成本高、管理復(fù)雜V 模型強(qiáng)測(cè)試要求的嵌入類項(xiàng)目開發(fā)與測(cè)試階段一一對(duì)應(yīng)靈活性差噴泉面向?qū)ο箝_發(fā)各階段無(wú)縫迭代、可回溯缺乏明確里程碑敏捷需求頻繁變化的小團(tuán)隊(duì)短迭代、可工作軟件優(yōu)先文檔可能不足XP 作為敏捷的具體實(shí)踐考點(diǎn)集中在四條結(jié)對(duì)編程、測(cè)試先行、小型發(fā)布、持續(xù)重構(gòu)。題干里出現(xiàn)兩人共用一臺(tái)機(jī)器先寫測(cè)試再寫實(shí)現(xiàn)每?jī)芍馨l(fā)布一次指向的都是 XP 而不是泛泛的敏捷。螺旋模型和增量模型也常被混區(qū)分點(diǎn)在于螺旋每輪必須做風(fēng)險(xiǎn)分析增量只是分批交付。4.4 關(guān)鍵路徑正推逆推和總時(shí)差關(guān)鍵路徑是上午題的?？褪止に阋槐椴浑y但活動(dòng)一多就容易算錯(cuò)。規(guī)則只有兩條正推求最早開始時(shí)間取所有前置活動(dòng)最早完成時(shí)間的最大值逆推求最晚開始時(shí)間取所有后置活動(dòng)最晚開始時(shí)間的最小值?？倳r(shí)差 最晚開始 - 最早開始為 0 的活動(dòng)連起來(lái)就是關(guān)鍵路徑。def critical_path(acts): acts: {活動(dòng)名: (工期, [前置活動(dòng)])} ES, EF {}, {} def forward(name): if name in EF: return dur, preds acts[name] for p in preds: forward(p) ES[name] max((EF[p] for p in preds), default0) EF[name] ES[name] dur for k in acts: forward(k) total max(EF.values()) succ {k: [] for k in acts} for k, (_, preds) in acts.items(): for p in preds: succ[p].append(k) LS, LF {}, {} def backward(name): if name in LS: return for s in succ[name]: backward(s) LF[name] min((LS[s] for s in succ[name]), defaulttotal) LS[name] LF[name] - acts[name][0] for k in acts: backward(k) slack {k: LS[k] - ES[k] for k in acts} path [k for k in acts if slack[k] 0] return total, slack, path acts { A: (3, []), # 需求梳理 B: (4, [A]), # 方案設(shè)計(jì) C: (2, [A]), # 環(huán)境準(zhǔn)備 D: (5, [B, C]), # 核心開發(fā) E: (2, [C]), # 接口聯(lián)調(diào) F: (3, [D, E]), # 驗(yàn)收測(cè)試 } print(critical_path(acts)) # (15, {A:0,B:0,C:2,D:0,E:5,F:0}, [A,B,D,F])邏輯說(shuō)明forward用遞歸保證前置活動(dòng)先算default0處理沒(méi)有前置的起始活動(dòng)backward反向遞歸終點(diǎn)活動(dòng)的LF取總工期。返回的slack是每個(gè)活動(dòng)的總時(shí)差為 0 說(shuō)明一天都拖不得。參數(shù)上活動(dòng)名必須唯一前置列表里的名字必須已定義否則forward會(huì)拋KeyError——手工畫圖時(shí)漏掉某個(gè)前置活動(dòng)算出來(lái)的工期會(huì)偏短這是最常見的錯(cuò)誤。5. 避坑與常見問(wèn)題筆記里最容易背反的 5 個(gè)點(diǎn)這份筆記整體結(jié)構(gòu)清楚但有幾處表述和筆誤會(huì)讓人在復(fù)習(xí)時(shí)繞進(jìn)去我自己就翻過(guò)車。下面五條按現(xiàn)象 → 原因 → 解決記錄都是我實(shí)際遇到過(guò)的問(wèn)題。5.1 按目錄頁(yè)碼跳轉(zhuǎn)找不到內(nèi)容現(xiàn)象照目錄上的頁(yè)碼去翻連續(xù)七八個(gè)標(biāo)題都指向同一頁(yè)翻過(guò)去發(fā)現(xiàn)那一頁(yè)擠了十來(lái)個(gè)知識(shí)點(diǎn)實(shí)際內(nèi)容排在后面幾頁(yè)。原因這份目錄是 Word 自動(dòng)生成后整段粘貼的域沒(méi)有更新頁(yè)碼停留在上一次排版的狀態(tài)而且原始筆記本身是按主題塊組織不是按頁(yè)分。解決不要用頁(yè)碼定位用標(biāo)題層級(jí)定位。如果需要在電子版里檢索先把它轉(zhuǎn)成帶層級(jí)標(biāo)記的文本下一章的腳本就是干這個(gè)的再用關(guān)鍵詞搜索比翻頁(yè)碼可靠。5.2 把平衡二叉樹的高度約束當(dāng)成普通二叉樹性質(zhì)現(xiàn)象原文寫二叉樹的重要特性左子樹和右子樹的高度不能超過(guò) 1照著背遇到普通二叉樹的題目也套這句判斷直接錯(cuò)。原因這句話是 AVL 樹的平衡條件被錯(cuò)寫到了二叉樹概述里。普通二叉樹對(duì)左右子樹高度沒(méi)有任何限制可以是一條鏈。解決三條硬性質(zhì)記住——第 i 層最多 2^(i-1) 個(gè)結(jié)點(diǎn)、深度 k 最多 2^k-1 個(gè)結(jié)點(diǎn)、n0 n2 1。高度差絕對(duì)值不超過(guò) 1 只屬于平衡二叉樹做題時(shí)看到平衡兩個(gè)字才啟用這條。5.3 關(guān)鍵詞檢索不到因?yàn)樵挠泄P誤現(xiàn)象想在文檔里搜里氏替換搜不到搜復(fù)雜度也搜不到幾處。原因原文寫的是李氏替換原則和McCabe 復(fù)制度還有網(wǎng)絡(luò)完全控制技術(shù)應(yīng)為網(wǎng)絡(luò)安全控制技術(shù)。這類輸入法誤寫在整理型筆記里很常見它不影響閱讀但會(huì)讓全文檢索失效。解決檢索時(shí)做同義詞展開。里氏/李氏、復(fù)雜度/復(fù)制度、網(wǎng)絡(luò)安全/網(wǎng)絡(luò)完全、建造者/builder四個(gè)詞對(duì)都記一下。熟手重建索引時(shí)可以在腳本里加一層別名映射把常見誤寫一起收進(jìn)去。5.4 排序算法的穩(wěn)定性記反現(xiàn)象把快速排序、堆排序、選擇排序、希爾排序記成穩(wěn)定的選擇題一對(duì)答案全錯(cuò)。原因只盯著復(fù)雜度那一列背穩(wěn)定性那一列靠印象補(bǔ)而印象里快排很快所以應(yīng)該穩(wěn)定這種直覺是錯(cuò)的。解決只記穩(wěn)定的四個(gè)——冒泡、插入、歸并、基數(shù)其余的默認(rèn)不穩(wěn)定遇到拿不準(zhǔn)的用上一章那份(key, tag)腳本跑一遍。別用直覺推這是純記憶題。5.5 設(shè)計(jì)模式歸類張冠李戴現(xiàn)象把建造者放進(jìn)結(jié)構(gòu)型把享元放進(jìn)行為型答題時(shí)二選一必錯(cuò)。原因建造者原文寫的是英文 builder讀的時(shí)候沒(méi)和中文名對(duì)應(yīng)上享元的共享字樣容易被理解成對(duì)象間的交互行為。解決按造、拼、分三個(gè)動(dòng)詞重新分組創(chuàng)建型 5 個(gè)解決對(duì)象怎么造結(jié)構(gòu)型 7 個(gè)解決對(duì)象怎么拼行為型 11 個(gè)解決職責(zé)怎么分。享元?dú)w結(jié)構(gòu)型因?yàn)樗幚淼氖菍?duì)象內(nèi)部狀態(tài)的共享結(jié)構(gòu)不涉及對(duì)象之間的消息傳遞。6. 把 docx 變成可檢索索引我用 python-docx 做的一次改造純靠 Word 的查找功能翻一份四十多頁(yè)的筆記效率很低尤其是想同時(shí)看某個(gè)知識(shí)點(diǎn)在哪些章節(jié)出現(xiàn)過(guò)的時(shí)候。我一般的做法是先用python-docx把段落和樣式層級(jí)導(dǎo)出來(lái)生成一份帶標(biāo)題標(biāo)記的 Markdown 副本之后所有檢索都在副本上做。from docx import Document doc Document(軟件設(shè)計(jì)師中級(jí)考試知識(shí)點(diǎn)整理.docx) lines [] for p in doc.paragraphs: text p.text.strip() if not text: continue style p.style.name # Heading 1 / Heading 2 / Normal if style.startswith(Heading 1): lines.append(f## {text}) elif style.startswith(Heading 2): lines.append(f### {text}) else: lines.append(text) with open(軟考筆記_索引.md, w, encodingutf-8) as f: f.write(\n\n.join(lines)) print(f導(dǎo)出段落 {len(lines)} 條)邏輯說(shuō)明p.style.name返回的是樣式名Heading 1對(duì)應(yīng)章、Heading 2對(duì)應(yīng)節(jié)據(jù)此還原出兩級(jí)標(biāo)題結(jié)構(gòu)正文段落原樣保留。參數(shù)上要注意兩點(diǎn)一是原始文檔如果用的是自定義樣式名比如標(biāo)題 1startswith的判斷要跟著改二是導(dǎo)出用utf-8編碼別用系統(tǒng)默認(rèn)否則在部分終端里打開是亂碼。生成的 Markdown 副本只用于檢索不用于閱讀排版所以段落之間的空行用\n\n簡(jiǎn)單拼接就夠了。有了副本之后檢索就變成一行命令的事# 在所有標(biāo)題和正文里找關(guān)鍵詞帶行號(hào)輸出方便回原文定位 rg -n McCabe|環(huán)路|復(fù)雜度|復(fù)制度 軟考筆記_索引.md # 只看標(biāo)題層級(jí)快速確認(rèn)某個(gè)知識(shí)點(diǎn)歸屬哪一章 rg -n ^#{2,3} 軟考筆記_索引.md | rg 測(cè)試|維護(hù)|CMMI第二條命令里^#{2,3}匹配二級(jí)和三級(jí)標(biāo)題管道再過(guò)濾一次幾秒鐘就能看出軟件測(cè)試相關(guān)的小節(jié)分布在哪幾個(gè)章下面比在 Word 導(dǎo)航窗格里一個(gè)個(gè)展開快得多。從那以后我每次拿到這類整理型筆記都強(qiáng)制先跑一遍導(dǎo)出腳本再做復(fù)習(xí)計(jì)劃——不是為了排版好看是因?yàn)橹挥邪呀Y(jié)構(gòu)攤平成可檢索的文本才能發(fā)現(xiàn)原文里那些頁(yè)碼錯(cuò)位、術(shù)語(yǔ)筆誤和歸類錯(cuò)誤。這些東西不攤開看考場(chǎng)上就會(huì)變成實(shí)打?qū)嵉氖Х贮c(diǎn)。希望幫到你。本文還有配套的精品資源點(diǎn)擊獲取