算法思維：競賽真題精選精講(第2版)

丹尼爾·津加羅（Daniel Zingaro）

多倫多大學計算機科學系副教授，以其獨特的互動式教學方法和在“主動學習”領域的開創性研究而享譽國際。他的課程涵蓋計算機基礎、數據結構與算法、程序設計、操作系統等核心方向。除本書外，他還是Learn to Code by Solving Problems和Learn AI-Assisted Python Programming等書的作者，深受全球計算機學習者的喜愛。

第 1章　哈希表 1

1.1　問題1：獨特的雪花 1

1.1.1　題幹 1

1.1.2　簡化問題 3

1.1.3　解決核心問題 4

1.1.4　解法1：成對比較 7

1.1.5　解法2：減少工作量 11

1.2　哈希表概覽 16

1.2.1　設計哈希表 16

1.2.2　為什麼使用哈希表 18

1.3　問題2：登錄風波 19

1.3.1　題幹 19

1.3.2　解法1：遍歷所有密碼 20

1.3.3　解法2：使用哈希表 22

1.4　問題3：拼寫檢查 27

1.4.1　題幹 27

1.4.2　考慮哈希表 28

1.4.3　臨時解決方案 30

1.5　小結 33

1.6　說明 33

第 2章　樹與遞歸 34

2.1　問題1：萬聖節掃蕩 34

2.1.1　題幹 34

2.1.2　二叉樹 36

2.1.3　求解用例 38

2.1.4　二叉樹的表示 38

2.1.5　收集所有糖果 42

2.1.6　一個完全不同的解法 47

2.1.7　最小遍歷街道數 52

2.1.8　讀取輸入 54

2.2　為什麼使用遞歸 60

2.3　問題2：後代距離 61

2.3.1　題幹 61

2.3.2　讀取輸入 63

2.3.3　一個節點的後代數量 67

2.3.4　所有節點的後代數量 68

2.3.5　節點排序 68

2.3.6　輸出信息 69

2.3.7　main函數 70

2.4　小結 70

2.5　說明 71

第3章　記憶化與動態規劃 72

3.1　問題1：漢堡狂 72

3.1.1　題幹 72

3.1.2　制訂計劃 73

3.1.3　確定最優解的特征 74

3.1.4　解法1：遞歸 76

3.1.5　解法2：記憶化 80

3.1.6　解法3：動態規劃 85

3.2　記憶化與動態規劃的步驟 88

3.2.1　第 一步：最優解的結構 88

3.2.2　第二步：遞歸解 89

3.2.3　第三步：記憶化 89

3.2.4　第四步：動態規劃 90

3.3　問題2：精打細算 91

3.3.1　題幹 91

3.3.2　確定最優解的特征 92

3.3.3　解法1：遞歸 94

3.3.4　解法2：記憶化 99

3.4　問題3：冰球勁敵 101

3.4.1　題幹 101

3.4.2　關於勁敵 102

3.4.3　確定最優解的特征 104

3.4.4　解法1：遞歸 106

3.4.5　解法2：記憶化 109

3.4.6　解法3：動態規劃 110

3.4.7　空間優化 113

3.5　小結 114

3.6　說明 115

第4章　高級記憶化與動態規劃 116

4.1　問題1：跳一跳 116

4.1.1　題幹 116

4.1.2　示例解析 117

4.1.3　解法1：反向構造 119

4.1.4　解法2：正向構造 123

4.2　問題2：構建方式 127

4.2.1　題幹 127

4.2.2　示例解析 128

4.2.3　解法1：使用“恰好”子問題 129

4.2.4　解法2：引入更多子問題 134

4.3　小結 138

4.4　說明 138

第5章　圖與廣度優先搜索 139

5.1　問題1：騎士追擊 139

5.1.1　題幹 139

5.1.2　最優走法 141

5.1.3　騎士的最佳結果 148

5.1.4　騎士往返 150

5.1.5　時間優化 153

5.2　圖與BFS 154

5.2.1　圖是什麼 154

5.2.2　圖與樹 155

5.2.3　圖的BFS 157

5.2.4　圖與動態規劃 158

5.3　問題2：攀繩 158

5.3.1　題幹 158

5.3.2　解法1：尋找動作 159

5.3.3　解法2：重新建模 163

5.4　問題3：圖書翻譯 171

5.4.1　題幹 171

5.4.2　讀取語言名稱 172

5.4.3　構造圖 173

5.4.4　BFS 176

5.4.5　總成本 177

5.5　小結 178

5.6　說明 178

第6章　加權圖中的最短路徑 179

6.1　問題1：老鼠迷宮 179

6.1.1　題幹 179

6.1.2　從BFS出發 180

6.1.3　加權圖中的最短路徑 181

