非启发式算法学习知识目录

简介: 非启发式算法学习知识目录

小编整理的算法学习知识目录

读大学时,小编有幸参加过ACM算法比赛,也收集了不少算法模板,现在整理了一个算法目录,大家可以根据相关的介绍,找一些学习资料。学习某个算法时,大家可以使用关键字ACM+算法名称在搜索引擎搜索,搜出来的算法文章内容一般质量更高。

动态规划

  1. 「背包问题:」 解决背包问题的动态规划算法,涉及如何在有限容量下选择物品以达到最优价值。
  2. 「树形 DP:」 处理树形结构上的动态规划问题,通常通过递归或DFS来计算子树状态。
  3. 「状态压缩 DP:」 使用状态压缩技巧来简化动态规划问题,通常在状态较多时有效。
  4. 「概率 DP:」 利用概率的动态规划方法解决问题,考虑事件发生的可能性和期望价值。
  5. 「插头 DP:」 插头DP是一种处理序列问题的动态规划方法,通常用于求解字符串匹配等问题。
  6. 「区间 DP:」 解决涉及区间操作的动态规划问题,考虑如何将问题划分为多个互不重叠的区间进行求解。
  7. 「数位 DP:」 处理数字位操作的动态规划问题,通常用于解决数字相关的排列组合问题。
  8. 「最长公共子序列:」 使用动态规划求解两个序列中的最长公共子序列。
  9. 「最大连续和:」 动态规划方法解决数组中找出最大连续和的问题。
  10. 「数字三角形:」 利用动态规划处理三角形形状的数据结构,通常用于求解最优路径问题。
  11. 「最长上升子序列:」 使用动态规划找出序列中的最长上升子序列。
  12. 「贪心:」 贪心算法的应用,通常用于求解一些最优化问题,每一步都做出当前最优选择。
  13. 「嵌套矩形:」 解决嵌套矩形问题的动态规划算法,通常用于求解最大嵌套矩形数量。
  14. 「斜率优化 DP:」 在动态规划中使用斜率优化方法,通常用于优化状态转移方程的计算。

字符串算法

  1. 「最小表示法:」 最小表示法是用于求解循环同构字符串的算法,通过比较字符串的循环同构性质,找到字符串的最小表示形式。
  2. 「KMP 算法模板:」 Knuth-Morris-Pratt(KMP)算法是一种高效的字符串匹配算法,通过构建部分匹配表(next数组)来加速字符串匹配过程。
  3. 「扩展 KMP:」 扩展 KMP 算法是在 KMP 算法基础上拓展得到的,用于解决更复杂的字符串匹配问题,可以同时匹配多个模式串。
  4. 「AC 自动机:」 AC 自动机是一种用于多模式匹配的高效算法,利用Trie树和失败指针实现,在一个文本中同时查找多个模式串的出现位置。
  5. 「Trie 树:」 Trie 树(字典树)是一种用于存储动态集合或关联数组的树状数据结构,常用于字符串检索和前缀匹配。
  6. 「Manacher 算法:」 Manacher 算法用于查找字符串中的最长回文子串,通过预处理字符串,避免了传统动态规划算法中重复计算的问题,提高了效率。
  7. 「后缀数组:」 后缀数组是一种用于解决字符串相关问题的数据结构,它存储了字符串的所有后缀的排列顺序,可以高效解决很多字符串匹配和排序问题。
  8. 「括号匹配问题:」 解决括号匹配问题的算法,通过栈的数据结构或其他方法来判断字符串中的括号是否匹配正确。
  9. 「Hash 字符串:」 Hash 字符串是通过哈希函数将字符串映射为一个固定大小的哈希值,常用于加速字符串比较和匹配的过程,尤其在大规模文本数据中的应用。

