算法问题实战策略PDF电子书下载

第一部分 开始解决问题 4

第1章 解决问题与程序设计竞赛 4

1.1 引言 4

1.2 程序设计竞赛 4

1.3 阅读本书的方法 7

1.4 值得参加的程序设计竞赛 8

1.5 对赛前准备工作的一些建议 9

1.6 续读 12

第2章 解决问题概述 13

2.1 引言 13

2.2 解决问题的过程 13

2.3 解决问题的策略 17

2.4 续读 26

第3章 编码与调试 27

3.1 引言：不要忽视编码的重要性 27

3.2 编写优秀代码的原则 27

3.3 常见失误 32

3.4 调试与测试 39

3.5 变量的取值范围 42

3.6 理解实数型数据类型 46

3.7 续读 55

第二部分 算法分析 60

第4章 分析算法的时间复杂度 60

4.1 引言 60

4.2 线性时间算法 62

4.3 次线性时间算法 65

4.4 指数时间算法 67

4.5 时间复杂度 70

4.6 推测执行时间 76

4.7 计算复杂度类：P、NP、NP-完备 81

4.8 续读 84

第5章 算法正确性证明 85

5.1 引言 85

5.2 数学归纳法和循环不变式 86

5.3 归谬法 90

5.4 其他技巧 92

5.5 续读 95

第三部分 算法设计范式 99

第6章 暴力解决法 99

6.1 引言 99

6.2 递归调用和穷举搜索法 100

6.3 练习题：郊游（习题ID：PICNIC，难度：低） 106

6.4 解题：郊游 107

6.5 练习题：盖游戏板（习题ID：BOARDCOVER，难度：低） 109

6.6 解题：盖游戏板 111

6.7 优化问题 113

6.8 练习题：时钟同步（习题ID：CLOCKSYNC，难度：中） 116

6.9 解题：时钟同步 117

6.10 常见穷举搜索类型 119

第7章 分治法 120

7.1 引言 120

7.2 练习题：四叉树问题（题目ID：QUADTREE，难度：低） 130

7.3 解题：四叉树问题 131

7.4 练习题：切割篱笆（习题ID：FENCE，难度：中） 134

7.5 解题：切割篱笆 135

7.6 练习题：粉丝见面会（题目ID：FANMEETING，难度：高） 139

7.7 解题：粉丝见面会 141

第8章 动态规划法 143

8.1 引言 143

8.2 练习题：通配符（习题ID：WILDCARD，难度：中） 151

8.3 解题：通配符 152

8.4 典型优化问题 156

8.5 练习题：合并LIS（题目ID：JLIS，难度：低） 163

8.6 解题：合并LIS 164

8.7 练习题：背诵圆周率（题目ID：PI，难度：低） 166

8.8 解题：背诵圆周率 167

8.9 练习题：Quantization（题目ID：QUANTIZE，难度：中） 169

8.10 解题：Quantization 170

8.11 所有可能的个数与概率 174

8.12 练习题：非对称铺设（题目ID：ASYMTILING，难度：低） 180

8.13 解题：非对称铺设 181

8.14 练习题：多联骨牌（题目ID：POLY，难度：中） 183

8.15 解题：多联骨牌 185

8.16 练习题：逃狱的韩尼拔博士（题目ID：NUMB3RS，难度：中） 187

8.17 解题：逃狱的韩尼拔博士 189

第9章 动态规划技巧 194

9.1 计算优化问题的实际答案 194

9.2 练习题：打包行李（题目ID：PACKING，难度：中） 195

9.3 解题：打包行李 197

9.4 练习题：光学字符识别（题目ID：OCR，难度：高） 199

9.5 解题：光学字符识别 201

9.6 计算第k个答案 204

9.7 练习题：第k个最大递增子序列（题目ID：KLIS，难度：高） 209

9.8 解题：第k个最长递增子序列 210

9.9 练习题：龙曲线（题目ID：DRAGON，难度：中） 214

9.10 解题：龙曲线 216

9.11 对非整数型输入的制表 219

9.12 练习题：韦布巴津（题目ID：ZIMBABWE，难度：高） 224

9.13 解题：韦布巴津 225

9.14 练习题：恢复实验数据（题目ID：RESTORE，难度：中） 230

9.15 解题：恢复实验数据 231

9.16 组合游戏 234

9.17 练习题：数字游戏（题目ID：NUMBERGAME，难度：低） 239

9.18 解题：数字游戏 240

9.19 练习题：方块游戏（题目ID：BLOCKGAME，难度：中） 242

9.20 解题：方块游戏 243

9.21 迭代动态规划法 245

9.22 练习题：回转寿司（题目ID：SUSHI，难度：中） 249

9.23 解题：回转寿司 250

9.24 练习题：Genius（题目ID：GENIUS，难度：中） 253

9.25 解题：Genius 254

9.26 续读 256

第10章 贪心法 257

10.1 引言 257

10.2 练习题：加热便当（题目ID：LUNCHBOX，难度：低） 264

