序

前言

第 1章 初識(shí)算法 1

1.1 算法無(wú)處不在 1

1.2 算法是什么 5

1.2.1 算法定義 5

1.2.2 數(shù)據(jù)結(jié)構(gòu)定義 5

1.2.3 數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系 5

1.3 小結(jié) 7

第 2章 復(fù)雜度分析 9

2.1 算法效率評(píng)估 9

2.1.1 實(shí)際測(cè)試 9

2.1.2 理論估算 10

2.2 迭代與遞歸 10

2.2.1 迭代 11

2.2.2 遞歸 13

2.2.3 兩者對(duì)比 18

2.3 時(shí)間復(fù)雜度 19

2.3.1 統(tǒng)計(jì)時(shí)間增長(zhǎng)趨勢(shì) 20

2.3.2 函數(shù)漸近上界 21

2.3.3 推算方法 22

2.3.4 常見(jiàn)類型 23

2.3.5 最差、最佳、平均時(shí)間復(fù)雜度 30

2.4 空間復(fù)雜度 32

2.4.1 算法相關(guān)空間 32

2.4.2 推算方法 33

2.4.3 常見(jiàn)類型 34

2.4.4 權(quán)衡時(shí)間與空間 38

2.5 小結(jié) 39

第3章 數(shù)據(jù)結(jié)構(gòu) 42

3.1 數(shù)據(jù)結(jié)構(gòu)分類 42

3.1.1 邏輯結(jié)構(gòu)：線性與非線性 42

3.1.2 物理結(jié)構(gòu)：連續(xù)與分散 43

3.2 基本數(shù)據(jù)類型 45

3.3 數(shù)字編碼* 46

3.3.1 原碼、反碼和補(bǔ)碼 46

3.3.2 浮點(diǎn)數(shù)編碼 49

3.4 字符編碼* 50

3.4.1 ASCII字符集 50

3.4.2 GBK字符集 51

3.4.3 Unicode字符集 51

3.4.4 UTF-8編碼 53

3.4.5 編程語(yǔ)言的字符編碼 54

3.5 小結(jié) 55

第4章 數(shù)組與鏈表 58

4.1 數(shù)組 58

4.1.1 數(shù)組常用操作 58

4.1.2 數(shù)組的優(yōu)點(diǎn)與局限性 62

4.1.3 數(shù)組典型應(yīng)用 63

4.2 鏈表 63

4.2.1 鏈表常用操作 64

4.2.2 數(shù)組與鏈表對(duì)比 67

4.2.3 常見(jiàn)鏈表類型 67

4.2.4 鏈表典型應(yīng)用 68

4.3 列表 69

4.3.1 列表常用操作 69

4.3.2 列表實(shí)現(xiàn) 71

4.4 內(nèi)存與緩存* 73

4.4.1 計(jì)算機(jī)存儲(chǔ)設(shè)備 73

4.4.2 數(shù)據(jù)結(jié)構(gòu)的內(nèi)存效率 75

4.4.3 數(shù)據(jù)結(jié)構(gòu)的緩存效率 75

4.5 小結(jié) 76

第5章 棧與隊(duì)列 81

5.1 棧 81

5.1.1 棧的常用操作 81

5.1.2 棧的實(shí)現(xiàn) 82

5.1.3 兩種實(shí)現(xiàn)對(duì)比 86

5.1.4 棧的典型應(yīng)用 87

5.2 隊(duì)列 87

5.2.1 隊(duì)列常用操作 88

5.2.2 隊(duì)列實(shí)現(xiàn) 89

5.2.3 隊(duì)列典型應(yīng)用 94

5.3 雙向隊(duì)列 95

5.3.1 雙向隊(duì)列常用操作 95

5.3.2 雙向隊(duì)列實(shí)現(xiàn)* 96

5.3.3 雙向隊(duì)列應(yīng)用 104

5.4 小結(jié) 104

第6章 哈希表 107

6.1 哈希表 107

6.1.1 哈希表常用操作 108

6.1.2 哈希表簡(jiǎn)單實(shí)現(xiàn) 109

