区间类结构基础：前缀和与差分
区间类结构基础：前缀和与差分 学到这里，很多数据结构都在围绕“单点操作”展开：查一个值、插一个点、删一个节点、维护一个最值。但在很多实际问题里，我们关心的并不是单个位置，而是一整段区间。例如： 某个区间的元素和是多少； 某一段范围需要统一加...
特殊数据结构题型：LRU、LFU、最小栈与最大队列
特殊数据结构题型：LRU、LFU、最小栈与最大队列 学完基础数据结构之后，很多人会发现一个现象：真正进阶的题目，往往不再直接问“什么是链表”“什么是栈”，而是会给出一个带约束的功能需求，让你设计一种支持特定操作的数据结构。例如： 要求 O(...
位图与布隆过滤器：空间效率与误判问题
位图与布隆过滤器：空间效率与误判问题 学数据结构时，很多时候我们关注的是：怎么更快。但到了实际工程里，另一个同样重要的问题经常会跳出来： 如果数据量极大，而我们只想做“是否存在”这种很粗粒度的判断，能不能用更少空间？ 位图和布隆过滤器，就是...
跳表：多层索引结构的优雅实现
跳表：多层索引结构的优雅实现 学完 BST、AVL、红黑树和 B+ 树之后，你会很自然地觉得：如果要做有序查找结构，好像就该在“平衡树家族”里选一个。但跳表的出现告诉我们： 想要接近平衡树的查找效率，并不一定非要靠复杂旋转和严格结构维护，也...
字符串匹配进阶：BM、Sunday 与 Rabin-Karp
字符串匹配进阶：BM、Sunday 与 Rabin-Karp 学完朴素匹配和 KMP 之后，很容易产生一个问题：字符串匹配是不是就到此为止了？其实远远没有。KMP 很经典，但它并不是唯一重要的匹配思路。特别是在工程实践和不同输入分布下，人们...
字符串匹配基础：朴素匹配与 KMP
字符串匹配基础：朴素匹配与 KMP 学字符串时，我们已经提到过一个非常核心的问题： 在一个主串中，如何高效找到某个模式串出现的位置？ 这个问题看起来简单，但实际上几乎贯穿了所有文本处理系统： 编辑器搜索； 日志关键字定位； 编译器词法处理；...
哈希表：哈希函数、冲突处理与装载因子
哈希表：哈希函数、冲突处理与装载因子 如果说折半查找是“利用有序性”来加速查找，那么哈希表代表的则是另一条完全不同的路线： 我不按大小比较，也不沿树路径逐步缩小范围，而是想办法把键直接映射到一个位置上，争取一次就找到。 这正是哈希表最吸引人...
查找基础：顺序查找、折半查找与分块查找
查找基础：顺序查找、折半查找与分块查找 学完树和图之后，再回头看“查找”这个主题，会发现它其实一直贯穿在整个数据结构学习里。顺序表在查找，BST 在查找，哈希表在查找，B+ 树本质上也在查找。只不过不同结构对查找做了不同层次的优化。而在正式...
关键路径：工程调度中的图模型
关键路径：工程调度中的图模型 前面讲拓扑排序时，我们已经看到：有向无环图很适合表达“谁必须先于谁”的依赖关系。但在真实工程里，仅仅知道先后顺序还不够，很多时候我们更关心另一个问题： 整个工程最早什么时候能完成？哪些任务一旦拖延，就会直接拖慢...
最短路径：Dijkstra、Bellman-Ford 与 Floyd
最短路径：Dijkstra、Bellman-Ford 与 Floyd 图算法学到这里，一个最自然、也最现实的问题就会出现： 从一个点到另一个点，怎么走代价最小？ 这里的“代价”可以是很多东西： 距离最短； 时间最少； 花费最低； 风险最小；...