算法题常用版速查（大类 -> 方法 -> 一句话用途）

用途：

• 比“极简版”多一层说明
• 适合平时翻看，快速知道“这个方法是干嘛的”
• 不展开讲模板，只做知识框架速查

1. 数组

• 遍历：最基础的方法，用来顺序处理、统计、查找元素。
• 模拟：按题目要求一步一步执行过程，适合规则明确的题。
• 双指针：常用于有序数组、对撞搜索、原地修改、去重。
• 快慢指针：常用于原地删除元素、压缩数组、保留满足条件的值。
• 滑动窗口：常用于连续子数组/子串的最长、最短、个数问题。
• 前缀和：常用于快速求区间和，或把连续区间问题转成差值问题。
• 差分：常用于区间批量加减更新，最后统一还原结果。
• 哈希统计：常用于频次统计、去重、快速判断是否存在。
• 排序：常用于先建立顺序，再做去重、合并、贪心、二分等操作。
• 二分查找：常用于有序数组中查值、找边界、找插入位置。
• 单调栈：常用于找左边/右边第一个更大或更小的元素。
• 单调队列：常用于滑动窗口内维护最大值或最小值。
• 堆 / 优先队列：常用于维护前 K 个元素、动态最值。
• 摩尔投票：常用于找出现次数超过一半的元素。
• 位运算：常用于状态压缩、异或去重、二进制技巧题。
• 动态规划：常用于求最优值、方案数、可行性问题。
• 贪心：常用于每一步做局部最优，最终得到整体较优解。

2. 字符串

• 遍历：适合基础统计、比较、构造新字符串。
• 模拟：适合按字符规则转换、解析表达式、处理进位。
• 双指针：常用于回文判断、反转、从两端向中间处理。
• 滑动窗口：常用于连续子串的长度、覆盖、去重类问题。
• 哈希计数：常用于字符频次统计、异位词判断。
• 排序：常用于统一字符顺序，便于比较字符串是否等价。
• 栈：常用于括号匹配、字符串消除、表达式处理。
• 前缀和：常用于某类字符区间统计。
• KMP：常用于高效字符串匹配，避免重复比较。
• Trie（前缀树）：常用于前缀匹配、词典搜索、多单词查询。
• 回文处理：常用于判断回文、最长回文子串/子序列。
• 动态规划：常用于编辑距离、公共子序列、回文问题。
• 回溯：常用于字符串切割、生成所有合法结果。
• 位运算：常用于字符状态压缩、判重、大小写技巧。

3. 链表

• 遍历：最基础的方法，用来查找、统计、定位节点。
• 虚拟头结点：适合统一处理头节点删除、插入等边界情况。
• 快慢指针：常用于找中点、找环、找倒数第 k 个节点。
• 反转链表：常用于局部反转、整体反转、回文链表等题。
• 双指针：常用于链表合并、节点定位、间隔追赶。
• 分组合并：常用于每 k 个一组反转、链表重排等题。
• 递归：适合写法简洁的链表反转、合并、删除类问题。
• 分治：常用于合并 K 个有序链表、链表排序。
• 哈希映射：常用于随机指针复制、节点映射关系处理。

4. 栈 / 队列 / 堆

栈

• 普通栈：适合后进先出场景，如括号匹配、路径回退、表达式求值。
• 单调栈：适合快速找最近更大/更小元素。
• 辅助栈：适合在普通栈基础上额外维护最值等信息。

队列

• 普通队列：适合先进先出场景，如 BFS 层序遍历。
• 双端队列：适合两端插入删除，常用于窗口维护。
• 单调队列：适合在线维护窗口最值。

堆

• 小顶堆：适合随时取当前最小值。
• 大顶堆：适合随时取当前最大值。
• 双堆：适合同时维护一半较大值和一半较小值，如中位数问题。

5. 哈希

• HashMap：适合维护键值映射、频次统计、位置记录。
• HashSet：适合快速判重、集合去重、判断存在性。
• 频次统计：适合统计元素/字符出现次数。
• 映射关系：适合维护旧值到新值、字符到字符、节点到节点的关系。
• 去重：适合过滤重复元素或判断是否出现过。
• 前缀和 + 哈希：适合统计某个区间和条件是否满足。
• 状态记录：适合记录某个状态是否访问过或出现过。

6. 树