10.3 解题：加热便当 265

10.4 练习题：合并字符串（题目ID：STRJOIN，难度：中） 268

10.5 解题：合并字符串 269

10.6 练习题：米那斯雅诺（题目ID：MINASTIRITH，难度：高） 273

10.7 解题：米那斯雅诺 275

第11章 组合搜索 281

11.1 引言 281

11.2 组合搜索的方法 283

11.3 练习题：盖游戏板2（题目ID：BOARDCOVER2，难度：低） 298

11.4 解题：盖游戏板2 299

11.5 练习题：患有严重过敏症的朋友们（题目ID：ALLERGY，难度：中） 303

11.6 解题：患有严重过敏症的朋友们 304

11.7 练习题：数谜（题目ID：KAKURO2，难度：中） 307

11.8 解题：数谜 309

11.9 续读 315

第12章 将优化问题转换为决策 问题求解 316

12.1 引言 316

12.2 练习题：南极基地（题目ID：ARCTIC，难度：低） 320

12.3 解题：南极基地 321

12.4 练习题：加拿大旅行（题目ID：CANADATRIP，难度：中） 323

12.5 解题：加拿大旅行 324

12.6 练习题：退选课程（题目ID：WITHDRAWAL，难度：高） 326

12.7 解题：退选课程 327

第四部分 一些著名的算法 331

第13章 数值分析 331

13.1 引言 331

13.2 二分法 331

13.3 练习题：提高获胜率（题目ID：RATIO，难度：低） 338

13.4 解题：提高获胜率 339

13.5 三叉搜索 341

13.6 练习题：花粉化石（题目ID：FOSSIL，难度：高） 346

13.7 解题：花粉化石 347

13.8 其他主题 351

第14章 整数论 352

14.1 引言 352

14.2 素数 352

14.3 练习题：密码486（题目ID：PASS486，难度：中） 357

14.4 解题：密码486 357

14.5 欧几里得算法 360

14.6 练习题：魔法药水（题目ID：POTION，难度：中） 361

14.7 解题：魔法药水 362

14.8 模运算 364

14.9 续读 366

第15章 计算几何 367

15.1 引言 367

15.2 计算几何的工具 367

15.3 相交、距离、面积 373

15.4 练习题：弹球模拟（题目ID：PINBALL，难度：高） 377

15.5 解题：弹球模拟 379

15.6 多边形 383

15.7 练习题：金银岛（题目ID：TREASURE，难度：高） 386

15.8 解题：金银岛 387

15.9 练习题：是呆子？不是呆子？（题目ID：NERDS，难度：中） 390

15.10 解题：是呆子？不是呆子？ 392

15.11 计算几何算法设计范式 396

15.12 常见失误与注意事项 403

15.13 续读 404

第五部分 基本数据结构 410

第16章 位掩码 410

16.1 引言 410

16.2 利用位掩码实现集合 413

16.3 位掩码应用示例 417

16.4 练习题：毕业学期（题目ID：GRADUATION，难度：中） 420

16.5 解题：毕业学期 422

16.6 续读 424

第17章 部分和 425

17.1 引言 425

17.2 练习题：圣诞娃娃（题目ID：CHRISTMAS，难度：中） 429

17.3 解题：圣诞娃娃 430

17.4 其他学习内容 432

第18章 线性数据结构 433

18.1 引言 433

18.2 动态数组 433

18.3 链表 437

18.4 动态数组和链表的比较 440

18.5 练习题：约瑟夫斯（题目ID：JOSEPHUS，难度：低） 440

18.6 解题：约瑟夫斯 441

18.7 续读 442

第19章 队列、栈以及双端队列 443

19.1 引言 443

19.2 队列、栈以及双端队列的实现方法 444

19.3 队列与栈的应用 445

19.4 练习题：不匹配括号（题目ID：BRACKETS2，难度：低） 448

19.5 解题：不匹配括号 449

19.6 练习题：分析外星信号（题目ID：ITES，难度：中） 450

19.7 解题：分析外星信号 451

第20章 字符串 455

20.1 引言 455

20.2 字符串检索 456

20.3 练习题：宰河的保险箱（题目ID：JAEHASAFE，难度：中） 466

20.4 解题：宰河的保险箱 467

20.5 后缀数组 468

20.6 练习题：口头禅（题目ID：HABIT，难度：中） 476

20.7 解题：口头禅 477

20.8 续读 478

第六部分 树 481

第21章 树的实现与遍历 481

21.1 引言 481

21.2 树的遍历 483

21.3 练习题：变更树的遍历顺序（题目ID：TRAVERSAL，难度：低） 484

21.4 解题：变更树的遍历顺序 486

21.5 练习题：要塞（题目ID：FORTRESS，难度：中） 487

21.6 解题：要塞 488

第22章 二叉搜索树 493

22.1 引言 493

22.2 二叉搜索树的定义和操作 493

22.3 时间复杂度分析与平衡二叉搜索树 496