数学专题

  1. 「剩余类:」 剩余类是解决同余方程的概念,通过对模数的选择,可以简化模运算的问题。
  2. 「扩展欧几里得:」 扩展欧几里得算法用于求解整数的最大公约数,并计算满足 Bézout 等式的系数。
  3. 「欧拉函数:」 欧拉函数是计算小于某个正整数的与该数互质的正整数个数,常用于解决模运算中的问题。
  4. 「莫比乌斯函数:」 莫比乌斯函数用于表示正整数的因数个数和符号,常用于组合数学和数论中的计算。
  5. 「乘法逆元:」 乘法逆元是对于给定的模数和整数,找到满足乘法逆元关系的整数,常用于解决除法取模的问题。
  6. 「素数:」 素数是仅有两个正因数(1和自身)的正整数,常用于解决数论和密码学中的问题。
  • 「miller_rabin 和 pollard_rho:」 两种用于素数判定和整数分解的算法,分别基于 Miller-Rabin 素数测试和 Pollard Rho 整数分解算法。
  • 「快速筛法:」 一种高效求解素数的算法,常用于生成素数表。
  1. 「大模拟:」 处理大整数运算和模运算的问题,包括高斯消元和分数加减乘除的实现。
  2. 「组合数学:」 解决组合数学中的问题,包括容斥定理的应用。
  3. 「卢卡斯定理:」 卢卡斯定理用于计算组合数的模,通过将组合数问题转化为模运算问题。
  4. 「Burnside 定理:」 Burnside 定理用于计算循环置换群的不动点数量,常用于组合计数问题。
  5. 「快速幂:」 快速幂算法是高效计算幂运算的方法,通过分治和二进制思想降低计算复杂度。
  6. 「中国剩余定理:」 中国剩余定理用于解决一组同余方程,通过对模数的两两互质性质降低问题的复杂度。
  7. 「高次同余方程:」 解决高次同余方程的问题,通过模运算和扩展欧几里得算法求解。
  8. 「鸽巢原理:」 鸽巢原理是一种基于抽屉原理的计数方法,常用于解决放置对象到有限数量的容器中的问题。
  9. 「数位统计问题:」 处理整数的数位表示和统计问题,通常用于计数问题的求解。
  10. 「二分搜索:」 二分搜索是一种通过减半搜索空间的方法,常用于解决有序数组或有序序列中的查找问题。
  11. 「三分搜索:」 三分搜索是一种通过减小或增大搜索空间的方法,常用于解决某个函数的极值问题。
  12. 「模拟退火:」 模拟退火是一种通过模拟物理退火过程的优化算法,常用于求解复杂问题的近似最优解。
  13. 「函数最值求解问题:」 解决函数最值问题的算法,通过搜索函数的极值点来找到最优解。
  14. 「TSP 问题:」 旅行商问题(TSP)是一种求解旅行商遍历所有城市的最短路径问题,通过动态规划等方法求解。
  15. 「卡特兰数:」 卡特兰数是一种计数数学中的数列,通常用于解决组合计数问题。
  16. 「那罗延数:」 那罗延数是一种数论中的数列,用于表示阶乘的另一种形式。
  17. 「平面上的直线问题:」 解决平面上直线交点等问题的算法,常用于几何学中的计算。
  18. 「伯努利数:」 伯努利数是一种数学中的数列,用于表示数学中的一些常见问题,如组合数。
  19. 「斐波那契数:」 斐波那契数列是一种数学中的数列,通过递归或动态规划求解。
  20. 「斯特林数:」 斯特林数是一种数学中的数列,用于计算排列组合问题。
  21. 「贝尔数:」 贝尔数是一种数学中的数列,表示将集合分割的方法数。
  22. 「进制转换模板:」 处理进制转换问题的算法模板,通常用于不同进制间的数值转换。
  23. 「异或的一道题:」 解决异或运算相关的问题,常用于位运算和密码学中。
  24. 「错排问题:」 错排问题是一种计数问题,表示排列中所有元素都不在其原始位置上的方法数。
  25. 「快速傅里叶变换:」 快速傅里叶变换是一种高效计算离散傅里叶变换的算法,常用于信号处理和多项式求解。
  26. 「快速数论变换:」 快速数论变换是一种高效计算离散傅里叶变换的算法,常用于数论和密码学中。
  27. 「线性规划模板:」 解决线性规划问题的算法模板,通常用于优化问题的求解。

数据结构专题

  1. 「Vector、Pair:」 Vector是C++标准模板库(STL)中的动态数组实现,Pair是一个可以容纳两个不同类型的值的模板类,常用于构建简单的数据结构。
  2. 「Bitset:」 Bitset是C++标准模板库(STL)中的一个类,用于存储位序列,支持位运算,通常用于位操作和压位。
  3. 「优先队列:」 优先队列是一种支持高效插入和删除最大或最小元素的数据结构,通常用堆实现。
  4. 「双端队列:」 双端队列是一种允许在两端进行插入和删除操作的数据结构,常用于需要在队列两端进行操作的场景。
  5. 「二叉堆:」 二叉堆是一种特殊的堆实现,分为最大堆和最小堆,常用于优先队列的底层实现。
  6. 「Map:」 Map是C++ STL中的关联容器,实现了键-值对的存储和访问,通常基于红黑树实现。
  7. 「Multimap:」 Multimap是Map的一种变体,允许多个相同键对应不同的值,通常用于多对一关系的存储。
  8. 「Set:」 Set是C++ STL中的关联容器,存储唯一值的有序集合,通常基于红黑树实现。
  9. 「求交集、并集、对称差积的自带函数:」 C++ STL提供了用于集合操作的算法函数,包括set_intersection、set_union、set_symmetric_difference等,用于求两个集合的交集、并集、对称差积。
  10. 「Stack:」 Stack是C++ STL中的容器适配器,实现了后进先出(LIFO)的操作,通常基于deque实现。
  11. 「区间查询:」 区间查询是一类数据结构和算法,包括树状数组、ST算法、滚动实现ST、线段树等,用于处理区间查询和更新操作。
  • 「树状数组:」 一种用于高效计算前缀和的数据结构,支持单点更新和区间查询。
  • 「ST算法:」 通过预处理得到每个区间内的最值,用于高效查询区间最值。
  • 「滚动实现ST:」 对ST算法的一种优化,通过滚动更新方式减小计算复杂度。
  • 「线段树:」 一种用于高效处理区间查询和更新的数据结构,通常用于解决一维和二维区间问题。