6.1.3 哈希沖突與擴(kuò)容 111

6.2 哈希沖突 113

6.2.1 鏈?zhǔn)降刂?113

6.2.2 開放尋址 116

6.2.3 編程語(yǔ)言的選擇 120

6.3 哈希算法 120

6.3.1 哈希算法的目標(biāo) 121

6.3.2 哈希算法的設(shè)計(jì) 122

6.3.3 常見(jiàn)哈希算法 124

6.3.4 數(shù)據(jù)結(jié)構(gòu)的哈希值 124

6.4 小結(jié) 125

第7章 樹 129

7.1 二叉樹 129

7.1.1 二叉樹常見(jiàn)術(shù)語(yǔ) 129

7.1.2 二叉樹基本操作 131

7.1.3 常見(jiàn)二叉樹類型 132

7.1.4 二叉樹的退化 134

7.2 二叉樹遍歷 135

7.2.1 層序遍歷 135

7.2.2 前序、中序、后序遍歷 136

7.3 二叉樹數(shù)組表示 138

7.3.1 表示完美二叉樹 138

7.3.2 表示任意二叉樹 139

7.3.3 優(yōu)點(diǎn)與局限性 142

7.4 二叉搜索樹 142

7.4.1 二叉搜索樹的操作 143

7.4.2 二叉搜索樹的效率 151

7.4.3 二叉搜索樹常見(jiàn)應(yīng)用 151

7.5 AVL樹* 152

7.5.1 AVL樹常見(jiàn)術(shù)語(yǔ) 153

7.5.2 AVL樹旋轉(zhuǎn) 154

7.5.3 AVL樹常用操作 160

7.5.4 AVL樹典型應(yīng)用 161

7.6 小結(jié) 162

第8章 堆 165

8.1 堆 165

8.1.1 堆的常用操作 166

8.1.2 堆的實(shí)現(xiàn) 167

8.1.3 堆的常見(jiàn)應(yīng)用 177

8.2 建堆操作 177

8.2.1 借助入堆操作實(shí)現(xiàn) 177

8.2.2 通過(guò)遍歷堆化實(shí)現(xiàn) 178

8.2.3 復(fù)雜度分析 178

8.3 Top-k問(wèn)題 180

8.3.1 方法一：遍歷選擇 180

8.3.2 方法二：排序 180

8.3.3 方法三：堆 181

8.4 小結(jié) 182

第9章 圖 184

9.1 圖 184

9.1.1 圖的常見(jiàn)類型與術(shù)語(yǔ) 185

9.1.2 圖的表示 186

9.1.3 圖的常見(jiàn)應(yīng)用 188

9.2 圖的基礎(chǔ)操作 188

9.2.1 基于鄰接矩陣的實(shí)現(xiàn) 188

9.2.2 基于鄰接表的實(shí)現(xiàn) 192

9.2.3 效率對(duì)比 196

9.3 圖的遍歷 196

9.3.1 廣度優(yōu)先遍歷 196

9.3.2 深度優(yōu)先遍歷 198

9.4 小結(jié) 200

第 10章 搜索 203

10.1 二分查找 203

10.1.1 區(qū)間表示方法 207

10.1.2 優(yōu)點(diǎn)與局限性 208

10.2 二分查找插入點(diǎn) 209

10.2.1 無(wú)重復(fù)元素的情況 209

10.2.2 存在重復(fù)元素的情況 210

10.3 二分查找邊界 212

10.3.1 查找左邊界 212

10.3.2 查找右邊界 212

10.4 哈希優(yōu)化策略 214

10.4.1 線性查找：以時(shí)間換空間 214

10.4.2 哈希查找：以空間換時(shí)間 215

10.5 重識(shí)搜索算法 217

10.5.1 暴力搜索 217

10.5.2 自適應(yīng)搜索 218

10.5.3 搜索方法選取 218

10.6 小結(jié) 220

第 11章 排序 222

11.1 排序算法 222

11.1.1 評(píng)價(jià)維度 222

11.1.2 理想排序算法 223

11.2 選擇排序 224

