算法思想总结
·
目录
一、基础策略
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 暴力枚举 | 遍历所有可能性，逐个验证 | 密码破解、穷举所有解 |
| 贪心算法 | 每步选局部最优，不回溯 | 活动选择、找零钱（部分场景） |
| 分治法 | 分解为独立子问题，递归解决后合并 | 归并排序、快速排序 |
| 回溯法 | DFS + 剪枝，尝试后回退撤销状态 | N皇后、迷宫寻路、数独求解 |
| 动态规划 | 记录子问题解（查表），避免重复计算 | 背包问题、编辑距离、LCS |
| 分支限界法 | BFS/优先队列 + 界限剪枝，求最优解 | 旅行商问题、任务分配 |
二、图遍历
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 深度优先搜索(DFS) | 沿一条路径深入到底，回溯，使用栈/递归 | 连通性检测、拓扑排序 |
| 广度优先搜索(BFS) | 层层推进，先访问所有邻居，使用队列 | 无权图最短路径、网络爬虫 |
三、动态规划细分
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 线性DP | 状态在一维/二维数组按顺序递推 | LIS、LCS、最大子数组和 |
| 背包DP | 在容量限制下选物品求最大价值 | 0/1背包、完全背包 |
| 区间DP | 由小区间合并成大区间递推 | 矩阵链乘法、石子合并 |
| 树形DP | 在树上做DFS后序遍历，子传父 | 树的直径、打家劫舍III |
| 状态压缩DP | 用二进制位表示集合状态 | TSP、集合覆盖问题 |
| 数位DP | 按十进制位逐位统计 | 统计1到n中不含某数字的个数 |
四、图论算法
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| Dijkstra | 贪心策略，优先队列，非负权 | 单源最短路径 |
| Bellman-Ford | 可处理负权边，检测负环 | 含负权边的单源最短路 |
| Floyd | 动态规划，多源，O(n³) | 任意两点间最短路径 |
| Kruskal | 按边权排序 + 并查集判环 | 最小生成树 |
| Prim | 优先队列，按点扩展 | 最小生成树 |
| 拓扑排序 | 对有向无环图节点线性排序（Kahn/DFS） | 课程表安排、编译依赖 |
| Tarjan | 强连通分量缩点 | 求强连通分量、缩点建图 |
| 网络流 | 求最大流量（Ford-Fulkerson/Dinic） | 最大流、最小割、二分图匹配 |
| 匈牙利算法 | 增广路找最大匹配 | 二分图最大匹配 |
五、字符串算法
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| KMP | 利用前缀函数（next数组），线性匹配 | 单模式串匹配 |
| Trie树 | 树形结构存储字符串集合，支持前缀查询 | 自动补全、单词搜索 |
| Manacher | 线性时间求最长回文子串 | 最长回文子串 |
| AC自动机 | Trie + KMP（fail指针），多模式匹配 | 敏感词过滤、多关键词搜索 |
六、数据结构
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 并查集 | 集合合并与查询连通性，路径压缩 | 朋友圈、Kruskal、连通块 |
| 线段树 | 递归维护区间信息，支持区间查询/更新 | 区间最值、区间和、动态RMQ |
| 树状数组 | 前缀查询 + 单点更新（lowbit操作） | 逆序对、动态前缀和 |
| 单调栈 | 维护单调序列，找左右第一个更大/更小元素 | 最大矩形面积、接雨水 |
| 单调队列 | 维护窗口内单调序列 | 滑动窗口最值 |
七、搜索优化
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 双向BFS | 起点终点同时BFS，相遇时停止 | 单词接龙、八数码问题 |
| A*搜索 | 带启发函数（f=g+h）的BFS | 游戏寻路、路径规划 |
| 迭代加深 | 限制深度DFS，逐渐放宽 | 棋盘搜索、IDA* |
八、智能优化
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 模拟退火 | 概率接受较差解以跳出局部最优 | 函数最值、TSP近似解 |
| 遗传算法 | 选择、交叉、变异迭代进化 | 优化问题、神经网络结构搜索 |
九、其他常用技巧
| 算法名称 | 核心特征 | 主要应用场景 |
|---|---|---|
| 双指针 | 两个指针协同扫描数组 | 两数之和、链表判环 |
| 前缀和/差分 | 预处理O(1)区间查询 / O(1)区间加减 | 区间和、差分数组 |
| 快速幂 | 二分乘法，O(log n)计算幂次 | a^b mod m、矩阵快速幂 |
| 扩展欧几里得 | 解线性同余方程，求逆元 | 求逆元、解模线性方程 |
| 素数筛 | 标记法批量筛素数（埃筛/欧拉筛） | 求n以内所有素数 |
| Miller-Rabin | 大数概率性素性测试 | 大数素数判断 |
一站式 AI 云服务平台
更多推荐
6
0- 0
已为社区贡献1条内容
所有评论(0)