算法知识 #
以下是笔者整理的算法相关的知识。希望能把常见的算法都枚举穷尽。如有遗漏，欢迎大家赐教，提 PR。相关题目还在慢慢整理中，讲解的文章还在创作中。
刷题只是提升算法能力的手段，最终目的应该是提升自我的思维能力，知识需要凝结成块，那么就把这些总结在第一章这两节中，让它得到升华吧~希望读者在刷完题之后再回过头来看这个表格，能很清晰的梳理自己的知识体系，查缺补漏，尽早完善。
| 算法 | 具体类型 | 相关题目 | 讲解文章 |
|---|---|---|---|
| 排序算法 | 1. 冒泡排序 2. 插入排序 3. 选择排序 4. 希尔 Shell 排序 5. 快速排序 6. 归并排序 7. 堆排序 8. 线性排序算法 9. 自省排序 10. 间接排序 11. 计数排序 12. 基数排序 13. 桶排序 14. 外部排序 - k 路归并败者树 15. 外部排序 - 最佳归并树 | ||
| 递归与分治 | 1. 二分搜索/查找 2. 大整数的乘法 3. Strassen 矩阵乘法 4. 棋盘覆盖 5. 合并排序 6. 快速排序 7. 线性时间选择 8. 最接近点对问题 9. 循环赛日程表 | ||
| 动态规划 | 1. 矩阵连乘问题 2. 最长公共子序列 3. 最大子段和 4. 凸多边形最优三角剖分 5. 多边形游戏 6. 图像压缩 7. 电路布线 8. 流水作业调度 9. 0-1 背包问题/背包九讲 10. 最优二叉搜索树 11. 动态规划加速原理 12. 树型 DP | ||
| 贪心 | 1. 活动安排问题 2. 最优装载 3. 哈夫曼编码 4. 单源最短路径 5. 最小生成树 6. 多机调度问题 | ||
| 回溯法 | 1. 装载问题 2. 批处理作业调度 3. 符号三角形问题 4. n 后问题 5. 0-1 背包问题 6. 最大团问题 7. 图的 m 着色问题 8. 旅行售货员问题 9. 圆排列问题 10. 电路板排列问题 11. 连续邮资问题 | ||
| 搜索 | 1. 枚举 2. DFS 3. BFS 4. 启发式搜索 | ||
| 随机化 | 1. 随机数 2. 数值随机化算法 3. Sherwood 舍伍德算法 4. Las Vegas 拉斯维加斯算法 5. Monte Carlo 蒙特卡罗算法 | 1. 计算 π 值 2. 计算定积分 3. 解非线性方程组 4. 线性时间选择算法 5. 跳跃表 6. n 后问题 7. 整数因子分解 8. 主元素问题 9. 素数测试 | |
| 图论 | 1. 遍历 DFS / BFS 2. AOV / AOE 网络 3. Kruskal 算法(最小生成树) 4. Prim 算法(最小生成树) 5. Boruvka 算法(最小生成树) 6. Dijkstra 算法(单源最短路径) 7. Bellman-Ford 算法(单源最短路径) 8. SPFA 算法(单源最短路径) 9. Floyd 算法(多源最短路径) 10. Johnson 算法(多源最短路径) 11. Fleury 算法(欧拉回路) 12. Ford-Fulkerson 算法(最大网络流增广路) 13. Edmonds-Karp 算法(最大网络流) 14. Dinic 算法(最大网络流) 15. 一般预流推进算法 16. 最高标号预流推进 HLPP 算法 17. Primal-Dual 原始对偶算法(最小费用流)18. Kosaraju 算法(有向图强连通分量) 19. Tarjan 算法(有向图强连通分量) 20. Gabow 算法(有向图强连通分量) 21. 匈牙利算法(二分图匹配) 22. Hopcroft－Karp 算法(二分图匹配) 23. kuhn munkras 算法(二分图最佳匹配) 24. Edmonds’ Blossom-Contraction 算法(一般图匹配) | 1. 图遍历 2. 有向图和无向图的强弱连通性 3. 割点/割边 3. AOV 网络和拓扑排序 4. AOE 网络和关键路径 5. 最小代价生成树/次小生成树 6. 最短路径问题/第 K 短路问题 7. 最大网络流问题 8. 最小费用流问题 9. 图着色问题 10. 差分约束系统 11. 欧拉回路 12. 中国邮递员问题 13. 汉密尔顿回路 14. 最佳边割集/最佳点割集/最小边割集/最小点割集/最小路径覆盖/最小点集覆盖 15. 边覆盖集 16. 二分图完美匹配和最大匹配问题 17. 仙人掌图 18. 弦图 19. 稳定婚姻问题 20. 最大团问题 | |
| 数论 | 1. 最大公约数 2. 最小公倍数 3. 分解质因数 4. 素数判定 5. 进制转换 6. 高精度计算 7. 整除问题 8. 同余问题 9. 欧拉函数 10. 扩展欧几里得 11. 置换群 12. 母函数 13. 离散变换 14. 康托展开 15. 矩阵 16. 向量 17. 线性方程组 18. 线性规划 | ||
| 几何 | 1. 凸包 - Gift wrapping 2. 凸包 - Graham scan 3. 线段问题 4. 多边形和多面体相关问题 | ||
| NP 完全 | 1. 计算模型 2. P 类与 NP 类问题 3. NP 完全问题 4. NP 完全问题的近似算法 | 1. 随机存取机 RAM 2. 随机存取存储程序机 RASP 3. 图灵机 4. 非确定性图灵机 5. P 类与 NP 类语言 6. 多项式时间验证 7. 多项式时间变换 8. Cook定理 9. 合取范式的可满足性问题 CNF-SAT 10. 3 元合取范式的可满足性问题 3-SAT 11. 团问题 CLIQUE 12. 顶点覆盖问题 VERTEX-COVER 13. 子集和问题 SUBSET-SUM 14. 哈密顿回路问题 HAM-CYCLE 15. 旅行售货员问题 TSP 16. 顶点覆盖问题的近似算法 17. 旅行售货员问题近似算法 18. 具有三角不等式性质的旅行售货员问题 19. 一般的旅行售货员问题 20. 集合覆盖问题的近似算法 21. 子集和问题的近似算法 22. 子集和问题的指数时间算法 23. 子集和问题的多项式时间近似格式 | |
| 位运算 | 位操作包括： 1. 取反（NOT） 2. 按位或（OR） 3. 按位异或（XOR） 4. 按位与（AND） 5. 移位: 是一个二元运算符，用来将一个二进制数中的每一位全部都向一个方向移动指定位，溢出的部分将被舍弃，而空缺的部分填入一定的值。 | 1.数字范围按位与 2.UTF-8 编码验证 3.数字转换为十六进制数 4.找出最长的超赞子字符串 5.数组异或操作 6.幂集 7.位1的个数 8.二进制表示中质数个计算置位 9.子数组异或查询 | 力扣：位运算 |
| ———— | —————————————————————— | —————————————————————– | ——————– |