秒懂算法：用常识解读数据结构与算法_[美]杰伊·温格罗（Jay Wengrow）_9787115598134

本书是简单易懂的数据结构与算法入门书。作者略过复杂的数学公式，用“通俗讲解×逐步图示×代码实现”的方式介绍了数据结构与算法的基本概念，培养读者的算法思维。全书共有20章。读者将了解数据结构与算法为何如此重要，如何快速使用大O记法判断代码的运行效率，以及如何用动态规划优化算法。本书的重点内容包括冒泡排序、选择排序、插入排序等排序算法，以及深度优先搜索、广度优先搜索、迪杰斯特拉算法等图算法。在学习算法的过程中，读者也将通晓数组、哈希表、栈、队列、链表、图等常用数据结构的适用场景。

第 1 章数据结构为何重要 1 1.1 数据结构 2 1.2 数组：基础数据结构 3 1.3 速度计量 4 1.4 读取 4 1.5 查找 7 1.6 插入 9 1.7 删除 11 1.8 集合：差之毫厘，“慢”之千里 12 1.9 小结 15 习题 15 第 2 章算法为何重要 17 2.1 有序数组 18 2.2 有序数组的查找 20 2.3 二分查找 21 2.4 二分查找与线性查找 25 2.5 小结 27 习题 28 第 3 章哦！大O记法 29 3.1 大O：对N个元素来说需要多少步 29 3.2 大O的灵魂 30 3.2.1 深入大O的灵魂 32 3.2.2 同样的算法，不同的场景 32 3.3 第三类算法 33 3.4 对数 34 3.5 O(log N)的含义 34 3.6 实际例子 35 3.7 小结 36 习题 36 第 4 章使用大O给代码提速 38 4.1 冒泡排序 38 4.2 冒泡排序实战 39 4.3 冒泡排序的效率 44 4.4 平方问题 45 4.5 线性解法 47 4.6 小结 48 习题 49 第 5 章用或不用大O来优化代码 50 5.1 选择排序 50 5.2 选择排序实战 51 5.3 选择排序的效率 55 5.4 忽略常数 56 5.5 大O类别 57 5.5.1 实际例子 58 5.5.2 关键步骤 59 5.6 小结 59 习题 60 第 6 章根据情况进行优化 61 6.1 插入排序 61 6.2 插入排序实战 62 6.3 插入排序的效率 67 6.4 平均情况 68 6.5 实际例子 70 6.6 小结 72 习题 72 第 7 章日常代码中的大O 74 7.1 偶数平均数 74 7.2 构词程序 75 7.3 数组抽样 77 7.4 摄氏温度平均值 78 7.5 衣服标签 79 7.6 1的个数 80 7.7 回文检查 80 7.8 计算所有的积 81 7.9 密码破解程序 84 7.10 小结 86 习题 86 第 8 章查找迅速的哈希表 89 8.1 哈希表 89 8.2 用哈希函数进行哈希 90 8.3 好玩又赚钱的同义词典（赚钱是重点） 91 8.4 哈希表查找 92 8.5 解决冲突 94 8.6 创造高效的哈希表 96 8.7 用哈希表整合数据 98 8.8 用哈希表优化速度 99 8.9 小结 103 习题 103 第 9 章用栈和队列打造优雅的代码 104 9.1 栈 104 9.2 抽象数据类型 106 9.3 栈实战 107 9.4 受限数据结构的重要性 112 9.5 队列 113 9.6 队列实战 114 9.7 小结 116 习题 116 第 10 章用递归不停递归 117 10.1 用递归代替循环 117 10.2 基准情形 118 10.3 阅读递归代码 119 10.4 计算机眼中的递归 121 10.4.1 调用栈 121 10.4.2 栈溢出 123 10.5 文件系统遍历 123 10.6 小结 125 习题 125 第 11 章学习编写递归代码 127 11.1 递归类别：重复执行 127 11.2 递归类别：计算 130 11.3 自上而下递归：新的思维方式 132 11.3.1 自上而下的思考过程 133 11.3.2 数组的和 133 11.3.3 字符串倒序 134 11.3.4 x的个数 135 11.4 台阶问题 136 11.5 易位构词生成 139 11.6 小结 142 习题 143 第 12 章动态规划 144 12.1 不必要的递归调用 144 12.2 大O小改 147 12.3 递归的效率 148 12.4 重复子问题 149 12.5 动态规划与记忆化 150 12.6 自下而上的动态规划 153 12.6.1 自下而上的斐波那契函数 154 12.6.2 记忆化与自下而上 154 12.7 小结 155 习题 155 第 13 章飞快的递归算法 156 13.1 分区 156 13.2 快速排序 161 13.3 快速排序的效率 165 13.3.1 快速排序鸟瞰 166 13.3.2 快速排序的时间复杂度 167 13.4 最坏情况下的快速排序 169 13.5 快速选择 171 13.5.1 快速选择的效率 172 13.5.2 代码实现：快速选择 173 13.6 基于排序的其他算法 173 13.7 小结 175 习题 175 第 14 章基于节点的数据结构 176 14.1 链表 176 14.2 链表实现 177 14.3 读取 179 14.4 查找 180 14.5 插入 181 14.6 删除 185 14.7 链表操作的效率 187 14.8 链表实战 187 14.9 双链表 188 14.9.1 代码实现：双链表插入 189 14.9.2 前后移动 190 14.10 队列的双链表实现 190 14.11 小结 192 习题 192 第 15 章用二叉查找树加速万物 193 15.1 树 193 15.2 二叉查找树 195 15.3 查找 196 15.3.1 二叉查找树的查找效率 198 15.3.2 logN层 198 15.3.3 代码实现：二叉查找树查找 199 15.4 插入 200 15.4.1 代码实现：二叉查找树插入 202 15.4.2 插入顺序 203 15.5 删除 203 15.5.1 删除有两个子节点的节点 204 15.5.2 找到后继节点 205 15.5.3 有右子节点的后继节点 206 15.5.4 完整的删除算法 208 15.5.5 代码实现：二叉查找树删除 208 15.5.6 二叉查找树删除的效率 211 15.6 二叉查找树实战 211 15.7 二叉查找树遍历 212 15.8 小结 215 习题 216 第 16 章使用堆分清主次 217 16.1 优先队列 217 16.2 堆 218 16.2.1 堆条件 219 16.2.2 完全树 220 16.3 堆的性质 221 16.4 堆的插入 222 16.5 寻找尾节点 223 16.6 堆的删除 224 16.7 堆和有序数组 227 16.8 重新解决尾节点问题 228 16.9 用数组实现堆 230 16.9.1 遍历基于数组的堆 231 16.9.2 代码实现：堆插入 232 16.9.3 代码实现：堆删除 233 16.9.4 堆的其他实现方法 235 16.10 用堆实现优先队列 235 16.11 小结 236 习题 236 第 17 章字典树又何妨 237 17.1 字典树 237 17.1.1 字典树节点 238 17.1.2 Trie类 238 17.2 存储单词 239 17.3 字典树查找 241 17.4 字典树查找的效率 245 17.5 字典树插入 246 17.6 实现自动补全 249 17.6.1 收集所有单词 249 17.6.2 递归过程分析 251 17.7 完成自动补全功能 254 17.8 带有值的字典树：更好的自动补全 255 17.9 小结 256 习题 257 第 18 章连接万物的图 258 18.1 图 258 18.1.1 图和树 259 18.1.2 图的术语 259 18.1.3 图的基本实现 260 18.2 有向图 260 18.3 面向对象的图实现 261 18.4 图的搜索 262 18.5 深度优先搜索 264 18.5.1 深度优先搜索步骤详解 265 18.5.2 代码实现：深度优先搜索 271 18.6 广度优先搜索 272 18.6.1 广度优先搜索步骤详解 273 18.6.2 代码实现：广度优先搜索 280 18.6.3 对比广度优先搜索与深度优先搜索 281 18.7 图的搜索效率 283 18.8 加权图 285 18.8.1 加权图的代码实现 286 18.8.2 最短路径问题 287 18.9 迪杰斯特拉算法 288 18.9.1 迪杰斯特拉算法的准备工作 288 18.9.2 迪杰斯特拉算法的步骤 289 18.9.3 迪杰斯特拉算法详解 289 18.9.4 找到最短路径 295 18.9.5 代码实现：迪杰斯特拉算法 296 18.9.6 迪杰斯特拉算法的效率 301 18.10 小结 301 习题 302 第 19 章对付空间限制 304 19.1 空间复杂度的大O记法 304 19.2 时间和空间的取舍 306 19.3 递归的隐藏成本 308 19.4 小结 310 习题 310 第 20 章代码优化技巧 312 20.1 前置工作：确定目前的时间复杂度 312 20.2 从这里开始：最理想复杂度 312 20.3 魔法查找 313 20.3.1 魔法查找：查找作者 314 20.3.2 使用其他数据结构 315 20.3.3 两数之和问题 317 20.4 找规律 319 20.4.1 硬币游戏 319 20.4.2 举例法 320 20.4.3 交换和问题 321 20.5 贪心算法 325 20.5.1 数组最大值 326 20.5.2 最大子数组和 326 20.5.3 贪心的股价预测 331 20.6 更换数据结构 335 20.6.1 易位构词检查器 335 20.6.2 分组排序 338 20.7 小结 340 20.8 临别感言 340 习题 341 附录习题答案（图灵社区下载）

你还可能感兴趣

我要评论