計算機編程之美：數(shù)據(jù)結構與算法之美+設計模式之美

《數(shù)據(jù)結構與算法之美（全彩印刷）》

目錄

第 1章　復雜度分析　1

1.1　復雜度分析（上）：如何分析代碼的執(zhí)行效率和資源消耗　2

1.1.1　復雜度分析的意義　2

1.1.2　大O復雜度表示法　2

1.1.3　時間復雜度分析方法　4

1.1.4　幾種常見的時間復雜度量級　5

1.1.5　空間復雜度分析方法　7

1.1.6　內容小結　7

1.1.7　思考題　8

1.2　復雜度分析（下）：詳解最好、最壞、平均、均攤這4種時間復雜度　8

1.2.1　最好時間復雜度和最壞時間復雜度　8

1.2.2　平均時間復雜度　9

1.2.3　均攤時間復雜度　10

1.2.4　內容小結　11

1.2.5　思考題　12

第 2章　數(shù)組、鏈表、棧和隊列　13

2.1　數(shù)組（上）：為什么數(shù)組的下標一般從0開始編號　14

2.2　數(shù)組（下）：數(shù)據(jù)結構中的數(shù)組和編程語言中的數(shù)組的區(qū)別　19

2.3　鏈表（上）：如何基于鏈表實現(xiàn)LRU緩存淘汰算法　23

2.4　鏈表（下）：借助哪些技巧可以輕松地編寫鏈表相關的復雜代碼　30

2.5　棧：如何實現(xiàn)瀏覽器的前進和后退功能　35

2.6　隊列：如何實現(xiàn)線程池等有限資源池的請求排隊功能　40

第3章　遞歸、排序、二分查找　46

3.1　遞歸：如何用3行代碼找到“Z終推薦人”　47

3.2　尾遞歸：如何借助尾遞歸避免遞歸過深導致的堆棧溢出　53

3.3　排序算法基礎：從哪幾個方面分析排序算法　55

3.4　O(n2)排序：為什么插入排序比冒泡排序更受歡迎　58

3.5　O(nlogn)排序：如何借助快速排序思想快速查找第K大元素　64

3.6　線性排序：如何根據(jù)年齡給100萬個用戶排序　72

3.7　排序優(yōu)化：如何實現(xiàn)一個高性能的通用的排序函數(shù)　78

3.8　二分查找：如何用Z省內存的方式實現(xiàn)快速查找功能　80

3.9　二分查找的變體：如何快速定位IP地址對應的歸屬地　85

第4章　哈希表、位圖和哈希算法　91

4.1　哈希表（上）：Word軟件的單詞拼寫檢查功能是如何實現(xiàn)的　92

4.2　哈希表（中）：如何打造一個工業(yè)級的哈希表　96

4.3　哈希表（下）：如何利用哈希表優(yōu)化LRU緩存淘汰算法　101

4.4　位圖：如何實現(xiàn)網(wǎng)頁“爬蟲”中的網(wǎng)址鏈接去重功能　106

4.5　哈希算法：如何防止數(shù)據(jù)庫脫庫后用戶信息泄露　111

第5章　樹　117

5.1　樹和二叉樹：什么樣的二叉樹適合用數(shù)組存儲　118

5.2　二叉查找樹：相比哈希表，二叉查找樹有何優(yōu)勢　122

5.3　平衡二叉查找樹：為什么紅黑樹如此受歡迎　128

5.4　遞歸樹：如何借助樹求遞歸算法的時間復雜度　131

5.5　B+樹：MySQL數(shù)據(jù)庫索引是如何實現(xiàn)的　135

第6章　堆　141

6.1　堆：如何維護動態(tài)集合的最值　142

6.2　堆排序：為什么說堆排序沒有快速排序快　147

6.3　堆的應用：如何快速獲取Top 10熱門搜索關鍵詞　151

第7章　跳表、并查集、線段樹和樹狀數(shù)組　157

7.1　跳表：Redis中的有序集合類型是如何實現(xiàn)的　158

7.2　并查集：路徑壓縮和按秩合并這兩個優(yōu)化是否沖突　163

7.3　線段樹：如何查找獵聘網(wǎng)中積分排在第K位的獵頭　168

7.4　樹狀數(shù)組：如何實現(xiàn)一個高性能、低延遲的實時排行榜　174

第8章　字符串匹配算法　179

8.1　BF算法：編程語言中的查找、替換函數(shù)是怎樣實現(xiàn)的　180

