算法都是套路系列-数据结构模板

🌸数据结构模板

🍂快速排序

public class Main{ static int[] arr = new int[100010]; public static void q_sort(int l,int r){ if(l>=r)return; int i = l - 1; int j = r + 1; int x = arr[l + r >> 1]; while(i < j){ do i++;while(arr[i] < x); do j--;while(arr[j] > x); if(i<j){ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } q_sort(l,j); q_sort(j+1,r); } public static void main(String[] args) throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(in.readLine()); String s[] = in.readLine().split(" "); for(int i = 0; i < s.length; i++){ arr[i] = Integer.parseInt(s[i]); } q_sort(0, n-1); for(int i = 0; i < n; i++){ System.out.print(arr[i]+" "); } } }

🍂归并排序

void mergesort(int a[], int l, int r){ if(l>=r) return; int mid = l+r>>1; mergesort(a, l, mid); mergesort(a, mid+1, r); int i,j,k = l; for(i = l, j = mid + 1; i <= mid&&j <= r;){ if(a[i] > a[j]){ b[k++] = a[j]; j++; } else b[k++] = a[i], i++; } while(i <= mid) b[k++] = a[i++]; while(j <= r) b[k++] = a[j++]; for(int ii = l; ii <= r; ii++){ a[ii] = b[ii]; } }

🍂朴素Dijkstra

