-
约数
判断一个数的所有约数求一个数的约数个数求一个数的约数之和求两个数最大公约数求两个数最小公倍数AcWing 869. 试除法求约数 原题链接给定n个正整数aiai，对于每个整数aiai,请你按照从小到大的顺序输出它的所有约数。输入格式第一行包含整数n。接下来n行，每行包含一个整数aiai。输出格式输出共n行，其中第 i 行输出第 i 个整数aiai的所有约数。数据范围1≤n≤1001≤n≤100,2≤ai≤2∗1092≤ai≤2∗109输入样例：268输出样例：1 2 3 6 1 2 4...…
-
快速幂
快速幂乘法逆元 乘法逆元的定义若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b−1(mod m)。b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，bm−2即为b的乘法逆元。AcWing 875. 快速幂 原题链接给定nn组ai,bi,piai,bi,pi，对于每组数据，求出abii mod piaibi mod pi的值。输入格式第一行包含整数nn。接下来nn行，每行包含三个整数...…
-
拓扑排序
拓扑排序思想利用图的BFS思想来处理 事件A依赖于事件B，则添加一条A指向B的边 将所有入度为0的点加入到队列 从队列中弹出一个点，表示这个任务已经完成，遍历这个点指向了哪些点，将这些点的入度-1，如果有点的入度减至为0则入队 最后结果数组中的点的个数要等于所有点的个数，否则这个图没有拓扑排序关键数据结构indegree[]：用来保存每个点的入度情况AcWing 848. 有向图的拓扑序列 原题链接注意，有自环的有向图没有拓扑排序给定一个n个点m条边的有向图，点的编号是1到n，...…
-
图论题一般算法总结
最短路算法总结最小生成树问题Prim算法稠密图Kruskal算法稀疏图二分图问题染色法判定一个图是否是二分图最大匹配问题匈牙利算法求二分图的最大匹配…
-
二分图的最大匹配
匈牙利算法算法思路每次匹配的时候去访问已经匹配好的是否可以做出让步AcWing 861. 二分图的最大匹配 原题链接给定一个二分图，其中左半部包含n1n1个点（编号1~n1n1），右半部包含n2n2个点（编号1~n2n2），二分图共包含m条边。数据保证任意一条边的两个端点都不可能在同一部分中。请你求出二分图的最大匹配数。 二分图的匹配：给定一个二分图G，在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点，则称M是一个匹配。 二分图的最大匹配：所有匹配中包含边数最多...…
-
二分图的判定
二分图一个图是二分图，当且仅当图中不含奇数环（环中边数为奇数）可以将图划分到两个集合，只存在集合中的边，集合内部没有边染色法用dfs来染色，过程中不能出现颜色冲突要注意什么时候应该递归，否则会出现无限递归的情况并且这个图不一定联通，需要判断每个连通块是否是二分图AcWing 860. 染色法判定二分图 原题链接给定一个n个点m条边的无向图，图中可能存在重边和自环。请你判断这个图是否是二分图。输入格式第一行包含两个整数n和m。接下来m行，每行包含两个整数u和v，表示点u和点v之间存在一条...…
-
SPFA
SPFA形式上很像Dijkstra，是Bellman-ford算法的优化利用宽搜的方式来优化，定义一个队列queue,其中存的是变化过的点，如果一个点没有变化（即没有变小）就不会入队。可以利用这个算法来判断是否存在负环 维护一个count数组，记录边数，当count[i] >= n时，说明有n条边，经过了n + 1个点，所以存在负环AcWing 851. spfa求最短路 原题链接给定一个n个点m条边的有向图，图中可能存在重边和自环， 边权可能为负数。请你求出1号点到n号点的最...…
-
Prim
Prim适用于无向稠密图，可以存在负边不需要初始化dist[1] = 0，因为dist[i]表示点i到整个集合的距离，应该存这个点到集合最短边的值任选一点作为开始都行算法思路 dist[n] = Integer.MAX_VALUE / 2 进行n次迭代，找到没有在集合中（及已经确定的最小连通块）的距离最小的点t 用点t来更新其他点到集合的距离 st[t] = true,表示这个点已经确定了，并将t放入到集合中AcWing 858. Prim算法求最小生成树 原题链接给定一个n个...…
-
Kruskal
Kruskal适用于稀疏图算法思路 将所有的边排序 依次取出时判断这条边是否是冗余的（即加入这条边会有回路），利用并查集来实现AcWing 859. Kruskal算法求最小生成树 原题链接给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。 给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n= V ，m= ...…
-
Floyd
Floyd用来求多源汇最短路问题原理是动态规划，代码形式是三重循环关键数据结构dist[i][j]:代表从i到j最短路注意dist数组的初始化，dist[i][i] = 0AcWing 854. Floyd求最短路 原题链接给定一个n个点m条边的有向图，图中可能存在重边和自环，边权可能为负数。再给定k个询问，每个询问包含两个整数x和y，表示查询从点x到点y的最短距离，如果路径不存在，则输出“impossible”。数据保证图中不存在负权回路。输入格式第一行包含三个整数n，m，k接下来m...…
-
Dijkstra
Dijkstra朴素版Dijkstra适用于稠密图，用邻接矩阵来存储图对于重边只需要存储最小的那一条 将开始点的dist[0] = 0 others dist[n] = Integer.MAX_VALUE / 2 遍历所有点：找到未确定最短距离的点中距离最短的点 利用这个点更新与之相连的点到起点的最短路径关键数据结构st[]:表示第i个点已经确定了最短路，及要以这个点为基准来更新其他路径，而这个点的最短路已经确定。dist[]:表示第i个点到起点的最短路堆优化版Dijkstra适用于...…
-
DFS
DFSAcWing 842. 排列数字 原题链接给定一个整数n，将数字1~n排成一排，将会有很多种排列方法。现在，请你按照字典序将所有的排列方法输出。输入格式共一行，包含一个整数n。输出格式按字典序输出所有排列方案，每个方案占一行。数据范围1≤n≤71≤n≤7输入样例：3输出样例：1 2 31 3 22 1 32 3 13 1 23 2 1 static List<Integer> res = new ArrayList<>(); static boole...…
-
Bellman-Ford
Bellman-Ford 存储所有的边 如果有负权回路则答案可能是负无穷 可以用来判断负权回路是否存在，不过一般用SPFA来做 循环k次，表示不经过超过k条边 每次循环要进行备份，否则可能发生串联（即用更新后的结果更新下个点），在一次完整的更新过程中只能用原来的结果来迭代后面的结果 每次循环所有的边找最短的 要注意最后能否到达的判断，因为存在负权边所以可能使不可到达的距离不为Integer.MAX_VALUE / 2，所以我们使用>= Int...…
-
BFS
BFS需要自己写栈，当时可以用来求最短步数的问题，维护一个dist数组，表示遍历到的点到起始位置的距离AcWing 844. 走迷宫 原题链接给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路...…
-
离散化
离散化处理数据的值域很大，数量很少的问题我们需要将数据映射到 一定空间中如 a[] = 1, 3, 100, 2000, 500000，映射到 下标0, 1, 2, 3, 4 a[]中可能有重复数据 先排序后去重,java 中利用set 先去重再排序 如何算出a[i]离散化后的值 二分来做AcWing 802. 区间和 原题链接假定有一个无限长的数轴，数轴上每个坐标上的数都是0。现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。接下来，进行 m 次询问，每个询问包含两...…
-
快速排序
AcWing 785. 快速排序 原题链接给定你一个长度为n的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。输出格式输出共一行，包含 n 个整数，表示排好序的数列。数据范围1≤n≤1000001≤n≤100000输入样例：53 1 2 4 5输出样例：1 2 3 4 5private static void quickSort(in...…
-
归并排序
AcWing 787. 归并排序 原题链接给定你一个长度为n的整数数列。请你使用归并排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。输入格式输入共两行，第一行包含整数 n。第二行包含 n 个整数（所有整数均在1~109109范围内），表示整个数列。输出格式输出共一行，包含 n 个整数，表示排好序的数列。数据范围1≤n≤1000001≤n≤100000输入样例：53 1 2 4 5输出样例：1 2 3 4 5private static void mergeSort(in...…
-
并查集
并查集有何用？快速的 将两个集合合并 询问两个元素是否在 同一个集合之中原理 用树的形式来维护 集合 （不一定是二叉树） 根节点的编号就是 集合的编号，每一个节点都要存储 父节点是什么实现 判断树根：p[x] == x 求集合编号 find(int x) 方法 合并两个集合 p[x] = y、第2步有一个优化 路径压缩：将整个查找路径上的点 都 直接 指向 根节点方法find(int x): 返回 x 的 祖宗节点 + 路径压缩维护一些信息的并查集问题 维护每个集...…
-
堆
AcWing 838. 堆排序 原题链接输入一个长度为n的整数数列，从小到大输出前m小的数。输入格式第一行包含整数n和m。第二行包含n个整数，表示整数数列。输出格式共一行，包含m个整数，表示整数数列中前m小的数。数据范围1≤m≤n≤1051≤m≤n≤105，1≤数列中元素≤1091≤数列中元素≤109输入样例：5 34 5 1 3 2输出样例：1 2 3class Heap{ int[] heap; int size; public void creatHeapByA...…
-
双指针
双指针模板for(int i=0,j=0,i<n;i++){ while(j<i&&check(i,j)) j++;}AcWing 799. 最长连续不重复子序列 原题链接给定一个长度为n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。输入格式第一行包含整数n。第二行包含n个整数（均在0~100000范围内），表示整数序列。输出格式共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。数据范围1≤n≤1000001≤n≤100...…