8.2　RK算法：如何借助哈希算法實現(xiàn)高效的字符串匹配　182

8.3　BM算法：如何實現(xiàn)文本編輯器中的查找和替換功能　185

8.4　KMP算法：如何借助BM算法理解KMP算法　194

8.5　Trie樹：如何實現(xiàn)搜索引擎的搜索關鍵詞提示功能　198

8.6　AC自動機：如何用多模式串匹配實現(xiàn)敏感詞過濾　204

第9章　圖　210

9.1　圖的表示：如何存儲微博、微信等社交網(wǎng)絡中的好友關系　211

9.2　深度優(yōu)先搜索和廣度優(yōu)先搜索：如何找出社交網(wǎng)絡中的三度好友關系　216

9.3　拓撲排序：如何確定代碼源文件的編譯依賴關系　221

9.4　單源Z短路徑：地圖軟件如何“計算”Z優(yōu)出行路線　225

9.5　多源Z短路徑：如何利用Floyd算法解決傳遞閉包問題　231

9.6　啟發(fā)式搜索：如何用A*算法實現(xiàn)游戲中的尋路功能　233

9.7　Z小生成樹：如何隨機生成游戲中的迷宮地圖　238

9.8　Z大流：如何解決單身交友聯(lián)誼中的Z多匹配問題　245

第 10章　貪心、分治、回溯和動態(tài)規(guī)劃　251

10.1　貪心算法：如何利用貪心算法實現(xiàn)霍夫曼編碼　252

10.2　分治算法：談一談大規(guī)模計算框架MapReduce中的分治思想　256

10.3　回溯算法：從電影《蝴蝶效應》中學習回溯算法的核心思想　260

10.4　初識動態(tài)規(guī)劃：如何巧妙解決“雙11”購物時的湊單問題　264

10.5　動態(tài)規(guī)劃理論：徹底理解最優(yōu)子結構、無后效性和重復子問題　272

10.6　動態(tài)規(guī)劃實戰(zhàn)：如何實現(xiàn)搜索引擎中的拼寫糾錯功能　278

第 11章　數(shù)據(jù)結構和算法實戰(zhàn)　284

11.1　實戰(zhàn)1：剖析Redis的常用數(shù)據(jù)類型對應的數(shù)據(jù)結構　285

11.2　實戰(zhàn)2：剖析搜索引擎背后的經(jīng)典數(shù)據(jù)結構和算法　288

11.3　實戰(zhàn)3：剖析微服務鑒權和限流背后的數(shù)據(jù)結構和算法　293

11.4　實戰(zhàn)4：用學過的數(shù)據(jù)結構和算法實現(xiàn)短網(wǎng)址服務　299

附錄A　思考題答案　304

《設計模式之美》

第 1章概述　1

1.1　為什么學習代碼設計　2

1.1.1　編寫高質量的代碼　2

1.1.2　應對復雜代碼的開發(fā)　2

1.1.3　程序員的基本功　3

1.1.4　職場發(fā)展的必備技能　4

1.1.5　思考題　4

1.2　如何評價代碼質量　4

1.2.1　可維護性（maintainability）　5

1.2.2　可讀性（readability）　6

1.2.3　可擴展性（extensibility）　6

1.2.4　靈活性（flexibility）　6

1.2.5　簡潔性（simplicity）　7

1.2.6　可復用性（reusability）　7

1.2.7　可測試性（testability）　7

1.2.8　思考題　8

1.3　如何寫出高質量代碼　8

1.3.1　面向對象　8

1.3.2　設計原則　8

1.3.3　設計模式　9

1.3.4　代碼規(guī)范　9

1.3.5　重構技巧　10

1.3.6　思考題　11

1.4　如何避免過度設計　 11

1.4.1　代碼設計的初衷是提高代碼質量　11

1.4.2　代碼設計的原則是“先有問題，后有方案”　12

1.4.3　代碼設計的應用場景是復雜代碼　12

1.4.4　持續(xù)重構可有效避免過度設計　12

1.4.5　不要脫離具體的場景談代碼設計　13

1.4.6　思考題　13

第 2章面向對象編程范式　14

2.1　當我們在談論面向對象時，到底在談論什么　15

2.2　封裝、抽象、繼承和多態(tài)為何而生　17

2.3　如何進行面向對象分析、面向對象設計和面向對象編程　25

