算法学习路径

一.基础必会

1.基础排序

冒泡排序

是比较相邻元素，如果顺序错误就把它们交换过来。重复此步骤，直到整个数组有序，时间复杂度为 \(O(n^2)\)。它是一种稳定的排序算法，代码实现简单。

选择排序

选择排序是在未排序序列中找到最小（大）元素，和起始位置的元素进行交换。然后，然后就转换成了一个 \(n - 1\) 个元素的问题，继续同样的方法。时间复杂度为 \(O(n^2)\)，不稳定。

插入排序

插入排序是将未排序数据插入到已排序序列的合适位置。对于小规模数据，插入排序效率较高，时间复杂度为 \(O(n^2)\)。它是稳定的排序算法，适合部分有序的数据。

计数排序

计数排序是一种非比较排序算法，通过统计每个元素出现的次数来排序。时间复杂度为 \(O(n + k)\)，其中 \(k\) 是数据的范围。适用于数据范围较小且整数数据的排序。

接口调用（sort函数）

很多编程语言都提供了内置的排序函数，如C++ 以及 Python 中的sort函数。使用方便，效率较高，通常采用优化的排序算法。可以自定义比较函数，实现不同的排序规则。

比较函数实现

在自定义排序中，需要实现比较函数来确定元素的顺序。比较函数返回布尔值，用于判断两个元素的大小关系。不同的比较函数可以实现升序、降序等不同的排序效果。

结构体排序

当需要对结构体数组进行排序时，要根据结构体的某个或多个成员进行排序。可以通过自定义比较函数来实现结构体的排序。结构体排序在处理复杂数据时非常有用。

2.基础数据结构

顺序表（数组）

数组是一种连续存储的数据结构，通过下标可以快速访问元素。可以存储相同类型的数据，支持随机访问，时间复杂度为 \(O(1)\)。数组的大小在创建时确定，不便于动态扩展。

单链表

单链表由节点组成，每个节点包含数据和指向下一个节点的指针。插入和删除操作效率较高，时间复杂度为 \(O(1)\)，但随机访问效率低。适合频繁插入和删除元素的场景。

双链表

双链表的节点除了包含数据和指向下一个节点的指针，还包含指向前一个节点的指针。可以双向遍历，插入和删除操作更加灵活。相比单链表，双链表占用更多的存储空间。

栈

栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。常见的应用有函数调用栈、表达式求值等。可以用数组或链表来实现栈。

队列

队列是一种先进先出（FIFO）的数据结构，只能在队尾插入元素，在队头删除元素。常用于任务调度、广度优先搜索等场景。可以用数组或链表来实现队列。

二叉树

二叉树是每个节点最多有两个子节点的树结构。常见的二叉树有二叉搜索树、完全二叉树、满二叉树等。二叉树的遍历方式有前序、中序、后序和层序遍历。

3.基本搜索算法

深度优先搜索dfs

深度优先搜索是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。使用递归或栈来实现，适合寻找所有可能的解。在搜索过程中可能会陷入无限递归，需要注意边界条件。

广度优先搜索bfs

广度优先搜索是逐层遍历树的节点，先访问离根节点最近的节点。使用队列来实现，适合寻找最短路径。空间复杂度较高，需要存储大量的节点信息。

4.基础动态规划

线性DP

线性DP是指状态转移方程只与前一个或几个状态有关的动态规划问题。通常可以用一维数组来存储状态，如最长上升子序列问题。关键是找出状态转移方程和边界条件。

记忆化搜索

记忆化搜索是在递归的基础上，使用数组记录已经计算过的结果，避免重复计算。结合了递归和动态规划的优点，适用于状态转移复杂的问题。思考起来更加直观

最大连续子序列

最大连续子序列是指在一个序列中，找到连续的一段子序列，使其和最大。可以用动态规划的思想解决，时间复杂度为O(n)。关键是定义状态和状态转移方程

最长单调子序列

最长单调子序列是指在一个序列中，找到最长的单调递增或递减子序列。可以用动态规划或二分查找来解决，时间复杂度分别为O(n²)和O(nlogn)。在实际应用中，二分查找的方法效率更高。

最长公共子序列

最长公共子序列是指在两个序列中，找到最长的公共子序列。可以用二维动态规划来解决，时间复杂度为O(m * n)，其中m和n分别是两个序列的长度，状态转移方程的推导是关键。

