Leetcode Summary

常用算法思想

算法思想	核心逻辑	典型应用场景	主要步骤
暴力枚举 (Brute Force)	穷举所有可能，适合数据量小或无更优解法时使用	子集、全排列、简单模拟	列举所有可能 → 检查每种情况
递归 (Recursion)	问题自我调用自身，分解为更小子问题	树遍历、分治、回溯	设定终止条件 → 递归调用自身 → 合并结果
回溯 (Backtracking)	递归试探所有可能，遇到不合法就回退	组合、排列、N皇后、数独	尝试选择 → 递归探索 → 发现不行就回退（撤销选择）
分治（Divide & Conquer）	拆解为子问题递归解决后合并结果	归并排序、快速排序、最近点对	拆分问题 → 递归求解 → 合并结果
双指针 (Two Pointers)	用两个指针遍历或扫描序列	区间、排序、去重、链表	指针初始化 → 同步/异步移动 → 满足条件时处理
滑动窗口 (Sliding Window)	维护一个区间窗口，动态调整窗口边界	子串/子数组、最短区间	扩大窗口 → 满足条件时收缩窗口 → 记录最优解
哈希 (Hashing)	用哈希表快速查找、去重、计数等	查重、计数、映射	构建哈希表 → 查找/插入/删除 → 处理冲突
栈/队列 (Stack/Queue)	先进后出/先进先出，辅助递归、遍历	括号匹配、层序遍历、单调栈	入栈/队 → 弹出/出队 → 处理元素
单调栈/队列 (Monotonic Stack/Queue)	维护单调性，区间最值	下一个更大元素、滑动窗口最大值	入栈/队时维护单调 → 弹出不符元素 → 记录答案
并查集 (Union Find)	处理集合合并与查询	连通性、分组、朋友圈	初始化集合 → 合并集合 → 查询根节点
拓扑排序 (Topological Sort)	有向无环图排序	任务调度、依赖关系	统计入度 → 队列弹出入度为0节点 → 更新入度
贪心（Greedy）	每一步选择局部最优	区间调度、最小生成树、跳跃游戏	按规则排序/选择 → 每步取最优 → 得到全局解
动态规划（DP）	分解为重叠子问题，递推求解	背包、最长子序列、股票买卖	定义状态 → 状态转移 → 递推填表
记忆化搜索 (Memoization)	递归+缓存子问题结果，避免重复计算	递归DP、树形DP	递归求解 → 查询/保存子问题结果 → 返回答案
二分查找 (Binary Search)	有序区间每次折半查找	有序数组、最值判定	设定左右边界 → 取中间值 → 判断调整区间
位运算 (Bit Manipulation)	用二进制位操作优化空间和速度	状态压缩、子集枚举	构造掩码 → 按位操作 → 组合/判断状态
树状数组/线段树 (BIT/Segment Tree)	区间查询与修改，适合动态数据结构	区间和、区间最值	构建树结构 → 查询/修改区间 → 递归/迭代更新
有限状态机（FSM）	定义状态和转移规则，按输入切换	KMP、正则表达式解析	设计状态 → 按输入转移 → 处理输出
随机化算法（Randomized）	利用随机性加速或近似求解	快速排序、素数测试	随机选择/采样 → 多次尝试 → 统计/判断
Meet in the Middle	分两半分别求解后合并结果	超大背包、子集和	拆分集合 → 分别枚举 → 合并统计
扫描线（Sweep Line）	按顺序扫描事件处理区间重叠	矩形面积并、航班统计	排序事件 → 顺序扫描 → 动态维护区间
启发式搜索（Heuristic）	用估价函数优先探索更优路径	A*、八数码、路径规划	设计估价函数 → 优先队列扩展 → 找到目标
模拟退火（Simulated Annealing）	概率性接受次优解跳出局部最优	TSP、参数优化	初始解 → 随机扰动 → 接受/拒绝新解
遗传算法（Genetic Algorithm）	模拟进化逼近最优解	组合优化、超参数调优	编码种群 → 选择/交叉/变异 → 迭代进化

数学与几何相关算法

算法思想	核心逻辑	典型应用场景	主要步骤
数论（Number Theory）	利用质数、模运算、同余等性质解决问题	RSA加密、约瑟夫环	分析性质 → 设计公式/递推 → 求解
计算几何（Computational Geometry）	向量、叉积等处理几何图形	凸包、最近点对、线段相交	坐标建模 → 几何运算 → 判断/统计
线性代数（Linear Algebra）	矩阵运算、特征值分解等高维问题	PCA、SVD、图像处理	构建矩阵 → 运算/分解 → 得到结果

字符串处理专项

算法思想	核心逻辑	典型应用场景	主要步骤
KMP算法	部分匹配表避免重复匹配	字符串模式匹配	构建next表 → 匹配时跳转 → 找到所有位置
Trie（前缀树）	树形结构存储字符串，共享前缀	自动补全、词频统计	构建树结构 → 插入/查找 → 统计/输出
后缀自动机（SAM）	压缩后缀信息高效处理子串	最长重复子串、子串计数	构建自动机 → 状态转移 → 统计答案
Rabin-Karp	滚动哈希快速比较子串	多模式匹配、查重	计算哈希 → 滑动窗口 → 比较/确认

图论进阶算法

算法思想	核心逻辑	典型应用场景	主要步骤
网络流（Network Flow）	建模为流量网络，求最大流/最小割	任务分配、二分图匹配	建图 → 增广路/推流 → 统计最大流
欧拉回路/路径	遍历所有边且不重复	邮路、DNA组装	统计度数 → DFS/栈遍历 → 记录路径
Tarjan算法	DFS求强连通分量、割点/桥	社区发现、电路设计	DFS遍历 → 记录时间戳 → 标记分量
匈牙利算法	增广路径求二分图最大匹配	任务分配、约会匹配	匹配初始化 → DFS/BFS增广 → 更新匹配

特殊场景优化算法

算法思想	核心逻辑	典型应用场景	主要步骤
离线算法（Offline）	预处理所有查询后统一处理	区间统计、莫队算法	收集所有查询 → 排序/分组 → 统一处理
增量算法（Incremental）	逐步添加数据动态维护结果	实时数据流处理	初始化结构 → 每次插入/更新 → 维护答案
近似算法（Approximation）	牺牲精度换取效率	NP难问题工程解法	设计近似规则 → 迭代优化 → 得到可行解