算法题类型

1. 排序与查找

排序问题：将一组数据按照特定顺序（通常是升序或降序）排列。
- 基础排序：简单直观，适用于小规模数据。
  - 冒泡排序：通过不断交换相邻元素进行排序。（稳定排序）
  - 选择排序：每次选择未排序部分的最小元素放到已排序部分的末尾。（不稳定排序）
  - 插入排序：将每个元素插入到已排序部分的正确位置。（稳定排序）
- 高级排序：效率较高，适用于大规模数据。
  - 快速排序：通过分治法和基准元素进行排序。（不稳定排序）
  - 归并排序：通过分治法将数据分成小份排序，然后合并。（稳定排序）
  - 堆排序：利用堆这种数据结构进行排序。（不稳定排序）
- 线性排序：时间复杂度为O(n)，适用于特定类型的数据。
  - 计数排序：适用于数据范围较小的整数。（稳定排序）
  - 桶排序：将数据分到不同的桶中，然后分别排序。（稳定排序）
  - 基数排序：按位进行排序，适用于整数或字符串。（稳定排序）
- 特殊排序：针对特定场景的排序算法。
  - 外部排序：用于处理无法一次性加载到内存的数据。
查找问题：在数据集中寻找特定元素。
- 线性查找：逐个遍历数据，直到找到目标元素。（时间复杂度O(n)）
- 二分查找：在已排序数据中，通过不断缩小搜索范围来查找目标元素。（时间复杂度O(log n)）
- 二分查找变种：查找第一个大于等于目标值的元素、查找最后一个小于等于目标值的元素等。
- 矩阵中的目标值查找：在二维数组中查找目标元素。

2. 数学与数论

基础数学：
- 素数判断：判断一个数是否为素数（只能被1和自身整除的数）。
  - 试除法：通过尝试除以小于等于其平方根的所有整数来判断。（时间复杂度O(sqrt(n))）
  - 埃拉托斯特尼筛法：一种高效的筛选素数的方法。（时间复杂度O(n log log n)）
- 最大公约数与最小公倍数：
  - 欧几里得算法：用于计算两个整数的最大公约数。（时间复杂度O(log(a, b))）
- 快速幂：高效计算大整数的幂。（时间复杂度O(log n)）
- 二进制转换：
  - 二进制转十进制
  - 十进制转二进制
数论：研究整数性质的数学分支。
- 同余问题：
  - 线性同余方程：求解形如ax ≡ b (mod m)的方程。
  - 模运算：求一个数除以另一个数的余数。
- 数论函数：定义在整数集合上的函数。
  - 欧拉函数：计算小于等于n且与n互质的正整数个数。
  - 莫比乌斯函数：一个数论函数，用于解决一些组合数学问题。
- 中国剩余定理：求解同余方程组。
- 矩阵快速幂：用于快速计算矩阵的幂。
组合数学：研究组合问题的数学分支。
- 组合数与杨辉三角：
  - 组合数：从n个元素中选择k个元素的方案数。
  - 杨辉三角：一个数表，用于计算组合数。
- 卡特兰数：一个出现在各种组合问题中的数列。

3. 动态规划 (Dynamic Programming, DP)

经典DP问题：
- 斐波那契数列：一个递归定义的数列，每个数是前两个数之和。（时间复杂度O(n)）
- 背包问题：
  - 0/1背包：每个物品只能选择一次。（时间复杂度O(n*capacity)）
  - 完全背包：每个物品可以选择多次。（时间复杂度O(n*capacity)）
  - 多重背包：每个物品有有限个。（时间复杂度O(n_capacity_count)）
- 最长公共子序列（LCS）：两个序列的最长公共子序列。（时间复杂度O(m*n)）
- 最长递增子序列（LIS）：一个序列的最长递增子序列。（时间复杂度O(n log n)）
- 硬币换零钱问题：用最少的硬币凑出指定金额。（时间复杂度O(amount*n)）
- 矩阵链乘法：找到矩阵相乘的最佳顺序，使得运算次数最少。（时间复杂度O(n^3)）
其他DP问题：
- 编辑距离问题：将一个字符串转换为另一个字符串所需的最少操作次数。（时间复杂度O(m*n)）
- 打家劫舍问题：在不能偷窃相邻房屋的情况下，偷窃最多金额。（时间复杂度O(n)）
- 状态压缩DP：使用位运算来表示状态的动态规划。
- 数位DP：用于解决与数字位数有关的动态规划问题。