22.4 练习题：是呆子？不是呆子？2（题目ID：NERD2，难度：中） 496

22.5 解题：是呆子？不是呆子？2 498

22.6 直接实现平衡二叉搜索树：树堆 501

22.7 练习题：反转插入排序（题目ID：INSERTION，难度：中） 508

22.8 解题：反转插入排序 509

第23章 优先级队列和堆 511

23.1 引言 511

23.2 堆的定义与实现方法 512

23.3 练习题：变化的中间值（题目ID：RUNNINGMEDIAN，难度：低） 518

23.4 解题：变化的中间值 519

第24章 区间树 521

24.1 区间树：区间相关问题解答 521

24.2 练习题：登山路（题目ID：MORDDR，难度：中） 527

24.3 解题：登山路 528

24.4 练习题：寻根问祖（题目ID：FAMILYTREE，难度：高） 529

24.5 解题：寻根问祖 530

24.6 树状数组：快速而简单的区间和 533

24.7 练习题：计算插入排序的时间（题目ID：MEASURETIME，难度：中） 536

24.8 解题：计算插入排序的时间 537

第25章 互斥集合 541

25.1 引言 541

25.2 练习题：编辑器之争（题目ID：EDITORWARS，难度：中） 546

25.3 解题：编辑器之争 548

第26章 字典树 553

26.1 引言 553

26.2 练习题：再见，谢谢所有的鱼（题目ID：SOLONG，难度：中） 557

26.3 解题：再见，谢谢所有的鱼 559

26.4 利用字典树检索多重字符串 563

26.5 练习题：安全终结者（题目ID：NH，难度：高） 569

26.6 解题：安全终结者 570

第七部分 图 576

第27章 图的表示方式及定义 576

27.1 引言 576

27.2 图的应用示例 579

27.3 隐式图结构 580

27.4 图的几种表示法 581

第28章 图的深度优先搜索 585

28.1 引言 585

28.2 练习题：古语词典（习题ID：DICTIONARY，难度：低） 590

28.3 解题：古语词典 591

28.4 欧拉回路 594

28.5 练习题：有限单词接龙（题目ID：WORDCHAIN，难度：低） 597

28.6 解题：有限单词接龙 598

28.7 理论背景及应用 602

28.8 练习题：安装监控摄像头（题目ID：GALLERY，难度：中） 613

28.9 解题：安装监控摄像头 614

28.10 练习题：安排会议室（题目ID：MEETINGROOM，难度：高） 616

28.11 解题：安排会议室 618

第29章 图的宽度优先搜索 625

29.1 引言 625

29.2 练习题：排序游戏（题目ID：SORTGAME，难度：中） 629

29.3 解题：排序游戏 630

29.4 练习题：儿童节（题目ID：CHILDRENDAY，难度：高） 633

29.5 解题：儿童节 634

29.6 最短路径策略 637

29.7 练习题：汉诺塔（题目ID：HANOI4B，难度：中） 648

29.8 解题：汉诺塔 650

第30章 最短路径问题 653

30.1 引言 653

30.2 迪杰斯特拉最短路径算法 654

30.3 练习题：信号路由（题目ID：ROUTING，难度：低） 661

30.4 解题：信号路由 662

30.5 练习题：消防车（题目ID：FIRETRUCKS，难度：中） 663

30.6 解题：消防车 664

30.7 练习题：铁人N项比赛（题目ID：NTHLON，难度：高） 665

30.8 解题：铁人N项比赛 667

30.9 贝尔曼-福特最短路径算法 669

30.10 练习题：时间旅行（题目ID：TIMETRIP，难度：中） 674

30.11 解题：时间旅行 675

30.12 弗洛伊德多源最短路径算法 677

30.13 练习题：检查酒驾（题目ID：DRUNKEN，难度：中） 682

30.14 解题：检查酒驾 684

30.15 练习题：竞选承诺（题目ID：PROMISES，难度：中） 685

30.16 解题：竞选承诺 687

第31章 最小生成树 689

31.1 引言 689

31.2 克鲁斯克尔最小生成树算法 690

31.3 普里姆最小生成树算法 694

31.4 练习题：局域网（题目ID：LAN，难度：低） 697

31.5 解题：局域网 698

31.6 练习题：选定旅行路线（题目ID：TPATH，难度：高） 699

31.7 解题：选定旅行路线 700

第32章 网络流 705

32.1 引言 705

32.2 福特-富尔克森算法 706

32.3 网络建模 713

32.4 练习题：操纵比赛（题目ID：MATCHFIX，难度：中） 715

32.5 解题：操纵比赛 717

32.6 练习题：国家项目（题目ID：PROJECTS，难度：高） 719

32.7 解题：国家项目 720

32.8 二分图匹配 723

32.9 练习题：象（题目ID：BISHOPS，难度：中） 729

32.10 解题：象 730

32.11 练习题：设置陷阱（题目ID：TRAPCARD，难度：高） 732

32.12 解题：设置陷阱 734

32.13 其他学习内容 737