public static int Dijkstra(){ Arrays.fill(dis, 0x3f3f3f3f); dis[1] = 0; for(int i = 0; i < n; i++){ // 循环n次， 每次找出一个离起点最近的点。 int t = -1; for(int j = 1; j <= n; j++){ if(S[j] == 0 && (t == -1 || dis[t] > dis[j])){ // 找到一个距离最短的加入S集合。 t = j; } } S[t] = 1; // 然后通过这个点来缩短原点到达其他点的距离。 for(int j = 2; j <= n; j++){ dis[j] = Math.min(dis[j], dis[t] + w[t][j]); } } if(dis[n] != 0x3f3f3f3f) return dis[n]; else return -1; }

🍂堆优化Dijkstra

public static int Dijkstra(){ Arrays.fill(dis, INF); // 初始化dis数组为正无穷 q.add(new Pair(0, 1)); // 将起点当做一个距离起点最近的点加入优先队列。 dis[1] = 0; // 起点到起点的距离是1. while(!q.isEmpty()){ // 广度优先搜索 + 堆优化。 Pair t = q.poll(); if(S[t.a] == 1) continue; S[t.a] = 1; for(int i = h[t.a]; i != 0; i = ne[i]){ //搜索当前点的所有邻接点。 if(dis[e[i]] > t.w + w[i]){ // 更新距离 dis[e[i]] = t.w + w[i]; q.add(new Pair(dis[e[i]], e[i])); } } } if(dis[n] != INF) return dis[n]; // 可以到达n号点 else return -1; } }

🍂SPFA

/** 我们在一次循环中做了很多不必要的操作，如果我们可以只更新那些前驱结点被更新过的点，就可以大大提升效率。因为只有前驱结点到达起点的距离减小了，它的后继结点到达起点的距离才能减小。 所以我们用宽搜的思想，每次将被更新过的点入队，然后遍历队列中每个点的后继结点，重复更新操作和入队操作。 */ public static void SPFA(){ Arrays.fill(dis, 0x3f3f3f3f); dis[1] = 0; q.add(1); while(!q.isEmpty()){ int t = q.poll(); s[t] = 0; //出对后标记为0，因为可能存在负权边，所以一个点可能会被更新多次， //所以一个点只要被更新过就能入队，次数不限 for(int i = h[t]; i != 0; i = ne[i]){ int j = e[i]; if(dis[j] > dis[t] + w[i]){ dis[j] = dis[t] + w[i]; if(s[j] == 0){// 如果该点当前不在队中，就入队，避免重复操作。 q.add(j); s[j] = 1; //标记已在队中 } } } } }

🍂Prim算法

public static int Prim(){ Arrays.fill(dis, 0x3f3f3f3f); //设所有边距离边集的的距离为正无穷，也就是设所有边的状态为不可查找 int res = 0;// 存储最小生成树的总边权 dis[1] = 0; // 设1号点距离边集的距离为0 for(int i = 0; i < n; i++){// 循环n次 int t = -1; int minv = INF; //存储最短边 for(int j = 1; j <= n; j++){ if(st[j] == 0 && minv > dis[j]){ t = j; minv = dis[j]; } } if(minv == INF) return INF;// 最短边是无穷大，说明该图不连通 res += dis[t]; st[t] = 1; //将t的邻接边的状态更新为待查找 for(int j = 1; j <= n; j++){ // 或者说是缩短t的邻接点到达边集的距离 dis[j] = Math.min(dis[j], g[t][j]); } } return res; }

🍂并查集模板

public class Text { static int n, m, cnt = 0; static int[] f = new int[10005];//初始化一般是f[i] = i public static void main(String[] args) { } public static int find(int x) { if(f[x] == x) { return x; } return f[x] = find(f[x]); } public static void union(int x, int y) { int a = find(x); int b = find(y); if(a != b) { f[a] = b; cnt++; } } }

🍂dfs求联通块

import java.util.Scanner; public class Text { /** * 联通快 */ static int MAX_N = 100 + 2; static char map[][] = new char[MAX_N][MAX_N]; static int n, m; static boolean vis[][] = new boolean[MAX_N][MAX_N];// 用来标记是否是联通快 static int dir[][] = { { -1, -1 }, { -1, 0 }, { -1, 1 }, { 0, -1 }, { 0, 1 }, { 1, -1 }, { 1, 0 }, { 1, 1 } }; public static void main(String args[]) { Scanner scanner = new Scanner(System.in); while (scanner.hasNext()) { n = scanner.nextInt(); m = scanner.nextInt(); if (n + m == 0) { break; } scanner.nextLine(); for (int i = 0; i < n; i++) { String str = scanner.nextLine(); char a[] = str.toCharArray(); for (int j = 0; j < m; j++) { map[i][j] = a[j]; } } int sum = 0; init(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (!vis[i][j] && map[i][j] == '@') {// 当从每个点出发搜索的时候 都会标记以改点扩散的油田 当从下个点搜索的时候 sum++;// 就直接不搜索改点 dfs(i, j); } } } scanner.close(); System.out.println(sum); } } private static void dfs(int x, int y) { vis[x][y] = true; for (int i = 0; i < 8; i++) { int dx = x + dir[i][0]; int dy = y + dir[i][1]; if (dx >= 0 && dx < n && dy > 0 && dy < m && !vis[dx][dy] && map[dx][dy] == '@') { dfs(dx, dy); } } } private static void init() { for (int i = 0; i < MAX_N; i++) { for (int j = 0; j < MAX_N; j++) { vis[i][j] = false; } } } }

🍂最小生成树

import java.util.PriorityQueue; import java.util.Scanner; public class Text { static int n, m, cnt = 0, ans = 0; static int[] f; static int find(int x) { if (f[x] == x) return x; return f[x] = find(f[x]); } static int union(int x, int y) { int a = find(x); int b = find(y); if (a != b) { f[a] = b; return 1; } return 0; } static class Edge implements Comparable<Edge> { int a, b, c; public Edge(int a, int b, int c) { this.a = a; this.b = b; this.c = c; } @Override public int compareTo(Edge o) { return this.c - o.c; } } public static void main(String[] args) { Scanner in = new Scanner(System.in); // 用它来代替Scanner。 while (true) { n = in.nextInt(); if (n == 0) break; m = n * (n - 1) / 2; cnt = 0; ans = 0; f = new int[n + 5]; for (int i = 1; i <= n; i++) f[i] = i; PriorityQueue<Edge> pq = new PriorityQueue<>(); for (int i = 1; i <= m; i++) { int a = in.nextInt(); int b = in.nextInt(); int c = in.nextInt(); int d = in.nextInt(); if (d == 1) cnt += union(a, b); else pq.add(new Edge(a, b, c)); } while (!pq.isEmpty()) { Edge u = pq.poll(); if (union(u.a, u.b) == 1) { cnt++; ans += u.c; if (cnt == n - 1) break; } } in.close(); System.out.println(ans); } } }

🍂拓扑排序

static ArrayList<Integer> list = new ArrayList<>(); static ArrayList<Integer>[] edge = new ArrayList[105]; while(m-->0) {//建图 邻接表 并且用w[i]记录入度 String s1 = in.next(); String s2 = in.next(); if(!map.containsKey(s1)) map.put(s1,n++); if(!map.containsKey(s2)) map.put(s2,n++); w[map.get(s2)]++; edge[map.get(s1)].add(map.get(s2)); } for(int i:map.values())//把边为0的放进队列 if(w[i]==0) q.add(i); while(!q.isEmpty()) { int u = q.poll(); list.add(u); for(int v:edge[u]) { w[v]--; if(w[v]==0) q.add(v); } }

🍂全排列（在搜索技术那里已经有了，这里再放出来加深记忆 ）

💥最常用

static int[] a = new int[] {1,2,3,4,5,6,7,8,9}; static int n=9,ans=0; static void dfs(int m) { if(m>=n) { System.out.println("一些核心的操作 比如ans:"+ans); ans++; for(int i=0;i<n;i++) System.out.print(a[i]+" "); System.out.println(); return; } for(int i=m;i<n;i++) { swap(i,m); dfs(m+1); swap(i,m);//回溯 } } static void swap(int i,int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }

💥使用标记数组的写法

static int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; static int[] b; static boolean[] vis; static int n = 9, ans = 0; static void dfs(int m) { if (m >= n) { System.out.println("一些核心的操作 比如ans:" + ans); ans++; for (int i = 0; i < n; i++) System.out.print(b[i] + " "); System.out.println(); return; } for (int i = 0; i < n; i++) if (!vis[i]) { vis[i] = true; b[m] = a[i]; dfs(m + 1); b[m] = 0;// 其实这个也可以不用回溯，它会被覆盖 vis[i] = false;// 回溯 } }

💥哈希排重

static int[] a = new int[] {1,2,3,4,5,6,7,8,9}; static int[] b; static boolean[] vis; static int n=9,ans=0; static void dfs(int m) { if(m>=n) { System.out.println("一些核心的操作 比如ans:"+ans); ans++; for(int i=0;i<n;i++) System.out.print(b[i]+" "); System.out.println(); return; } for(int i=0;i<n;i++) if(!vis[i]) { vis[i] = true; b[m] = a[i]; dfs(m+1); b[m] = 0;//其实这个也可以不用回溯，它会被覆盖 vis[i] = false;//回溯 } } static int[] a = new int[] {1,2,3,4,5,6,7,8,9}; static int[] b; static boolean[] vis; static int n=9,ans=0; static void dfs(int m) { if(m>=n) { System.out.println("一些核心的操作 比如ans:"+ans); ans++; for(int i=0;i<n;i++) System.out.print(b[i]+" "); System.out.println(); return; } for(int i=0;i<n;i++) if(!vis[i]) { vis[i] = true; b[m] = a[i]; dfs(m+1); b[m] = 0;//其实这个也可以不用回溯，它会被覆盖 vis[i] = false;//回溯 } }

🍂组合

public class Main { public static void main(String[] args) { int[] a = {1, 3, 2}; combinhelp(a, 0, 2, 0); } static int ans = 0; public static void combinhelp(int[] a, int index, int sel, int sum){ if(sel == 0){ System.out.println("[]"); } if(sum == sel){ if(check(a)){ ans++; } return; } if(index == a.length){ return; } //组合框架 a[index] = 1; combinhelp(a, index + 1, sel, sum + 1); a[index] = 0; combinhelp(a, index + 1, sel, sum); } public static boolean check(int[] a){ for(int i = 0; i < a.length; i++){ if(a[i] == 1){ System.out.print((i + 1) + " "); } } System.out.println(); return true; } }