11.3 冒泡排序 229

11.3.1 算法流程 231

11.3.2 效率優(yōu)化 232

11.3.3 算法特性 233

11.4 插入排序 233

11.4.1 算法流程 234

11.4.2 算法特性 235

11.4.3 插入排序的優(yōu)勢(shì) 235

11.5 快速排序 235

11.5.1 算法流程 239

11.5.2 算法特性 240

11.5.3 快速排序?yàn)槭裁纯?240

11.5.4 基準(zhǔn)數(shù)優(yōu)化 241

11.5.5 尾遞歸優(yōu)化 242

11.6 歸并排序 242

11.6.1 算法流程 243

11.6.2 算法特性 248

11.6.3 鏈表排序 248

11.7 堆排序 249

11.7.1 算法流程 249

11.7.2 算法特性 250

11.8 桶排序 250

11.8.1 算法流程 251

11.8.2 算法特性 252

11.8.3 如何實(shí)現(xiàn)平均分配 252

11.9 計(jì)數(shù)排序 253

11.9.1 簡(jiǎn)單實(shí)現(xiàn) 254

11.9.2 完整實(shí)現(xiàn) 255

11.9.3 算法特性 256

11.9.4 局限性 256

11.10 基數(shù)排序 257

11.10.1 算法流程 257

11.10.2 算法特性 259

11.11 小結(jié) 259

第 12章 分治 263

12.1 分治算法 263

12.1.1 如何判斷分治問(wèn)題 264

12.1.2 通過(guò)分治提升效率 264

12.1.3 分治常見(jiàn)應(yīng)用 266

12.2 分治搜索策略 267

12.3 構(gòu)建二叉樹問(wèn)題 269

12.4 漢諾塔問(wèn)題 273

12.5 小結(jié) 280

第 13章 回溯 282

13.1 回溯算法 282

13.1.1 嘗試與回退 283

13.1.2 剪枝 288

13.1.3 框架代碼 289

13.1.4 常用術(shù)語(yǔ) 291

13.1.5 優(yōu)點(diǎn)與局限性 291

13.1.6 回溯典型例題 292

13.2 全排列問(wèn)題 292

13.2.1 無(wú)相等元素的情況 293

13.2.2 考慮相等元素的情況 295

13.3 子集和問(wèn)題 298

13.3.1 無(wú)重復(fù)元素的情況 298

13.3.2 考慮重復(fù)元素的情況 302

13.4 n 皇后問(wèn)題 304

13.5 小結(jié) 308

第 14章 動(dòng)態(tài)規(guī)劃 310

14.1 初探動(dòng)態(tài)規(guī)劃 310

14.1.1 方法一：暴力搜索 311

14.1.2 方法二：記憶化搜索 313

14.1.3 方法三：動(dòng)態(tài)規(guī)劃 314

14.1.4 空間優(yōu)化 316

14.2 動(dòng)態(tài)規(guī)劃問(wèn)題特性 316

14.2.1 最優(yōu)子結(jié)構(gòu) 316

14.2.2 無(wú)后效性 319

14.3 動(dòng)態(tài)規(guī)劃解題思路 321

14.3.1 問(wèn)題判斷 321

14.3.2 問(wèn)題求解步驟 322

14.4 0-1 背包問(wèn)題 332

14.5 完全背包問(wèn)題 343

14.5.1 完全背包問(wèn)題 344

14.5.2 零錢兌換問(wèn)題 I348

14.5.3 零錢兌換問(wèn)題II 350

14.6 編輯距離問(wèn)題 352

14.7 小結(jié) 356

第 15章 貪心 359

15.1 貪心算法 359

15.1.1 貪心算法的優(yōu)點(diǎn)與局限性 360

15.1.2 貪心算法特性 361

15.1.3 貪心算法解題步驟 362

15.1.4 貪心算法典型例題 363

15.2 分?jǐn)?shù)背包問(wèn)題 363

15.3 最大容量問(wèn)題 366

15.4 最大切分乘積問(wèn)題 373

15.5 小結(jié) 377

附錄A 術(shù)語(yǔ)表 379