• DFS 递归：适合树的天然递归结构，如深度、路径、子树问题。
• DFS 迭代：适合用栈模拟递归遍历，避免递归栈。
• BFS 层序遍历：适合按层处理树节点。
• 前序 / 中序 / 后序：适合不同遍历需求，尤其 BST 常用中序。
• 分治递归：适合把问题拆成左右子树分别求解。
• 回溯：适合根到叶路径、路径和等需要恢复现场的问题。
• BST 性质：适合利用左小右大的特点剪枝或快速定位。
• 树形 DP：适合树上选点、树上最优值问题。
• 前缀树 Trie：适合存大量字符串并支持高效前缀查询。

7. 图

• DFS：适合做连通性判断、遍历整张图、找所有可达点。
• BFS：适合无权图最短路径、分层扩散问题。
• 拓扑排序：适合处理依赖关系、任务顺序、有向无环图问题。
• 并查集：适合处理动态连通性、集合合并、成环判断。
• 最短路径：适合求起点到终点的最小代价。
• 最小生成树：适合在保证连通的前提下让总边权最小。
• 染色法：适合二分图判断、图着色类问题。
• Floyd：适合求任意两点之间最短路。
• Bellman-Ford / SPFA：适合处理带负权边的最短路问题。

8. 搜索

• DFS：适合一路走到底地搜索所有可能路径。
• BFS：适合一层一层扩展，常用于求最短步数。
• 双向 BFS：适合起点和终点已知时加速最短路搜索。
• 回溯：适合枚举所有解，并在返回时撤销选择。
• 剪枝：适合提前砍掉不可能更优或非法的分支。
• 记忆化搜索：适合把重复搜索结果缓存下来，避免重复计算。

9. 排序

基础排序

• 冒泡排序：适合理解交换思想，但实战较少使用。
• 选择排序：适合理解每轮选择最值的思想。
• 插入排序：适合数据规模小或基本有序时使用。
• 希尔排序：是插入排序的改进版，减少大量移动。

进阶排序

• 归并排序：适合稳定排序、链表排序、分治处理。
• 快速排序：适合平均性能优秀的通用排序场景。
• 堆排序：适合边维护最值边排序。

非比较排序

• 计数排序：适合数据范围小且整数值集中的场景。
• 桶排序：适合数据分布较均匀的场景。
• 基数排序：适合按位排序的整数或字符串场景。

10. 查找

• 顺序查找：适合数据无序且规模小的简单场景。
• 二分查找：适合有序数据的快速查找和边界定位。
• 哈希查找：适合近似 O(1) 的快速存在性判断。
• 树查找：适合动态维护有序结构。
• 堆查找：适合快速拿到最值，但不适合查任意值。

11. 二分

• 标准二分：适合在有序数组中找某个值。
• 边界二分：适合找第一个/最后一个满足条件的位置。
• 答案二分：适合“最小的可行值”或“最大的满足值”问题。
• 二分 + check：适合把问题转成“给定答案是否成立”的判定问题。
• 二分搜索树上答案：适合答案具有单调性的场景。

12. 回溯

• 组合：适合从若干元素中选若干个，不考虑顺序。
• 子集：适合枚举一个集合的所有选法。
• 排列：适合枚举所有顺序不同的安排方式。
• 切割：适合把字符串或数组切成若干段的所有方案。
• 枚举路径：适合从起点到终点找所有可行路径。
• 棋盘搜索：适合 N 皇后、数独、单词搜索等题。
• 剪枝优化：适合减少无效分支，提高搜索效率。

13. 动态规划

基础 DP

• 线性 DP：适合当前位置只依赖前面若干状态的问题。
• 记忆化搜索：适合自顶向下写递归，再缓存中间结果。
• 滚动数组优化：适合压缩 DP 空间，减少内存使用。

常见 DP 分类

• 背包 DP：适合“选或不选”以及容量限制类问题。
• 区间 DP：适合对子数组/子串区间求最优值。
• 子序列 DP：适合编辑距离、最长公共子序列等问题。
• 状态机 DP：适合股票买卖、持有/不持有转换问题。
• 树形 DP：适合树结构上的最优值问题。
• 数位 DP：适合统计某范围数字中满足条件的个数。
• 概率 DP：适合概率转移、期望计算问题。
• 状压 DP：适合状态数量不大、可以用二进制表示状态的问题。

14. 贪心

• 排序贪心：适合先排序，再按某种规则局部最优选择。
• 区间贪心：适合区间覆盖、选最多不重叠区间等问题。
• 局部最优：适合每一步直接做当前最优选择。
• 反悔贪心：适合先做选择，后面必要时撤销并调整。
• 堆优化贪心：适合一边贪心选择，一边动态维护候选项。