二维DP、多维DP

二维DP和多维DP是指状态需要用二维或多维数组来表示的动态规划问题。适用于处理多个变量的优化问题，如背包问题的变种。状态的定义和状态转移方程的推导更加复杂。一般当低维问题无法解决的时候，可以尝试扩展维度。

5.初高中基础数学知识

加减乘除

加减乘除是最基本的数学运算，在编程中经常使用。需要注意数据类型的选择，避免溢出和精度问题。可以通过运算符重载等方式实现自定义的运算。

取模

取模运算是求两个数相除的余数，常用于处理循环和周期性问题。取模运算满足一些基本的性质，如((a + b) % m = (a % m + b % m) % m）。

整除

整除是指一个数能被另一个数整除，没有余数。可以用取模运算来判断是否整除，如(a % b == 0)表示(a)能被(b)整除。

取整（上下整）

取整是将一个实数转换为整数的过程，分为上取整和下取整。上取整是将小数部分进位，下取整是舍去小数部分。在不同的编程语言中，取整函数的实现可能不同。

解方程

解方程是求方程的解的过程，常见的方程有一元一次方程、一元二次方程等。可以用代数方法或数值方法来解方程，如二分法、牛顿迭代法。

指数

指数是表示一个数自乘若干次的形式，如(a^n)表示(a)的(n)次方。指数运算满足一些基本的性质，如(a^m * a^n = a^{(m + n)})。在算法中，指数运算可能会导致结果过大，需要注意处理。

对数

对数是指数的逆运算，如(log_a(b))表示以(a)为底(b)的对数。对数运算满足一些基本的性质，如(log_a(mn) = log_a(m) + log_a(n))。

三角函数

三角函数是数学中常见的函数，如正弦、余弦、正切等。三角函数在几何、物理等领域有广泛的应用。在编程中，需要注意三角函数的参数是弧度制。

二.高难进阶

1.基础优化算法

贪心

贪心算法是在每一步选择中都采取当前状态下最优的选择，希望通过局部最优达到全局最优。贪心算法的关键是证明贪心策略的正确性，并非所有问题都适合贪心算法。常见的应用有活动选择问题、哈夫曼编码等。

哈希

哈希算法是将元素存储到一个特殊容器中，这个容器可以快速插入和查找，一般时间复杂度为 (O(1))，经典的“梦开始的地方——两数之和”，就可以采用哈希表快速进行统计。

前缀和+差分

前缀和是指一个数组中，从第一个元素到第 (i) 个元素的和。差分是前缀和的逆运算，用于快速查询区间元素的值。前缀和和差分可以将区间查询的时间复杂度从 (O(n)) 降低到 (O(1))。

双指针

双指针是指使用两个指针在数组或链表上移动，以解决一些特定的问题。可以分为同向双指针和相向双指针，常用于查找子数组、判断链表是否有环等。双指针可以降低时间复杂度，提高算法效率。

滑动窗口

滑动窗口是一种特殊的双指针技术，通过维护一个固定大小的窗口在数组或字符串上移动。可以用于解决一些连续子数组或子字符串的问题，如最大子数组和。滑动窗口的关键是确定窗口的大小和移动规则。

二分

二分查找是在有序数组中查找某个元素的高效算法，时间复杂度为 (O(log n))。二分查找的关键是确定查找区间和中间位置，不断缩小查找范围。二分查找可以应用于很多问题，如查找最小值、最大值等。

2.高阶数据结构

哈希表 

哈希表是基于哈希函数实现的数据结构，用于快速存储和查找数据。哈希表的插入、查找和删除操作的平均时间复杂度为 (O(1))。哈希表的性能取决于哈希函数和解决冲突的方法。

字符串hash

字符串hash是将字符串映射为一个整数的过程，用于快速判断两个字符串是否相等。常见的字符串hash方法有BKDRHash、DJBHash等。字符串hash可以提高字符串匹配的效率。

堆

堆是一种完全二叉树，分为最大堆和最小堆。最大堆的每个节点的值都大于或等于其子节点的值，最小堆反之。堆可以用于实现优先队列，支持插入和删除操作，时间复杂度为 (O(log n))。

并查集

并查集是一种用于处理不相交集合的合并与查询问题的数据结构。主要操作有查找和合并，时间复杂度接近 (O(1))。并查集常用于解决连通性问题，如判断图的连通分量。

树状数组

树状数组是一种用于高效处理区间查询和单点修改问题的数据结构。可以在 (O(log n)) 的时间复杂度内完成区间和的查询和单点的修改。树状数组的实现基于二进制的思想。

ST表

ST表是一种用于高效处理静态区间最值查询问题的数据结构。预处理时间复杂度为 (O(nlog n))，查询时间复杂度为 (O(1))。ST表的核心是利用动态规划的思想进行预处理。

线段树

线段树是一种二叉树，用于高效处理区间查询和区间修改问题。可以在 (O(log n)) 的时间复杂度内完成区间和、区间最值等查询和区间修改操作。线段树的实现较为复杂，需要注意节点的更新和合并。

字典树

字典树是一种树形数据结构，用于高效存储和检索字符串集合。可以在 (O(m)) 的时间复杂度内完成字符串的插入、查找和删除操作，其中 (m) 是字符串的长度。字典树常用于字符串的前缀匹配和自动补全。

3.进阶动态规划

01背包

01背包是指选择若干物品放入背包，使背包中物品的价值最大。每个物品只能选择放入或不放入背包，。可以用二维数组或一维数组来实现，时间复杂度为 (O(n * m))，其中 (n) 是物品的数量，(m) 是背包的容量。

完全背包

完全背包与01背包类似，但每个物品可以选择无限次放入背包。状态转移方程与01背包有所不同，需要注意循环的顺序。同样可以用二维数组或一维数组来实现，时间复杂度为 (O(n * m))。

多重背包

多重背包是指每个物品有一定的数量限制，在一定的容量限制下选择物品使价值最大。可以通过二进制拆分将多重背包转化为01背包问题。时间复杂度为 (O(n * m * log k))，其中 (k) 是物品的最大数量。

分组背包

分组背包是指将物品分成若干组，每组中只能选择一个物品放入背包。状态转移方程需要考虑组内物品的选择，时间复杂度为 (O(n * m * g))，其中 (g) 是组数。分组背包可以用于解决一些资源分配问题。

树上分组背包

树上分组背包是在树结构上进行分组背包的问题。需要结合树的遍历和分组背包的思想，状态转移更加复杂。常用于处理树形结构的资源分配问题。

基础树形DP

基础树形DP是在树结构上进行动态规划的问题。通常需要利用树的递归性质，从子节点的状态推导出父节点的状态。常见的应用有树的最大独立集、树的最小支配集等。

树的重心

树的重心是指树中的一个节点，使得删除该节点后，剩余的各个子树的节点数的最大值最小。可以用树形DP来求解树的重心，时间复杂度为 (O(n))。树的重心在树的结构分析中有重要应用。

区间DP

区间DP是指在区间上进行动态规划的问题，通常需要枚举区间的长度和起点。状态转移方程通常与区间的合并有关，时间复杂度为 (O(n^3))。常见的应用有矩阵链乘法、石子合并等。

数位DP

数位DP是指在数字的每一位上进行动态规划的问题，常用于处理数字计数问题。需要考虑数字的范围和限制条件，状态转移方程较为复杂。可以通过记忆化搜索或递推的方式实现，时间复杂度与数字的位数有关。

状压DP

状压DP是指将原本多维度的状态，压缩成更少的维度，比如将这个状态 [2][2][2][2] 变成 [16] 的问题，状态数不变，但是可以利用位运算优化状态转移的过程。

4.图论

最短路

（1）Dijkstra

（2）Bellman-Ford

（3）Floyed

（4）SPFA

（5）Dijkstra + Heap

最小生成树

（1）prim

（2）kruskal

最近公共祖先

5.高等数学知识

初等数论

整除、素数、素数筛选、最大公约数、最小公倍数、因子数、因子和、因数分解、二分快速幂、线性同余、逆元、欧拉函数、欧拉定理、中国剩余定理、威尔逊定理、卢卡斯定理、整数分块等等。

容斥原理

容斥原理是用于计算多个集合的并集的元素个数的原理。可以通过枚举集合的组合来计算并集的元素个数。容斥原理在组合数学和算法中有广泛的应用。

二项式定理

二项式定理是指 ((a + b)^n = sum C(n, k) * a^{(n - k)} * b^k)，其中 (C(n, k)) 是组合数。可以用二项式定理来展开多项式。二项式定理在组合数学和算法中有重要应用。