[
-
内容大纲
本书精选IOI、NOIP、USACO、CCC、CCO、ICPC、DWITE等竞赛中28个富有趣味与挑战性的算法竞赛题，采用“问题描述–输入–输出–解决方案”的结构，引导读者在实战中培养算法思维，牢固掌握数据结构与算法的核心知识。全书共分10章，涵盖哈希表、树与递归、记忆化与动态规划、图与广度优先搜索、加权图中的最短路径、二分搜索、堆与线段树、并查集以及随机化算法等主题。所有示例均用C语言实现，但无论你使用C++、Java还是Python，都能轻松理解并迁移所学思想与方法。 -
作者介绍
丹尼尔·津加罗（Daniel Zingaro）博士是多伦多大学密西沙加分校计算机科学教学流中的获奖副教授，他在主动学习方面的专长得到了国际认可。他也是《算法思维》（No Starch Press）的作者。 -
目录
第1章 哈希表
1.1 问题1：独特的雪花
1.1.1 题干
1.1.2 简化问题
1.1.3 解决核心问题
1.1.4 解法1：成对比较
1.1.5 解法2：减少工作量
1.2 哈希表概览
1.2.1 设计哈希表
1.2.2 为什么使用哈希表
1.3 问题2：登录风波
1.3.1 题干
1.3.2 解法1：遍历所有密码
1.3.3 解法2：使用哈希表
1.4 问题3：拼写检查
1.4.1 题干
1.4.2 考虑哈希表
1.4.3 临时解决方案
1.5 小结
1.6 说明
第2章 树与递归
2.1 问题1：万圣节扫荡
2.1.1 题干
2.1.2 二叉树
2.1.3 求解用例
2.1.4 二叉树的表示
2.1.5 收集所有糖果
2.1.6 一个完全不同的解法
2.1.7 最小遍历街道数
2.1.8 读取输入
2.2 为什么使用递归
2.3 问题2：后代距离
2.3.1 题干
2.3.2 读取输入
2.3.3 一个节点的后代数量
2.3.4 所有节点的后代数量
2.3.5 节点排序
2.3.6 输出信息
2.3.7 main函数
2.4 小结
2.5 说明
第3章 记忆化与动态规划
3.1 问题1：汉堡狂
3.1.1 题干
3.1.2 制订计划
3.1.3 确定最优解的特征
3.1.4 解法1：递归
3.1.5 解法2：记忆化
3.1.6 解法3：动态规划
3.2 记忆化与动态规划的步骤
3.2.1 第一步：最优解的结构
3.2.2 第二步：递归解
3.2.3 第三步：记忆化
3.2.4 第四步：动态规划
3.3 问题2：精打细算
3.3.1 题干
3.3.2 确定最优解的特征
3.3.3 解法1：递归
3.3.4 解法2：记忆化
3.4 问题3：冰球劲敌
3.4.1 题干
3.4.2 关于劲敌
3.4.3 确定最优解的特征
3.4.4 解法1：递归
3.4.5 解法2：记忆化
3.4.6 解法3：动态规划
3.4.7 空间优化
3.5 小结
3.6 说明
第4章 高级记忆化与动态规划
4.1 问题1：跳一跳
4.1.1 题干
4.1.2 示例解析
4.1.3 解法1：反向构造
4.1.4 解法2：正向构造
4.2 问题2：构建方式
4.2.1 题干
4.2.2 示例解析
4.2.3 解法1：使用“恰好”子问题
4.2.4 解法2：引入更多子问题
4.3 小结
4.4 说明
第5章 图与广度优先搜索
5.1 问题1：骑士追击
5.1.1 题干
5.1.2 最优走法
5.1.3 骑士的最佳结果
5.1.4 骑士往返
5.1.5 时间优化
5.2 图与BFS
5.2.1 图是什么
5.2.2 图与树
5.2.3 图的BFS
5.2.4 图与动态规划
5.3 问题2：攀绳
5.3.1 题干
5.3.2 解法1：寻找动作
5.3.3 解法2：重新建模
5.4 问题3：图书翻译
5.4.1 题干
5.4.2 读取语言名称
5.4.3 构造图
5.4.4 BFS
5.4.5 总成本
5.5 小结
5.6 说明
第6章 加权图中的最短路径
6.1 问题1：老鼠迷宫
6.1.1 题干
6.1.2 从BFS出发
6.1.3 加权图中的最短路径
6.1.4 构造图
6.1.5 实现Dijkstra算法
6.1.6 两项优化
6.2 Dijkstra算法
6.2.1 Dijkstra算法的运行时间
6.2.2 负权边
6.3 问题2：探亲计划
6.3.1 题干
6.3.2 邻接矩阵
6.3.3 构造图
6.3.4 特殊路径
6.3.5 任务1：最短路径
6.3.6 任务2：最短路径的数量
6.4 小结
6.5 说明
第7章 二分搜索
7.1 问题1：喂蚂蚁
7.1.1 题干
7.1.2 树问题的变种
7.1.3 读取输入
7.1.4 可行性检验
7.1.5 搜索解
7.2 二分搜索概览
7.2.1 二分搜索的运行时间
7.2.2 判断可行性
7.2.3 搜索有序数组
7.3 问题2：河边跳
7.3.1 题干
7.3.2 贪心思想
7.3.3 可行性检验
7.3.4 搜索解
7.3.5 读取输入
7.4 问题3：生活质量
7.4.1 题干
7.4.2 给每个矩形排序
7.4.3 使用二分搜索
7.4.4 可行性检验
7.4.5 更高效的可行性检验
7.5 问题4：洞穴之门
7.5.1 题干
7.5.2 求解子问题
7.5.3 使用线性搜索
7.5.4 使用二分搜索
7.6 小结
7.7 说明
第8章 堆与线段树
8.1 问题1：促销活动
8.1.1 题干
8.1.2 解法1：数组中的最大值与最小值
8.1.3 最大堆
8.1.4 最小堆
8.1.5 解法2：堆
8.2 堆
8.2.1 另外两个应用场景
8.2.2 选择数据结构
8.3 问题2：构造树堆
8.3.1 题干
8.3.2 递归输出树堆
8.3.3 按标签排序
8.3.4 解法1：递归
8.3.5 区间最大值查询
8.3.6 用线段树处理区间查询
8.3.7 解法2：线段树
8.4 线段树
8.5 问题3：两数之和
8.5.1 题干
8.5.2 填充线段树
8.5.3 查询线段树
8.5.4 更新线段树
8.5.5 main函数
8.6 小结
8.7 说明
第9章 并查集
9.1 问题1：社交网络
9.1.1 题干
9.1.2 建模为图
9.1.3 解法1：BFS
9.1.4 并查集
9.1.5 解法2：并查集
9.1.6 优化1：按大小求并
9.1.7 优化2：路径压缩
9.2 并查集概览
9.2.1 关系：三个条件
9.2.2 选择并查集
9.2.3 优化
9.3 问题2：盟友和敌人
9.3.1 题干
9.3.2 扩充并查集
9.3.3 main函数
9.3.4 查找与合并
9.3.5 SetFriends与SetEnemies
9.3.6 AreFriends与AreEnemies
9.4 问题3：收拾抽屉
9.4.1 题干
9.4.2 等价的抽屉
9.4.3 main函数
9.4.4 查找与合并
9.5 小结
9.6 说明
第10章 随机化
10.1 问题1：羊羹
10.1.1 题干
10.1.2 随机选一块
10.1.3 生成随机数
10.1.4 确定块数
10.1.5 猜口味
10.1.6 需要试几次
10.1.7 填充口味数组
10.1.8 main函数
10.2 随机化概览
10.2.1 蒙特卡罗算法
10.2.2 拉斯维加斯算法
10.2.3 确定性算法与随机化算法
10.3 问题2：瓶盖和瓶子
10.3.1 题干
10.3.2 求解子问题
10.3.3 解法1：递归
10.3.4 解法2：添加随机化
10.4 快速排序
10.4.1 实现快速排序
10.4.2 最坏情况与预期运行时间
10.5 小结
10.6 说明
附录A 算法运行时间
附录B 未尽之言
附录C 问题来源
后记
同类热销排行榜
- C语言与程序设计教程(高等学校计算机类十二五规划教材)16
- 电机与拖动基础(教育部高等学校自动化专业教学指导分委员会规划工程应用型自动化专业系列教材)13.48
- 传感器与检测技术(第2版高职高专电子信息类系列教材)13.6
- ASP.NET项目开发实战(高职高专计算机项目任务驱动模式教材)15.2
- Access数据库实用教程(第2版十二五职业教育国家规划教材)14.72
- 信号与系统(第3版下普通高等教育九五国家级重点教材)15.08
- 电气控制与PLC(普通高等教育十二五电气信息类规划教材)17.2
- 数字电子技术基础(第2版)17.36
- VB程序设计及应用(第3版十二五职业教育国家规划教材)14.32
- Java Web从入门到精通(附光盘)/软件开发视频大讲堂27.92
推荐书目
-
孩子你慢慢来/人生三书 华人世界率性犀利的一枝笔，龙应台独家授权《孩子你慢慢来》20周年经典新版。她的《...
-
时间简史(插图版) 相对论、黑洞、弯曲空间……这些词给我们的感觉是艰深、晦涩、难以理解而且与我们的...
-
本质(精) 改革开放40年，恰如一部四部曲的年代大戏。技术突变、产品迭代、产业升级、资本对接...