特殊数据结构题型：LRU、LFU、最小栈与最大队列
特殊数据结构题型：LRU、LFU、最小栈与最大队列 学完基础数据结构之后，很多人会发现一个现象：真正进阶的题目，往往不再直接问“什么是链表”“什么是栈”，而是会给出一个带约束的功能需求，让你设计一种支...
分类：数据结构
位图与布隆过滤器：空间效率与误判问题
位图与布隆过滤器：空间效率与误判问题 学数据结构时，很多时候我们关注的是：怎么更快。但到了实际工程里，另一个同样重要的问题经常会跳出来： 如果数据量极大，而我们只想做“是否存在”这种很粗粒度的判断，能...
跳表：多层索引结构的优雅实现
跳表：多层索引结构的优雅实现 学完 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 图算法学到这里，一个最自然、也最现实的问题就会出现： 从一个点到另一个点，怎么走代价最小？ 这里的“代价”可以是很多东西： 距离最...
最小生成树：Prim 与 Kruskal
最小生成树：Prim 与 Kruskal 在带权无向图里，有一类非常经典的问题： 如果要把所有顶点连起来，同时总代价尽可能小，应该怎么选边？ 这类问题在现实里非常常见。比如： 修建通信网络，希望总布线...