6.1.4　構造圖 185

6.1.5　實現Dijkstra算法 187

6.1.6　兩項優化 189

6.2　Dijkstra算法 190

6.2.1　Dijkstra算法的運行時間 191

6.2.2　負權邊 192

6.3　問題2：探親計劃 194

6.3.1　題幹 194

6.3.2　鄰接矩陣 195

6.3.3　構造圖 196

6.3.4　特殊路徑 197

6.3.5　任務1：最短路徑 200

6.3.6　任務2：最短路徑的數量 202

6.4　小結 208

6.5　說明 209

第7章　二分搜索 210

7.1　問題1：餵螞蟻 210

7.1.1　題幹 210

7.1.2　樹問題的變種 212

7.1.3　讀取輸入 213

7.1.4　可行性檢驗 215

7.1.5　搜索解 217

7.2　二分搜索概覽 218

7.2.1　二分搜索的運行時間 219

7.2.2　判斷可行性 220

7.2.3　搜索有序數組 220

7.3　問題2：河邊跳 220

7.3.1　題幹 221

7.3.2　貪心思想 221

7.3.3　可行性檢驗 223

7.3.4　搜索解 227

7.3.5　讀取輸入 230

7.4　問題3：生活質量 231

7.4.1　題幹 231

7.4.2　給每個矩形排序 232

7.4.3　使用二分搜索 235

7.4.4　可行性檢驗 236

7.4.5　更高效的可行性檢驗 237

7.5　問題4：洞穴之門 242

7.5.1　題幹 242

7.5.2　求解子問題 243

7.5.3　使用線性搜索 245

7.5.4　使用二分搜索 247

7.6　小結 249

7.7　說明 249

第8章　堆與線段樹 250

8.1　問題1：促銷活動 250

8.1.1　題幹 250

8.1.2　解法1：數組中的最大值與最小值 251

8.1.3　最大堆 254

8.1.4　最小堆 264

8.1.5　解法2：堆 266

8.2　堆 269

8.2.1　另外兩個應用場景 269

8.2.2　選擇數據結構 270

8.3　問題2：構造樹堆 270

8.3.1　題幹 271

8.3.2　遞歸輸出樹堆 272

8.3.3　按標簽排序 273

8.3.4　解法1：遞歸 274

8.3.5　區間最大值查詢 277

8.3.6　用線段樹處理區間查詢 278

8.3.7　解法2：線段樹 285

8.4　線段樹 286

8.5　問題3：兩數之和 287

8.5.1　題幹 287

8.5.2　填充線段樹 288

8.5.3　查詢線段樹 291

8.5.4　更新線段樹 293

8.5.5　main函數 295

8.6　小結 296

8.7　說明 296

第9章　並查集 297

9.1　問題1：社交網絡 297

9.1.1　題幹 297

9.1.2　建模為圖 298

9.1.3　解法1：BFS 302

9.1.4　並查集 305

9.1.5　解法2：並查集 308

9.1.6　優化1：按大小求並 312

9.1.7　優化2：路徑壓縮 315

9.2　並查集概覽 317

9.2.1　關系：三個條件 317

9.2.2　選擇並查集 318

9.2.3　優化 318

9.3　問題2：盟友和敵人 318

9.3.1　題幹 319

9.3.2　擴充並查集 320

9.3.3　main函數 323

9.3.4　查找與合並 325

9.3.5　SetFriends與SetEnemies 326

9.3.6　AreFriends與AreEnemies 327

9.4　問題3：收拾抽屜 328

9.4.1　題幹 328

9.4.2　等價的抽屜 329

9.4.3　main函數 334

9.4.4　查找與合並 336

9.5　小結 337

9.6　說明 337

第 10章　隨機化 338

10.1　問題1：羊羹 338

10.1.1　題幹 338

10.1.2　隨機選一塊 339

10.1.3　生成隨機數 341

10.1.4　確定塊數 342

10.1.5　猜口味 344

10.1.6　需要試幾次 346

10.1.7　填充口味數組 347

10.1.8　main函數 348

10.2　隨機化概覽 349

10.2.1　蒙特卡羅算法 349

10.2.2　拉斯維加斯算法 350

10.2.3　確定性算法與隨機化算法 351

10.3　問題2：瓶蓋和瓶子 351

10.3.1　題幹 351

10.3.2　求解子問題 352

10.3.3　解法1：遞歸 354

10.3.4　解法2：添加隨機化 358

10.4　快速排序 359

10.4.1　實現快速排序 359

10.4.2　最壞情況與預期運行時間 361

10.5　小結 363

10.6　說明 363

附錄A　算法運行時間 364

附錄B　未盡之言 369

附錄C　問題來源 385

後記 387