算法训练营:海量图解+竞赛刷题(入门篇)

第1章 语言基础... 1

1.1 开启算法之旅：hello world! 1

1.2 常见数据类型及其表达范围... 2

1.3 玩转输入输出... 2

1.4 人生就是不断地选择：if…else. 9

1.5 每天都有很多次重复：for/while. 13

1.6 如何轻松写一个函数... 20

1.7 从前有座山，山里有座庙：递归之法... 25

1.8 信息携带者：定义一个结构体... 29

1.9 巧用数组——好玩贪吃蛇... 31

1.10 玩转字符串——不一样的风格... 37

第2章 算法入门... 42

2.1 算法之美... 42

2.1.1 如何评价一个算法的优劣... 42

2.1.2 算法复杂度的计算方法... 45

2.2 贪心算法... 48

2.2.1 贪心本质... 48

2.2.2 *优装载问题... 49

2.3 分治算法... 51

2.3.1 分治算法秘籍... 51

2.3.2 合并排序... 51

2.3.3 快速排序... 57

2.4 STL应用... 65

2.4.1 vector 65

训练 间谍... 67

2.4.2 栈... 68

训练 Web导航... 69

2.4.3 queue. 75

训练 骑士移动... 75

2.4.4 list 77

训练 士兵队列训练... 78

2.4.5 deque. 79

训练 度度熊学队列... 80

2.4.6 priority_queue. 82

训练 黑盒子... 83

2.4.7 bitset 85

训练 集合运算... 88

2.4.8 set/multiset 90

训练1 集合合并... 91

训练2 并行处理... 92

2.4.9 map/multimap. 94

训练1 硬木种类... 96

训练2 双重队列... 97

训练3 水果... 99

2.4.10 STL的常用函数... 100

训练1 差的中位数... 106

训练2 中位数... 108

训练3 订单管理... 109

训练4 字谜... 110

第3章 线性表的应用... 112

3.1 顺序表... 112

3.2 单链表... 116

3.3 双向链表... 119

3.4 循环链表... 122

3.5 静态链表... 123

训练1 区块世界... 126

训练2 悲剧文本... 132

训练3 移动盒子... 133

第4章 栈和队列的应用... 140

4.1 顺序栈... 140

4.2 链栈... 143

4.3 顺序队列... 146

4.4 链队列... 155

训练1 括号匹配... 158

训练2 铁轨... 160

训练3 矩阵连乘... 164

训练4 打印队列... 168

训练5 并发模拟器... 171

第5章 树的应用... 187

5.1 树... 187

5.1.1 树的存储... 190

5.1.2 树、森林与二叉树的转换... 193

5.2 二叉树... 194

5.2.1 二叉树的性质... 195

5.2.2 二叉树的存储结构... 200

5.2.3 二叉树的创建... 202

5.3 二叉树遍历... 210

5.3.1 先序遍历... 210

5.3.2 中序遍历... 214

5.3.3 后序遍历... 217

5.3.4 层次遍历... 221

5.3.5 遍历序列还原树... 224

训练1 新二叉树... 228

训练2 还原树... 229

训练3 树... 230

5.4 哈夫曼树... 232

原理 哈夫曼编码... 232

训练1 围栏修复... 245

训练2 信息熵... 246

训练3 转换哈夫曼编码... 248

训练4 可变基哈夫曼编码... 251

第6章 图论基础... 256

6.1 图的存储... 257

6.1.1 邻接矩阵... 257

6.1.2 边集数组... 263

6.1.3 邻接表... 263

6.1.4 链式前向星... 271

训练1 *大的节点... 274

训练2 有向图D和E. 276

训练3 奶牛排序... 278

6.2 图的遍历... 279

6.2.1 广度优先遍历... 279

6.2.2 深度优先遍历... 283

训练1 油田... 287

训练2 理想路径... 290

训练3 骑士的旅程... 293

训练4 抓住那头牛... 295

6.3 图的连通性... 298

6.3.1 连通性的相关知识... 298

6.3.2 Tarjan算法... 302

训练1 电话网络... 306

训练2 道路建设... 308

训练3 图的底部... 311

训练4 校园网络... 313

第7章 图的应用... 316

7.1 *短路径... 316

7.1.1 Dijkstra算法... 316

7.1.2 Floyd算法... 322

7.1.3 Bellman-Ford算法... 326

7.1.4 SPFA算法... 328

训练1 重型运输... 329

训练2 货币兑换... 331

训练3 虫洞... 332

训练4 *短路径... 335

7.2 *小生成树... 336

7.2.1 Prim算法... 337

7.2.2 Kruskal算法... 346

训练1 丛林之路... 351

训练2 联网... 352

训练3 空间站... 354

训练4 道路建设... 356

7.3 拓扑排序... 358

原理 拓扑排序... 358

训练1 家族树... 362

训练2 全排序... 364

训练3 标签球... 366

训练4 秩序... 369

7.4 关键路径... 371

原理 关键路径... 371

训练1 关键路径... 380

训练2 指令安排... 382

训练3 家务琐事... 384

训练4 免费DIY之旅... 385

训练5 游戏玩家... 388

第8章 查找算法... 391

8.1 哈希表... 391

8.1.1 散列函数... 392

8.1.2 处理冲突的方法... 394

8.1.3 散列查找及性能分析... 404

训练1 雪花... 406

训练2 公式... 407

训练3 正方形... 409

8.2 字符串模式匹配... 411

8.2.1 BF算法... 412

8.2.2 KMP算法... 415

训练1 统计单词数... 421

训练2 KMP字符串匹配... 423

8.3 二叉查找树... 424

原理 二叉查找树详解... 424

训练1 落叶... 436

训练2 完全二叉搜索树... 439

训练3 硬木种类... 441

训练4 二叉搜索树... 442

8.4 平衡二叉树... 444

原理 AVL树详解... 445

训练1 平衡二叉树... 458

训练2 双重队列... 461

训练3 黑盒子... 464

训练4 硬木种类... 465

第9章 搜索技术... 466

9.1 二分搜索... 466

原理 二分搜索技术... 466

训练1 跳房子游戏... 471

训练2 烘干衣服... 475

训练3 花环... 477

训练4 电缆切割... 479

9.2 深度优先搜索... 480

9.2.1 回溯法... 480

9.2.2 子集树... 483

9.2.3 m叉树... 491

9.2.4 排列树... 499

训练1 魅力手镯... 515

训练2 图的m着色问题... 516

训练3 N皇后问题... 517

9.2.5 DFS+剪枝优化... 517

训练1 数独游戏... 518

训练2 生日蛋糕... 521

训练3 木棒... 522

9.3 广度优先搜索... 524

9.3.1 分支限界法... 525

9.3.2 队列式广度优先搜索.... 525

9.3.3 优先队列式广度优先搜索... 535

训练1 迷宫问题... 541

训练2 加满油箱... 542

9.3.4 嵌套广度优先搜索... 545

训练 推箱子... 545

9.3.5 双向广度优先搜索... 549

训练 魔鬼Ⅱ... 549

9.4 启发式搜索... 551

9.4.1 A*算法... 552

9.4.2 IDA*算法... 552

训练1 八数码... 552

训练2 八数码II 562

训练3 第K短路... 565

训练4 幂运算... 567