快速幂 题目： 50. Pow(x, n) 372. 超级次方 1922. 统计好数字的数目 快速幂快速幂（二进制取幂，平方法），可以在$O(logN)$的时间复杂度内计算出$a^{n}$。 原理：n有$\left \lfloor log_{2} \ n \right \rfloor + 1$个二进制位，所以只用计算$O(logn)$次乘法就可以计算出$a^{n}$。 以计算$3^{13}$为例： $3 2024-02-12 算法与数据结构 算法 位运算 二进制 数学知识 幂 组合数
质数 质数（素数）是指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数。 大于1的自然数若不是质数，则称为合数。 题目： 204. 计数质数 判断一个数是否是质数1.朴素枚举法public boolean isPrime(int x) { for (int i = 2; i * i <= x; i++) { // x % i (i > sqrt(x)) 2024-02-12 算法与数据结构 算法 数学知识 质数 素数筛
约数和因数 GCD：最大公约数时间复杂度：$O(logN)$ int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 6015. 统计可以被 K 整除的下标对数目 $x*y \% k = 0$，已知$x和k$，那么$y$必须满足为$\frac{k}{gcd(k, x)}$的倍数 最小公倍数：LCMint lcm(in 2024-02-12 算法与数据结构 算法 数学知识 最大公约数 质因数分解
区间问题 56. 合并区间 57. 插入区间 2276. 统计区间中的整数数目 715. Range 模块 动态增添区间和删除区间 class RangeModule { // 保存区间的左右端点 TreeMap<Integer, Integer> map = new TreeMap<>(); public RangeModule() { 2024-02-12 算法与数据结构 算法 数据结构 二分 TreeMap 区间
线性DP 线性DP问题是指递推方程有明显的线性关系，有一维线性和二维线性。 题目： 120. 三角形最小路径和 剑指 Offer II 095. 最长公共子序列 931. 下降路径最小和 1289. 下降路径最小和 II 2024-02-12 算法与数据结构 算法 数据结构 动态规划 线性DP
背包DP 0-1背包218. 01背包问题 322. 零钱兑换 518. 零钱兑换 II 面试题 08.11. 硬币 剑指 Offer II 103. 最少的硬币数目 剑指 Offer II 104. 排列的数目 背包容量为$W$，物品数量为$n$，每个物品的重量为$w{i}$，价值为$v{i}$。 每个物品都只有一件，求背包能装下的最大价值？ 状态定义$dp[i][j]$：从前$i$个物品中选出总重量不 2024-02-12 算法与数据结构 算法 数据结构 动态规划 背包DP
BFS与DFS 面试题 17.22. 单词转换 面试题 17.07. 婴儿名字 1263. 推箱子 方向向量1.四方向int[] dx = {-1, 1, 0, 0}; int[] dy = {0, 0, -1, 1}; 2.八方向// 上 下 左 右 左上 右上 左下 右下 int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1}; 2024-02-12 算法与数据结构 数据结构 图论 深度优先搜索 广度优先搜索
二分图 二分图https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E5%9B%BE 在图论中，二分图是一类特殊的图，又称为二部图、偶图、双分图。二分图的顶点可以分成两个互斥的独立集 U 和 V 的图，使得所有边都是连结一个 U 中的点和一个 V 中的点。顶点集 U、V 被称为是图的两个部分。等价的，二分图可以被定义成图中所有的环都有偶数个顶点。 题目： 剑指 2024-02-12 算法与数据结构 算法 数据结构 图论 邻接矩阵 二分图 DFS
拓扑排序 题目： 802. 找到最终的安全状态 210. 课程表 II 5909. 并行课程 III 851. 喧闹和富有 剑指 Offer II 115. 重建序列 剑指 Offer II 114. 外星文字典 1.Kahn算法（卡恩算法）(BFS)卡恩于1962年提出了该算法。简单来说，假设L是存放结果的列表，先找到那些「入度为零」的节点，把这些节点放到L中，因为这些节点没有任何的父节点。然后把与这些节 2024-02-12 算法与数据结构 图论 DFS 邻接表 BFS 拓扑排序 环
最短路径算法 算法 时间复杂度 有向图/无向图 边权（正/负） 单源/多源 Dijkstra 朴素：$O(N^{2})$ 队列优化：$O(NlogN)$ 有向图、无向图 正 单源 Floyd-Warshall $O(N^{3})$ 有向图、无向图 正、负 多源 Bellman-Ford $O( V \ E )$ 有向图 正、负 单源 SPFA 最坏：$O( V \ E )$ 有向图 2024-02-12 算法与数据结构 数据结构 图论 邻接矩阵 邻接表 Dijkstra 最短路径 Floyd-Warshall Bellman-Ford
