加载中…
137 篇教程 · 系统学习算法与数据结构的原理与实现
堆排序（Heap Sort）是利用堆这种数据结构设计的排序算法。它是选择排序的改进版，通过维护最大堆（或最小堆）逐步取出极值，实现 O(n log n) 的原地...
基于比较的排序（快排、归并、堆排）有一个理论下界：Ω(n log n)。
归并排序（Merge Sort）是一种基于分治思想的高效排序算法。其核心思想包括以下几个步骤：
虽然工程中很少直接使用 O(n²) 排序，但它们是：
快速排序（Quick Sort）是一种高效的排序算法，由托尼·霍尔（Tony Hoare）于1960年提出。它基于分治法（Divide and Conquer）...
本篇对所有主流排序算法进行横向对比，帮助你在面试中快速选择正确的排序策略。
希尔排序（Shell Sort）是插入排序的改进版本，也称为缩小增量排序。它通过将数组分割成若干子序列进行插入排序，逐步缩小间隔，最终完成全局有序。由 Dona...
二分答案不是在一个数组里找某个值，而是在答案的可能范围内二分，通过一个验证函数（check）判断当前猜测是否可行，从而逐步缩小答案范围。
二分查找（Binary Search） 是一种在有序数组中查找目标元素的搜索算法。它通过每一步将搜索区间缩小一半，达到 O(log n) 的时间复杂度。
二分答案是一种将"求最优值"问题转化为"判定可行性"问题的通用技巧。只要答案具有单调性（满足/不满足某条件），就可以用二分将 O(n) 的搜索优化为 O(log...
线性查找（Linear Search）是最基础的搜索算法，也是理解所有高级搜索策略的起点。本篇从线性查找出发，梳理搜索算法的完整谱系。
倍增法（Binary Lifting）通过预处理每个节点的 2^k 级祖先，实现 O(log n) 查询任意两节点的最近公共祖先（LCA），是树上查询的基础工具...
并查集（Disjoint Set Union，简称 DSU）是一种用于处理不相交集合的合并与查询问题的数据结构。
并查集在基础的合并与查询之上，还可以扩展为带权并查集（维护节点间关系）、可撤销并查集（支持回退）和按秩合并优化。本篇覆盖进阶用法与经典应用。
graph LR
单调栈在基础应用（下一个更大元素）之上，还能解决柱状图最大矩形、接雨水、股票价格跨度等经典问题。本篇聚焦单调栈的进阶应用与思维模式。
单调栈是栈内元素保持单调递增或单调递减的栈结构。
堆（Heap） 是一种特殊的完全二叉树，满足堆序性：
队列（Queue） 是一种先进先出（FIFO, First In First Out） 的线性数据结构。
二叉树（Binary Tree） 是计算机科学中一种基本而重要的数据结构，由节点（Node）组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。
二叉树遍历是树形结构的基础操作，前序、中序、后序、层序四种遍历方式各有用途。掌握递归与迭代两种实现，是解决所有树形问题的起点。
二分搜索树（Binary Search Tree，BST） 是满足以下性质的二叉树：
graph LR
分块（Sqrt Decomposition）是一种"暴力美学"——将数据分成 √n 大小的块，整块预处理、零散暴力，实现 O(√n) 的查询与修改。莫队算法则是...
哈希表（Hash Table） 是一种通过哈希函数将键（Key）映射到值（Value）的数据结构，提供 O(1) 平均时间复杂度的查找、插入和删除操作。
哈希表的核心在于哈希函数设计和冲突处理策略。理解链地址法、开放地址法和负载因子的关系，是掌握 HashMap/HashSet 底层原理的关键。
普通 BST 在极端情况下会退化成链表（O(n) 操作）。
集合（Set）和映射（Map）是两种最基础的抽象数据类型。理解它们的底层实现（哈希表 vs 搜索树）是选择正确数据结构的关键。
graph LR
链表（Linked List） 是一种线性数据结构，由若干节点组成，每个节点包含数据和指向下一个节点的指针。
graph LR
链表是面试中出现频率最高的数据结构之一。反转、合并、环检测、排序等经典操作考察对指针操作的精准掌控。
graph LR
伸展树（Splay Tree） 是一种自调整（self-adjusting）的二叉搜索树，由 Sleator 和 Tarjan 于 1985 年提出。它不显式维...
树的直径是树上最远两点的距离，树的重心是删除后使最大连通分量最小的点。两者都是树形 DP 的经典应用。
Treap = Tree + heap。每个节点同时持有两个关键值：
树链剖分（Heavy-Light Decomposition, HLD）将树上的路径操作转化为 O(log n) 次区间操作，配合线段树实现高效的树上路径查询与...
树状数组（BIT / Fenwick Tree）是一种用于单点更新 + 前缀和查询的高效数据结构，两种操作均为 O(log n)，且代码极简、常数极小。
数组（Array） 是一种用连续内存存储相同类型元素的线性数据结构。它支持通过下标在 O(1) 时间内随机访问任意元素。
跳表（Skip List） 是一种基于有序链表的数据结构，通过建立多层索引实现 O(log n) 的查找、插入和删除。
在海量数据处理场景中，我们经常需要解决判重问题：
线段树是一种用于高效处理区间查询和区间更新的数据结构。它通常用于解决诸如区间求和、区间最小值/最大值查询等问题。
线段树的基础在于"区间查询 + 区间修改"，但真正的威力在于它的可扩展性：扫描线、区间合并、动态开点、可持久化……本节覆盖线段树在竞赛与面试中的进阶用法。
优先队列（PriorityQueue）在基础的 Top-K 之外，还能解决数据流中位数、任务调度、图的最短路径优化等复杂问题。本篇聚焦堆的进阶应用与多堆协作模式...
栈（Stack） 是一种后进先出（LIFO, Last In First Out） 的线性数据结构。就像一叠盘子——最后放上去的盘子最先被拿走。
主席树（Persistent Segment Tree）通过对每次修改保留历史版本，实现"查询第 k 个版本中某区间的值"。最经典应用是静态区间第 k 小。
graph LR
普通 BST 在有序数据插入时会退化为链表，查找从 O(log n) 退化到 O(n)。
B 树（B-Tree）和 B+ 树是专为磁盘 I/O 优化的多路平衡搜索树，是数据库索引和文件系统的核心数据结构。
数据库索引需要同时满足：
graph TD
graph LR
Trie，又称字典树或前缀树，是一种用于高效存储和检索字符串的树形数据结构。
博弈论研究多个理性决策者之间的策略互动。在算法竞赛中，Nim 游戏、SG 函数和 Sprague-Grundy 定理是核心工具，能判定组合游戏的必胜/必败态。
递归（Recursion） 是一种解决问题的方法，其中函数调用自身来解决问题的小实例。
graph TD
分治（Divide and Conquer） 将一个问题递归地分解为若干个规模更小的同类子问题，分别求解后再合并结果。
graph LR
编程语言内置的整数类型有上限（Java long 最大约 9.2×10^18）。当数字超过这个范围时（如 100 位的大数），必须用数组/字符串模拟竖式运算。
高斯消元法是求解线性方程组的经典算法，通过初等行变换将增广矩阵化为上三角（或行最简形），时间复杂度 O(n³)。
回溯（Backtracking） 是一种通过逐步构建候选解来搜索所有（或部分）可行解的算法策略。当发现当前路径不可能产生有效解时，立即撤销上一步选择（回退），尝...
计算几何研究几何对象的算法表示与操作，面试中常考：
快慢指针（Floyd's Tortoise and Hare）：两个指针从同一起点出发，快指针每次走两步，慢指针每次走一步。
快速幂将 O(n) 的幂运算优化为 O(log n)。矩阵快速幂进一步将线性递推的 O(n) 求解优化为 O(k³ log n)，是竞赛和面试中的高频技巧。
扩展欧几里得算法（exgcd）在求 GCD 的同时得到贝祖系数 x, y 使 ax + by = gcd(a,b)。它是求解模逆元、线性同余方程的基础工具。
graph TD
离散化（Coordinate Compression）将大范围的值域映射到连续的小范围整数，使得原本无法开数组的数据可以用线段树、树状数组等结构处理。
graph TD
graph TD
问题：给定数组，频繁查询区间 [l, r] 的和。
区间调度问题是贪心算法的经典应用场景：在有限资源下选择最多的不重叠区间。从简单的活动选择到复杂的会议室分配，核心都是"排序 + 贪心选择"。
区间类题目在面试中高频出现，且共享一套核心操作：排序 → 扫描 → 合并/插入/求交。掌握这套框架后，所有区间题都是变体。
扫描线（Sweep Line）是一种将二维问题降为一维的经典思想：用一条线沿某方向扫过平面，在扫描过程中用数据结构维护当前状态，高效处理区间覆盖、面积并等问题。
复杂度分析是对算法资源消耗的数学度量。
数论是算法竞赛和面试中的常见考点，涉及：
双指针（Two Pointers）是解决数组/链表问题最优雅的技巧之一。通过两个指针的协同移动，将 O(n²) 暴力枚举优化为 O(n) 线性扫描。
在数组/字符串题中，双指针 / 滑动窗口可以在线性时间 O(n) 内解决许多看似 O(n²) 的子数组问题，是面试最高频的题型之一。
graph LR
贪心（Greedy） 是一种在每一步都采取当前状态下最优选择的算法策略，希望通过局部最优得到全局最优。
graph LR
graph TD
中国剩余定理（CRT）求解一组两两互质模数下的同余方程组，是数论中最重要的定理之一，广泛应用于密码学、大数计算和竞赛编程。
组合数学是算法竞赛和面试中计数类问题的理论基础。排列、组合、容斥原理、卡特兰数等工具能优雅地解决"有多少种方案"类问题。
在游戏寻路、地图导航等场景中，我们需要在巨大地图中快速找到一条接近最短的路线。
CDQ 分治是一种离线算法框架，通过"分治 + 归并"的思想，将三维偏序等复杂计数问题降维处理，时间复杂度 O(n log²n)。
graph LR
编辑距离（Levenshtein Distance）：给定两个字符串 word1 和 word2，求将 word1 转换成 word2 所需的最少操作次数。允许...
graph LR
graph LR
LeetCode 上有 6 道经典股票题，看似各不相同，实则共享同一个状态机框架：
graph LR
记忆化搜索（Memoization）是自顶向下的动态规划实现方式，用递归 + 缓存代替递推，代码更直观、状态空间按需计算，是面试中快速写出 DP 的利器。
区间 DP 是在一个区间 [i, j] 上定义状态，通过枚举分割点 k 将大区间拆分为两个小区间来转移的 DP 模型。
树形 DP 是在树结构上进行动态规划。状态定义在节点上，转移通过子节点 → 父节点（后序遍历）完成。
数位 DP 是一类统计满足某条件的数的个数的动态规划方法。核心思路是将数字拆成各位，从高位到低位逐位决策，用"是否紧贴上限"作为状态。
状态机 DP 将问题建模为有限状态之间的转移，每个阶段根据当前状态做出决策并转移到下一状态。它是解决"带约束选择"问题（如股票买卖系列）的通用框架。
graph LR
最长递增子序列（Longest Increasing Subsequence）是动态规划的经典问题，从 O(n²) DP 到 O(n log n) 贪心+二分，...
最长公共子序列（Longest Common Subsequence）是动态规划的经典二维问题，广泛应用于 diff 工具、DNA 序列比对、版本控制等领域。
2-SAT（2-Satisfiability）是布尔可满足性问题的特殊情形：每个子句恰好含两个文字。它可以在 O(V+E) 时间内判定是否有解，并构造一组合法赋...
差分约束系统将一组形如 xⱼ - xᵢ ≤ c 的不等式转化为图上的最短路问题，用 Bellman-Ford 或 SPFA 判定可行性并求出一组解。
二分图（Bipartite Graph） 是一种特殊的无向图，其顶点可以分成两个互不相交的集合 A 和 B，使得每条边都连接 A 中的一个顶点和 B 中的一个顶...
graph LR
基础 BFS 从单一起点逐层扩展，能解决无权图最短路。但面试中有三类变体让朴素 BFS 力不从心：
graph TD
graph LR
欧拉回路/路径是图论中的经典问题：能否一笔画完所有边且不重复？从柯尼斯堡七桥问题到现代应用（DNA 测序、垃圾回收），欧拉算法无处不在。
拓扑排序（Topological Sort） 对有向无环图（DAG）的顶点排成线性序列，使得对每条有向边 (u, v)，u 都排在 v 前面。
图是最灵活也最复杂的数据结构。选择合适的存储方式（邻接矩阵/邻接表/边列表）和遍历策略（DFS/BFS）是解决所有图论问题的基础。
graph LR
网络流是图论中研究"流量"在带容量网络中如何分配的框架。最大流、最小割、费用流是三大核心问题，广泛应用于匹配、调度、资源分配等场景。
最短路径问题：在带权图中，找到从源点 s 到目标点 t（或所有点）的路径，使得路径上边的权值之和最小。
graph LR
最小生成树（Minimum Spanning Tree, MST）：在连通无向带权图中，选取 n-1 条边使所有顶点连通，且边权之和最小。
graph LR
Tarjan 算法通过一次 DFS 求出有向图中所有强连通分量（SCC），时间复杂度 O(V+E)。它是图论中最重要的线性算法之一。
后缀数组（Suffix Array）将字符串的所有后缀按字典序排列，配合 LCP（最长公共前缀）数组，可以高效解决大量字符串问题。
graph TD
graph TD
字符串是由字符组成的有限序列，是面试中出现频率最高的数据类型之一。
字符串哈希将字符串映射为整数，实现 O(1) 的子串比较。Rabin-Karp 算法利用滚动哈希在 O(n) 时间内完成模式匹配，并天然支持多模式匹配。
字符串匹配（Pattern Matching）：在文本串 text（长度 n）中查找模式串 pattern（长度 m）出现的位置。
AC 自动机（Aho-Corasick）= Trie + KMP 的 fail 指针，实现多模式串匹配：在文本中同时查找所有模式串，时间 O(n + 总模式长 ...
KMP（Knuth-Morris-Pratt）算法通过预处理模式串的"前缀函数"（next 数组），在匹配失败时跳过不必要的比较，实现 O(n+m) 的字符串匹...
Manacher 算法（马拉车算法）能在 O(n) 时间内求出字符串中每个位置的最长回文半径，从而找到最长回文子串。相比中心扩展的 O(n²)，它是回文问题的终...
面试设计题不考"背 API"，考的是组合基础结构达成目标复杂度的能力。核心思路：
graph LR
当算法层面已无法继续优化（如排序已是 O(n log n)），如何进一步提升性能？
如何自动过滤垃圾短信/垃圾邮件？三种递进方案：
面试和工程中最常见的错误不是"不会写代码"，而是选错数据结构——用数组做频繁查找，用链表做随机访问，用哈希表做范围查询。
将长 URL（如 https://example.com/very/long/path?param=xxx）转换为短链接（如 https://s.cn/Ab3x...
在高性能系统中（交易系统、日志收集、消息中间件），"生产者-消费者"模型无处不在。
搜索引擎是数据结构与算法的"集大成者"。从网页爬取到最终返回搜索结果，几乎用到了所有经典数据结构和算法。
微服务架构中，两个核心安全问题：
Redis 是高性能 Key-Value 内存数据库，其 5 种常用数据类型底层依赖了多种经典数据结构。理解这些底层实现，能帮助我们：
当数据量达到千万、亿级时，如何在海量数据中快速查找某条记录？
graph LR