15. 区间问题

• 排序 + 合并：适合区间合并、插入区间、去重叠问题。
• 前缀和：适合区间求和、区间统计。
• 差分：适合区间批量更新。
• 贪心：适合区间选择、覆盖、调度问题。
• 堆：适合处理区间资源分配，如会议室问题。
• 线段树：适合动态区间查询和更新。
• 树状数组：适合高效单点更新、前缀查询。

16. 数学

• 模拟：适合按数学规则一步步计算结果。
• 找规律：适合通过观察样例提炼公式或结论。
• 进制转换：适合数字与字符串编码映射问题。
• 最大公约数 GCD：适合求整除关系、约分、循环规律。
• 最小公倍数 LCM：适合同步周期、倍数类问题。
• 快速幂：适合高效计算大幂次结果。
• 质数筛：适合批量判断或统计素数。
• 组合数学：适合计数类、选法类问题。
• 容斥原理：适合多个条件重叠统计问题。
• 概率：适合随机过程、期望、概率转移问题。
• 同余：适合取模运算、循环节问题。
• 矩阵快速幂：适合优化递推数列计算。

17. 位运算

• 异或：适合去重、找只出现一次的数、状态切换。
• 与 / 或 / 非：适合做位级条件判断和状态组合。
• 左移 / 右移：适合做乘除 2、按位处理。
• lowbit：适合快速提取二进制最低位的 1。
• 位掩码：适合用一个整数表示多个开关状态。
• 状态压缩：适合把集合状态压成二进制进行搜索或 DP。
• 子集枚举：适合枚举某个集合的所有子集。

18. 设计题 / 数据结构题

• 栈：适合后进先出访问场景。
• 队列：适合先进先出访问场景。
• 双端队列：适合两端都要高效操作的场景。
• 堆：适合维护动态最值。
• 哈希表：适合快速查找、插入、删除。
• 链表：适合频繁插入删除。
• 双向链表：适合同时高效访问前驱和后继。
• Trie：适合前缀检索和字典树问题。
• 并查集：适合集合合并和连通性判断。
• LRU / LFU：适合缓存淘汰策略设计。
• 线段树：适合复杂区间操作。
• 树状数组：适合前缀统计与动态更新。
• 跳表：适合作为平衡树的替代有序结构。

19. 高频基础模块（优先掌握）

• 哈希：解决频次、去重、映射、存在性判断的高频工具。
• 双指针：解决数组和字符串中大量原地处理与有序搜索问题。
• 滑动窗口：解决连续区间最值与计数问题的高频方法。
• 快慢指针：解决链表中点、环、倒数节点等经典问题。
• 二分：解决有序查找、边界定位、答案搜索问题。
• 栈 / 单调栈：解决括号、表达式、最近更大更小元素问题。
• 堆：解决前 K、大量动态最值问题。
• 二叉树 DFS / BFS：解决树遍历、路径、层序、递归问题。
• 图的 DFS / BFS：解决图遍历、连通性、最短步数问题。
• 回溯：解决组合、子集、排列、搜索所有解问题。
• 动态规划基础：解决最优值、方案数、可行性问题。
• 贪心：解决区间、排序选择、局部最优类问题。
• 并查集：解决连通块、合并集合、判环问题。
• 拓扑排序：解决依赖关系和任务顺序问题。

20. 最简记忆版

• 数组：双指针 / 滑动窗口 / 前缀和 / 差分 / 哈希 / 二分 / 单调结构。
• 字符串：双指针 / 滑动窗口 / 哈希 / 栈 / KMP / Trie / DP。
• 链表：虚拟头 / 快慢指针 / 反转 / 合并 / 哈希。
• 树：DFS / BFS / 递归 / BST / 树形 DP。
• 图：DFS / BFS / 拓扑 / 并查集 / 最短路。
• 排序：基础排序 / 高级排序 / 非比较排序。
• 搜索：DFS / BFS / 回溯 / 剪枝 / 记忆化搜索。
• 二分：查值 / 查边界 / 查答案。
• DP：线性 / 背包 / 区间 / 子序列 / 状态机 / 树形。
• 贪心：排序贪心 / 区间贪心 / 反悔贪心。
• 数学：模拟 / 规律 / 进制 / GCD / 快速幂。
• 位运算：异或 / 位掩码 / 状压。