博弈论

  1. 「巴什博奕:」 巴什博奕是一种经典的博弈问题,两个玩家轮流从一堆物品中取若干个,每次可以取1至m个,最后取光者获胜,通过分析得到取胜策略。
  2. 「威佐夫博弈:」 威佐夫博弈是一种博弈问题,两个玩家轮流从两堆物品中取若干个,每次可以取相同数量,最后取光者获胜,通过数学方法得到取胜策略。
  3. 「斐波那契博弈:」 斐波那契博弈是一种博弈问题,两个玩家轮流从一堆物品中取若干个,每次可以取斐波那契数个,最后取光者获胜,通过分析得到取胜策略。
  4. 「尼姆博弈:」 尼姆博弈是一种经典的博弈问题,有若干堆物品,两个玩家轮流取若干个,每次可以取一堆的任意数量,最后取光者获胜,通过异或运算得到取胜策略。
  5. 「组合博弈:」 组合博弈是一类博弈问题,通过多个独立的博弈状态的组合,推导出整个博弈的胜负情况,常用于解决一些复杂的博弈问题。
  6. 「Sg 定理:」 Sg(Sprague-Grundy)定理是一种数学定理,用于分析组合游戏的必胜态和必败态,通过计算游戏状态的Grundy数。
  7. 「Sg 模板:」 Sg(Sprague-Grundy)模板是通过计算每个局面的Grundy数,从而判断整个博弈的胜负情况,通常使用深度优先搜索(DFS)实现。

图论

  1. 「二叉树层次遍历:」 通过广度优先搜索(BFS)实现,按层次遍历二叉树的节点,逐层访问。
  2. 「二叉树递归遍历:」 通过深度优先搜索(DFS)实现,递归遍历二叉树的节点,包括先序、中序和后序遍历。
  3. 「求连通块的方法及相关题目:」 通过深度优先搜索(DFS)或广度优先搜索(BFS)实现,找出图中的所有连通块,常用于解决图的连通性问题。
  4. 「欧拉回路:」 欧拉回路是指通过图中每条边一次且仅一次,最后回到起点的路径。通过深度优先搜索(DFS)实现,通常用于解决图的遍历问题。
  5. 「最小生成树:」 通过Prim算法或Kruskal算法实现,找出连通图中权重和最小的生成树,常用于解决网络布线和城市规划问题。
  6. 「克鲁斯卡尔算法:」 通过贪心策略,按边权递增的顺序选择边,构建最小生成树。
  7. 「最短路:」 通过Dijkstra算法或Bellman-Ford算法实现,找出图中两点之间最短路径,常用于解决路径规划问题。
  8. 「拓扑排序:」 通过深度优先搜索(DFS)或广度优先搜索(BFS)实现,找出有向无环图中节点的一种线性序列,用于表示事件的发生顺序。
  9. 「第 k 短路:」 通过最短路算法的变种实现,找出图中第 k 短的路径。
  10. 「最近公共祖先:」 通过Tarjan算法或倍增法实现,找出有根树或森林中两个节点的最近公共祖先。
  11. 「最大匹配:」 通过匈牙利算法实现,找出二分图中边数最大的匹配。
  12. 「强连通:」 通过Kosaraju算法或Tarjan算法实现,找出有向图中的所有强连通分量。
  13. 「双连通分量:」 通过割点和桥的概念实现,找出无向图中的双连通分量。
  14. 「割点和桥:」 通过DFS实现,找出无向图中的割点和桥。
  15. 「主席树:」 通过线段树的变种实现,支持区间修改和区间查询。
  16. 「树的同构:」 通过哈希或DFS实现,判断两棵树是否同构。
  17. 「最大团问题:」 通过图论算法实现,找出无向图中的最大完全子图。
  18. 「费用流:」 通过网络流算法实现,找出网络中的最小费用最大流。
  19. 「2-sat 问题:」 通过拓扑排序和缩点实现,判断一个布尔公式是否可满足。
  20. 「二分图最大匹配:」 通过匈牙利算法实现,找出二分图中边数最大的匹配。
  21. 「二分图最佳完美匹配:」 通过带权匈牙利算法实现,找出二分图中边权和最大的完美匹配。
  22. 「稳定婚姻:」 通过稳定婚姻算法实现,找出一个稳定的婚姻匹配方案。