4. 贪心算法

经典贪心问题：
- 活动选择问题：选择最多的不重叠活动。（时间复杂度O(n log n)）
- 区间调度问题：选择最多的非重叠时间区间。（时间复杂度O(n log n)）
- 零钱兑换问题：用最少的硬币凑出指定金额。（不一定能找到最优解）
其他贪心问题：
- 最小生成树：找到连接所有顶点的最小权值边的集合。
  - Prim算法（时间复杂度O(n^2)）
  - Kruskal算法（时间复杂度O(m log n)）
- 霍夫曼编码：用于数据压缩的编码方式。（时间复杂度O(n log n)）
- 分数背包问题：允许选择物品的一部分。（时间复杂度O(n log n)）
- Huffman树：一种用于霍夫曼编码的树结构。

5. 回溯法 (Backtracking)

经典回溯问题：
- 八皇后问题：在棋盘上放置八个皇后，使其互不攻击。（时间复杂度较高）
- N皇后问题：八皇后问题的推广。（时间复杂度较高）
- 全排列与组合：生成集合的所有排列和组合。（时间复杂度较高）
- 数独问题：填充数独游戏。（时间复杂度较高）
其他回溯问题：
- 矩阵路径问题：在矩阵中寻找满足条件的路径。（时间复杂度较高）
- 子集和问题：找到一个集合的子集，其元素之和等于目标值。（时间复杂度较高）

6. 分治法 (Divide and Conquer)

经典分治问题：
- 排序问题：
  - 归并排序（时间复杂度O(n log n)）
  - 快速排序（平均时间复杂度O(n log n)，最坏时间复杂度O(n^2)）
- 逆序对计数：计算数组中的逆序对数。（时间复杂度O(n log n)）
- 最大子数组和问题：找到数组中和最大的连续子数组。（时间复杂度O(n)）
其他分治问题：
- 矩阵乘法：
  - Strassen算法（时间复杂度O(n^log2(7))）

7. 图论 (Graph Theory)

图的遍历：
- 深度优先搜索（DFS）：沿着图的深度方向遍历。（时间复杂度O(V+E)）
- 广度优先搜索（BFS）：沿着图的宽度方向遍历。（时间复杂度O(V+E)）
最短路径问题：
- Dijkstra算法：用于计算非负权图的单源最短路径。（时间复杂度O(E log V)）
- Bellman-Ford算法：用于计算可以包含负权边的图的单源最短路径。（时间复杂度O(V*E)）
- Floyd-Warshall 算法：用于计算任意两点之间的最短路径。（时间复杂度O(V^3)）
最小生成树问题：
- Prim 算法（时间复杂度O(E log V)）
- Kruskal 算法（时间复杂度O(E log V)）
其他图论问题：
- 拓扑排序：对有向无环图进行排序，使得所有边都指向后面的顶点。（时间复杂度O(V+E)）
- 强连通分量：找到图中互相可达的顶点集合。（时间复杂度O(V+E)）
- 图的二分性判断：判断一个图是否为二分图。（时间复杂度O(V+E)）
- 网络流：研究网络中流量的分配问题。
- 二分图匹配：找到二分图中最大的匹配数。

8. 位运算

位运算技巧：直接对二进制位进行操作，效率高。
- 判断是否为 2 的幂：n & (n - 1) == 0
- 统计二进制中 1 的个数：Hamming Weight
- 交换两个数的值：a ^= b; b ^= a; a ^= b;
- 找出只出现一次的数字：利用异或运算的性质
- 计算二进制补码
位运算应用：
- 状态压缩：用二进制位表示状态
- 快速幂：利用位运算优化幂运算

9. 树与二叉树

二叉树的遍历：
- 前序、中序、后序遍历：递归或迭代方式访问所有节点
- 层次遍历：逐层访问节点
二叉树的性质：
- 判断是否为二叉搜索树：中序遍历结果为升序
- 二叉树的最大深度：递归或迭代方式求解
- 路径和问题：寻找满足条件的路径
其他树结构：
- 平衡二叉搜索树：
  - AVL 树：保持左右子树高度差不超过 1
  - 红黑树：一种自平衡的二叉搜索树
- 线段树：用于处理区间查询问题
- 字典树：用于存储和查找字符串