2.4　面向對象編程與面向過程編程和函數(shù)式編程之間的區(qū)別　35

2.5　哪些代碼看似面向對象編程風格，實則面向過程編程風格　45

2.6　基于“貧血”模型的傳統(tǒng)開發(fā)模式是否違背OOP　51

2.7　接口和抽象類：如何使用普通類模擬接口和抽象類　59

2.8　基于接口而非實現(xiàn)編程：有沒有必要為每個類都定義接口　65

2.9　組合優(yōu)于繼承：什么情況下可以使用繼承　70

第3章設計原則　75

3.1　單一職責原則：如何判定某個類的職責是否單一　76

3.2　開閉原則：只要修改代碼，就一定違反開閉原則嗎　79

3.3　里氏替換原則：什么樣的代碼才算違反里氏替換原則　86

3.4　接口隔離原則：如何理解該原則中的“接口”　89

3.5　依賴反轉原則：依賴反轉與控制反轉、依賴注入有何關系　97

3.6　KISS原則和YAGNI原則：二者是一回事嗎　100

3.7　DRY原則：相同的兩段代碼就一定違反DRY原則嗎　104

3.8　LoD：如何實現(xiàn)代碼的“高內聚、低耦合”　110

第4章代碼規(guī)范　117

4.1　命名與注釋：如何精準命名和編寫注釋　118

4.2　代碼風格：與其爭論標準，不如團隊統(tǒng)一　121

4.3　編程技巧：小技巧，大作用，一招提高代碼的可讀性　123

第5章重構技巧　130

5.1　重構四要素：目的、對象、時機和方法　131

5.2　單元測試：保證重構不出錯的有效手段　133

5.3　代碼的可測試性：如何編寫可測試代碼　139

5.4　解耦：哪些方法可以用來解耦代碼　147

5.5　重構案例：將ID生成器代碼從“能用”重構為“好用”　150

第6章創(chuàng)建型設計模式　166

6.1　單例模式（上）：為什么不推薦在項目中使用單例模式　167

6.2　單例模式（下）：如何設計實現(xiàn)一個分布式單例模式　177

6.3　工廠模式（上）：如何解耦復雜對象的創(chuàng)建和使用　180

6.4　工廠模式（下）：如何設計實現(xiàn)一個依賴注入容器　188

6.5　建造者模式：什么情況下必須用建造者模式創(chuàng)建對象　194

6.6　原型模式：如何快速復制（clone）一個哈希表　200

第7章結構型設計模式　208

7.1　代理模式：代理模式在RPC、緩存和監(jiān)控等場景中的應用　209

7.2　裝飾器模式：剖析Java IO類庫的底層設計思想　213

7.3　適配器模式：如何利用適配器模式解決代碼的不兼容問題　219

7.4　橋接模式：如何將M×N的繼承關系簡化為M+N的組合關系　230

7.5　門面模式：如何設計接口以兼顧接口的易用性和通用性　231

7.6　組合模式：一種應用在樹形結構上的特殊設計模式　233

7.7　享元模式：如何利用享元模式降低系統(tǒng)的內存開銷　239

第8章行為型設計模式　249

8.1　觀察者模式：如何實現(xiàn)一個異步非阻塞的EventBus框架　250

8.2　模板方法模式（上）：模板方法模式在JDK、Servlet、JUnit中的應用　261

8.3　模板方法模式（下）：模板方法模式與回調有何區(qū)別和聯(lián)系　267

8.4　策略模式：如何避免冗長的if-else和switch-case語句　273

8.5　職責鏈模式：框架中的過濾器、攔截器和插件是如何實現(xiàn)的　282

8.6　狀態(tài)模式：游戲和工作流引擎中常用的狀態(tài)機是如何實現(xiàn)的　297

8.7　迭代器模式（上）：為什么要用迭代器遍歷集合　306

8.8　迭代器模式（下）：如何實現(xiàn)一個支持快照功能的迭代器　315

8.9　訪問者模式：為什么支持雙分派的編程語言不需要訪問者模式　320

8.10　備忘錄模式：如何優(yōu)雅地實現(xiàn)數(shù)據(jù)防丟失、撤銷和恢復功能　330

8.11　命令模式：如何設計實現(xiàn)基于命令模式的手游服務器　334

8.12　解釋器模式：如何設計實現(xiàn)一個自定義接口告警規(guī)則的功能　337

8.13　中介模式：什么時候使用中介模式？什么時候使用觀察者模式？　343