几何专题

  1. 「几何模板:」 提供了一系列几何学基本操作和算法,包括点、线、面的表示与计算,以及几何问题的解决方法。
  2. 「极角排序:」 通过计算点相对于参考点的极角,实现对点集的极角排序,通常用于解决凸包等几何问题。
  3. 「凸包:」 通过Graham扫描法或Jarvis算法实现,找出给定点集的最小凸多边形,通常用于解决点集的包围问题。
  4. 「求凸包周长:」 通过遍历凸包的边,计算其长度之和,得到凸包的周长。
  5. 「回溯法:」 回溯法是一种穷举搜索的算法,通过递归实现,通常用于解决组合优化、排列组合等问题。
  6. 「八皇后问题:」 八皇后问题是回溯法的典型应用,通过递归搜索所有可能的放置方式,找出八个皇后不相互攻击的摆放方案。
  7. 「打印两点之间全部路径:」 通过深度优先搜索(DFS)实现,找出两点之间的所有路径,并输出。
  8. 「Cdq 分治:」 Cdq分治是一种高效解决一维偏序问题的算法,通常用于解决一些复杂的计算几何问题。
  9. 「Kd-tree:」 Kd-tree是一种空间划分树,通过递归地对k维空间进行划分,用于高效地进行范围查询。
  10. 「DLX 舞蹈链算法:」 舞蹈链是一种实现精确覆盖问题的数据结构,通常用于解决数独等问题。
  11. 「回文树:」 回文树是一种用于处理回文串的数据结构,通过动态维护回文串的信息,用于解决回文串相关的问题。
  12. 「动态树:」 动态树是一种支持树上路径操作的数据结构,通过维护轻链和重链实现动态修改。
目录
相关文章
|
2月前
|
机器学习/深度学习 数据采集 搜索推荐
Paper Digest | 突破个性化推荐数据稀疏性:长尾增强的图对比学习算法研究
本文提出了一种新的长尾增强的图对比学习方法(LAGCL),该方法促使模型同时兼顾头部节点与尾部节点之间的知识,并通过长尾增强技术来使模型产出更均匀更准确的节点表征,从而改进基于 GNN 的推荐任务。
|
2月前
|
算法 安全 Java
非启发式算法——中国剩余定理
非启发式算法——中国剩余定理
48 0
|
2月前
|
算法 网络协议 Linux
【Cisco Packet Tracer】交换机的自学习算法
【Cisco Packet Tracer】交换机的自学习算法
53 0
|
3月前
|
机器学习/深度学习 算法
机器学习 - [集成学习]Bagging算法的编程实现
机器学习 - [集成学习]Bagging算法的编程实现
32 1
|
8天前
|
机器学习/深度学习 算法 前端开发
Scikit-learn进阶:探索集成学习算法
【4月更文挑战第17天】本文介绍了Scikit-learn中的集成学习算法,包括Bagging(如RandomForest)、Boosting(AdaBoost、GradientBoosting)和Stacking。通过结合多个学习器,集成学习能提高模型性能,减少偏差和方差。文中展示了如何使用Scikit-learn实现这些算法,并提供示例代码,帮助读者理解和应用集成学习提升模型预测准确性。
|
8天前
|
机器学习/深度学习 算法 Python
使用Python实现集成学习算法:Bagging与Boosting
使用Python实现集成学习算法:Bagging与Boosting
18 0
|
15天前
|
算法
【算法学习--字符串】(不含KMP算法)
【算法学习--字符串】(不含KMP算法)
|
1月前
|
Rust Dart 算法
55.3k star!开源算法教程,附带动画图解,学习算法不再苦恼!
55.3k star!开源算法教程,附带动画图解,学习算法不再苦恼!
|
1月前
|
算法 C++ 计算机视觉
Opencv(C++)学习系列---Laplacian拉普拉斯边缘检测算法
Opencv(C++)学习系列---Laplacian拉普拉斯边缘检测算法
|
1月前
|
算法 C++ 计算机视觉
Opencv(C++)学习系列---Canny边缘检测算法
Opencv(C++)学习系列---Canny边缘检测算法