115 字
1 分钟
Java 常用算法模板备忘整理
归并排序
// 归并排序数组的[l, r)区间static void mergeSort(int[] arr, int l, int r) { if (r - l <= 1) return; // 一直拆分到只剩最后一个元素 int mid = l + (r - l) / 2; mergeSort(arr, l, mid); // 拆分左半边 mergeSort(arr, mid, r); // 拆分右半边 merge(arr, l, r); // 合并两边}static void merge(int[] arr, int l, int r) { int[] tmp = new int[r - l]; int mid = l + (r - l) / 2; int i = l, j = mid, k = 0; while (i < mid && j < r) { if (arr[i] < arr[j]) { tmp[k++] = arr[i++]; } else { tmp[k++] = arr[j++]; // 可选,累加逆序对数量 count += mid - i; // 左半边剩余元素与当前元素构成逆序对 } } // 补上剩余元素 while (i < mid) tmp[k++] = arr[i++]; while (j < r) tmp[k++] = arr[j++]; System.arraycopy(tmp, 0, arr, l, tmp.length);}质数筛
埃氏筛
boolean[] isPrime = new boolean[n + 1];Arrays.fill(isPrime, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } }}欧拉筛
boolean[] isPrime = new boolean[n + 1];int[] primes = new int[n];int count = 0;Arrays.fill(isPrime, true);isPrime[0] = isPrime[1] = false;for (int i = 2; i <= n; i++) { if (isPrime[i]) primes[count++] = i; for (int j = 0; j < count && i * primes[j] <= n; j++) { isPrime[i * primes[j]] = false; if (i % primes[j] == 0) break; }}快速幂
// 快速计算a^b % MODstatic long fastPow(long a, long b, long MOD) { long res = 1; while (b > 0) { if ((b & 1) == 1) { res = res * a % MOD; } a = a * a % MOD; b >>= 1; } return res;}费马小定理计算逆元
前提条件：MOD 为质数，且 a 不被 MOD 整除
a 在模下的逆元为 a^(MOD - 2) % MOD
// 直接除法取模 b/a%MOD 会丢失精度，除以a等价于乘a在模下的逆元 => b * a^(MOD-2) % MODstatic long calc(long a, long MOD) { return fastPow(a, MOD - 2, MOD); // 结果为逆元}最大公约数GCD和最小公倍数LCM
static long gcd(long a, long b) { if (b == 0) return a; return gcd(b, a % b);}static long lcm(long a, long b) { return a / gcd(a, b) * b; // 先除后乘防溢出}前缀和
int[] sum = new int[n + 1];for (int i = 0; i < n; i++) { sum[i + 1] = sum[i] + arr[i];}// 求区间 [l, r] 的和int rangeSum = sum[r] - sum[l - 1];差分
int[] diff = new int[n + 1];diff[0] = arr[0];// 构建差分数组for (int i = 1; i < n; i++) { diff[i] = arr[i] - arr[i - 1];}// 区间增值 [l, r] + valvoid add(int l, int r, int val) { diff[l] += val; diff[r + 1] -= val;}// 还原数组for (int i = 0; i < n; i++) { if (i == 0) arr[i] = diff[i]; else arr[i] = arr[i - 1] + diff[i];}最小生成树
Kruskal
// edges: [u, v, w]static int kruskal(int n, int[][] edges) { Arrays.sort(edges, (a, b) -> a[2] - b[2]); int sum = 0, count = 0; for (int[] e : edges) { // 根节点不同 => 不会连成环，可以合并 if (find(e[0]) != find(e[1])) { union(e[0], e[1]); sum += e[2]; if (++count == n - 1) break; } } return count == n - 1 ? sum : -1;}并查集
int[] p = new int[n + 1]; // 根节点负值取绝对值表示树高度// 初始化每个节点都是根，初始高度为1for (int i = 0; i <= n; i++) p[i] = -1;
// 查找根节点static int find(int x) { if (p[x] < 0) return x; return p[x] = find(p[x]); // 扁平化子节点}// 合并static void union(int x, int y) { int rx = find(x); int ry = find(y); if (rx == ry) return; if (p[rx] < p[ry]) { p[ry] = rx; } else if (p[rx] > p[ry]) { p[rx] = ry; } else { p[rx] = ry; p[ry]--; // 两树高度相同，合并高度+1（一个根指向另一个根） }}Prim (优先队列 堆优化版 适合稀疏图)
// g为邻接表 int[]为{v, w}static int prim(List<int[]>[] g, int n) { boolean[] visited = new boolean[n]; PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> a[1] - b[1]); pq.offer(new int[]{0, 0}); // 生成树起点 int sum = 0, count = 0; while (!pq.isEmpty() && count < n) { int[] cur = pq.poll(); int v = cur[0], w = cur[1]; if (visited[v]) continue; visited[v] = true; sum += w; count++; // 更新生成树周围 for (int[] e : g[v]) { if (!visited[e[0]]) pq.offer(e); } } return count == n ? sum : -1;}Prim (朴素版 适合稠密图)
// g为邻接矩阵 int[n][n]，不可达值设为 MAX_VALUEstatic int prim(int[][] g, int n) { boolean[] visited = new boolean[n]; int[] dist = new int[n]; // 当前生成树到各点的距离 Arrays.fill(dist, Integer.MAX_VALUE); dist[0] = 0; // 生成树起点距离为0 int sum = 0; for (int i = 0; i < n; i++) { int u = -1, min = Integer.MAX_VALUE; for (int j = 0; j < n; j++) { if (!visited[j] && dist[j] < min) { min = dist[j]; u = j; } } if (u == -1) return -1; // 找到了新的最近点，更新状态 visited[u] = true; sum += dist[u]; // 更新生成树周围 for (int v = 0; v < n; v++) { if (!visited[v] && g[u][v] < dist[v]) { dist[v] = g[u][v]; } } } return sum;}持续收集中…
分享
如果这篇文章对你有帮助，欢迎分享给更多人！
Java 常用算法模板备忘整理
http://mizuki.heycheems.top/posts/常用算法模板/ 部分信息可能已经过时
相关文章 智能推荐