【Java代码】DFS,BFS,并查集,二分法总结

最近没有更新博客，因为博主大部分的时间都在准备算法，备战蓝桥杯，学的比较琐碎，所以也不太好写博客总结。

经过一段时间的学习，总结一下自己这段时间的算法学习吧！

DFS

什么是DFS呢？

DFS就是深度优先遍历，一条路走到黑，不撞南墙不回头。

其实DFS就是一种递归算法。俗称爆搜。

枚举出所有的情况，再根据题目进行判断。

解题方法

对于递归问题，我们可以画递归搜索树，来帮助我们理解。

全排列递归实现排列型枚举

给定一个整数 n，将数字 1∼n排成一排，将会有很多种排列方法。

比如：

n = 3

我们要输出：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

import java.util.*;public class Main {    static int n;    // st[i] == false：i这个数字没用过，反之，i这个数字用过了    static boolean[] st = new boolean[8];    // 记录我们的答案    static int[] path = new int[8];    static Scanner in = new Scanner(System.in); static void dfs(int u) { // 找到了一组答案，搜索到了叶子节点 if (u == n) {     for (int i = 0; i < n ; i ++ ) {  System.out.print(path[i] + " ");     }     System.out.println();     return; }  for (int i = 1; i <= n; i ++ ) {     // 如果i没用过，说明u这层可以用i     if (!st[i]) {  st[i] = true;  path[u] = i;  // 递归下一层  dfs(u + 1);  // 回溯，恢复现场，让回溯的层也能用i  st[i] = false;  path[u] = 0;     } }    }    public static void main(String[] args) { n = in.nextInt(); dfs(0);    }}

递归实现指数型枚举

与上一题的区别是：不是每个数字都要选择的，你可以不选任何数字。

例如：

n = 3

我们要输出：

一个数字都不选

3
2
2 3
1
1 3
1 2
1 2 3

import java.util.*;public class Main {    static Scanner in = new Scanner(System.in);    static int[] st = new int[20];    static int n; static void dfs(int u) { if (u > n) {     for (int i = 1; i <= n; i ++ ) {  // 如果st[i] == 1，说明i是选的  if (st[i] == 1) System.out.print(i + " ");     }     System.out.println();     return; } // st[u] = 1：代表选它，0：代表还没考虑它，2：代表不选它。 st[u] = 2; dfs(u + 1);// 选是一个分支 st[u] = 0;// 恢复现场  st[u] = 1; dfs(u + 1);// 不选是一个分支 st[u] = 0;// 恢复现场    }     public static void main(String[] args) { n = in.nextInt(); // 从数字1开始 dfs(1);    }}

使用DFS解决蓝桥杯的一道真题：带分数

分析思路：

看到1~9分别出现，且只出现一次，我想到了：通过全排列将1 ~ 9的全部排列情况，爆搜出来，然后再根据题目的要求进行判断，就可以得出答案了。

import java.util.Scanner;public class 带分数DFS {    static int n;    // 记录全排列组合    static int[] path = new int[10];    // 记录数字有没有用过    static boolean[] st = new boolean[10];    // 答案    static int ans;    static Scanner in = new Scanner(System.in);    public static void main(String[] args) { n = in.nextInt(); dfs(1); System.out.println(ans);    }    // 全排列的模板    private static void dfs(int u) { if (u > 9) {     // 对于每种全排列的可能，分成三段，算出a，b，c，然后再判断是否满足条件。     for (int i = 1; i <= 7; i ++ ) {  for (int j = i + 1; j <= 8; j ++ ) {      int a = calc(1, i);      int b = calc(i + 1, j);      int c = calc(j + 1, 9);      // 判断是否满足条件      if (n * c - a * c == b) ans ++ ;  }     } } // 全排列的模板 for (int i = 1; i <= 9; i ++ ) {     if (!st[i]) {  path[u] = i;  st[i] = true;  dfs(u + 1);  st[i] = false;  path[u] = 0;     } }    }    // 将区间[l, r]变成具体的数字。    // 比如：[1, 2, 3] => sum = 0 * 10 + 1;(sum = 1)    // sum = 1 * 10 + 2;(sum = 12) sum = 12 * 10 + 3;(sum = 123)    private static int calc(int l, int r) { int sum = 0; for (int i = l; i <= r; i ++ ) {     sum = sum * 10 + path[i]; } return sum;    }}

BFS

什么是BFS？

BFS就是宽度优先遍历，广度优先遍历，它与DFS的区别在于，BFS是一层一层的搜的，因此有一个“最短”的性质，可以解决最小步数等问题。

解题方法

BFS的解题方法比较固定：

1. 将起点加入队列中
2. 当队列不空的时候，弹出队头的元素。
3. 扩展弹出来的元素，将符合条件的，加入到队尾中。

使用BFS解决一道题目：走迷宫

import java.util.*;public class 走迷宫BFS {    // 记录迷宫    static int[][] g = new int[110][110];    // d[i][j]:表示起点到i, j这个点的最短距离    static int[][] d = new int[110][110];    static int n, m;    static Scanner in = new Scanner(System.in);// 用于遍历四周    static int[] dx = {0, 0, -1, 1};    static int[] dy = {-1, 1, 0, 0};    static void bfs(Node start, Node end) { Queue<Node> queue = new LinkedList<>(); // 将起点加入队列中 queue.add(start);// 当队列不空的时候 while (!queue.isEmpty()) {     // 弹出队头元素     Node node = queue.poll();     // 达到终点的话，输出答案之后，直接返回。     if (node.x == end.x && node.y == end.y) {  System.out.println(d[end.x][end.y]);  return;     }     // 将符合条件的点加入到队尾中     for (int i = 0; i < 4; i ++ ) {  int x = node.x + dx[i];  int y = node.y + dy[i];// 不越界，并且可以走，并且是第一次走【确保最短步数】  if (x >= 1 && x <= n && y >= 1 && y <= m && d[x][y] == 0 && g[x][y] == 1) {      queue.add(new Node(x, y));      d[x][y] = d[node.x][node.y] + 1;  }     } } // 程序运行到这里说明没有找到终点，输出-1。 System.out.println(-1);    }    public static void main(String[] args) { n = in.nextInt(); m = in.nextInt(); for (int i = 1; i <= n; i ++ ) {     for (int j = 1; j <= m; j ++ ) {  g[i][j] = in.nextInt();     } } Node start = new Node(in.nextInt(), in.nextInt()); Node end = new Node(in.nextInt(), in.nextInt()); bfs(start, end);    }// 定义节点类    public static class Node { int x; int y; public Node(int x, int y) {     this.x = x;     this.y = y; }    }}

并查集

并查集常用于处理集合合并的问题。

先学习一下模板

1. 初始化操作
2. 合并操作，比如合并x和y：我们只要将x的祖宗节点和y的祖宗节点连接起来了就可以了。比如，把x的祖宗节点变成y的祖宗节点。
3. find函数，查找祖宗节点，含路径压缩。

import java.util.Scanner;public class 并查集 {    static int[] p;    static Scanner in = new Scanner(System.in);    public static void main(String[] args) { int n = in.nextInt(); int m = in.nextInt(); p = new int[n + 10];// 初始化操作，一开始每个元素指向自己。 for (int i = 1; i <= n; i ++ ) p[i] = i;// 合并操作,注意判断x和y是不是已经在同一个集合中了 int x的祖宗 = find(x); int y的祖宗 = find(y); if (x的祖宗 != y的祖宗) {     p[x的祖宗] = y的祖宗; } // 查询操作,直接比较x和y的祖宗节点一不一样即可。     }// 含路径压缩的find函数    private static int find(int x) { // 如果x的父节点不是祖宗节点，就让父节点去找它的祖宗节点，递归下去，最终一定会找到祖宗节点。 if (p[x] != x) p[x] = find(p[x]); // 返回祖宗节点。 return p[x];    }}

使用模板解决一道题目：蓝桥幼儿园

通俗的讲一下题目的意思：

一开始每个人都指向自己，然后进行一些操作，让x和y成为朋友（也就是在同一个集合中），最后进行一些询问，x和y是不是朋友。

import java.util.Scanner;public class 蓝桥幼儿园并查集 {    static int[] p;    static Scanner in = new Scanner(System.in);    public static void main(String[] args) { int n = in.nextInt(); int m = in.nextInt(); p = new int[n + 10]; for (int i = 1; i <= n; i ++ ) p[i] = i; while (m -- > 0) {     int op = in.nextInt();     int a = in.nextInt();     int b = in.nextInt();     if (op == 1) {  a = find(a);  b = find(b);  if (a != b) {      p[a] = b;  }     } else {  System.out.println(find(a) == find(b) ? "YES" : "NO");     } }    }    private static int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];    }}

合根植物

import java.util.HashSet;import java.util.Scanner;import java.util.Set;/** *  AC了，%100 *  并查集：1.将两个集合合并 *  2.询问两个元素是否在同一个集合中 *  近乎O(1) */public class 合根植物并查集 {    static int[] p = new int[1000010];    static Scanner in = new Scanner(System.in);    public static void main(String[] args) { int n = in.nextInt(); int m = in.nextInt(); int k = in.nextInt(); // 初始化，一开始所有节点的父节点都是自己。 for (int i = 1; i <= n * m; i ++ ) p[i] = i; while (k -- > 0) {     int a = in.nextInt();     int b = in.nextInt();     a = find(a);     b = find(b);     if (a != b) {  p[a] = b;     } } Set set = new HashSet(); for (int i = 1; i <= n * m; i ++ ) {     set.add(find(p[i])); } System.out.println(set.size());    }    // 返回x的祖宗节点，含有路径压缩的    static int find(int x) { if (p[x] != x) p[x] = find(p[x]); return p[x];    }//    // 正常的//    static int find(int x) {// while (p[x] != x) x = p[x];// return p[x];//    }}

种类并查集【拓展域并查集】

普通的并查集维护的关系：朋友的朋友是朋友，无法维护敌人的敌人是朋友，朋友的敌人是敌人。

这时就要用到种类并查集了。

种类并查集又叫做扩展域并查集，也就是我们扩展出一个域 i + n，作为 i号的点的敌人，

那么同时和 i + n 相连的点就是 i号点的敌人，那么他们之间也就是朋友，这样就可以维护 ”敌人的敌人是朋友“这 类关系了。

蓝桥侦探

import java.util.Scanner;public class 蓝桥侦探 {// 种类并查集static int[] p = new int[1000010];// 查找static int find(int x) {if (p[x] != x)p[x] = find(p[x]);return p[x];}// 合并static void merge(int x, int y) {int tx = find(x);int ty = find(y);if (tx != ty) {p[tx] = ty;}}public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int q = in.nextInt();// 种类并查集，不仅// 构造一个2n的空间for (int i = 1; i <= 2 * n + 1; i++)p[i] = i;int ans = 0;while (q-- > 0) {// x 和 y不在一个房间  x 和 y是敌人关系，不在同一个并查集中，x 和 y + n就是朋友，在同一个并查集中，// 同理，y 和 x + n就是朋友，在同一个并查集中。int x = in.nextInt();int y = in.nextInt();if (ans == 0) {// x 和 y， x + n 和 y + n,应该是对立的关系，不应该出现在同一个并查集中，那么答案就是这个x。if (find(x) == find(y) || find(x + n) == find(y + n)) {ans = x;}// 合并x 和 y + nmerge(find(x), find(y + n));// 合并y 和 x + nmerge(find(y), find(x + n));}}System.out.println(ans);}}

二分法

模板

// 模板1：int l = 0, r = n - 1;while (l < r) {    int mid = l + r >> 1;    if (q[mid] >= x) r = mid;    else l = mid + 1;}// 模板2：int l = 0, r = n - 1;while (l < r) {    int mid = l + r + 1 >> 1;    if (q[mid] <= x) l = mid;    else r = mid - 1;}

分巧克力

import java.util.Scanner;public class 打包贪心二分 {    static int[] weight = new int[100010];    public static void main(String[] args) { Scanner in = new Scanner(System.in); // 有n个物品 int n = in.nextInt(); // 打包成m个包裹 int m = in.nextInt(); // 答案一定在[max, sum]之间 int l = 0, r = 0; for (int i = 0; i < n; i ++ ) {     weight[i] = in.nextInt();     l = Math.max(l, weight[i]);     r += weight[i]; } while (l < r) {     int mid = l + r >> 1;     if (check(weight, mid, m)) {  r = mid;     } else {  l = mid + 1;     } } System.out.println(l);    }    private static boolean check(int[] weight, int ans, int m) { // 记录当前包裹的重量之和 int curWeight = 0; // 记录当前打包过的包裹数量 int curPack = 1; for (int val : weight) {     // 如果这个物品的重量大于了ans，直接返回false     if (val > ans) return false;     // 当前包裹的重量加上这个物品的重量     curWeight += val;     // 如果加上之后，包裹的总重量 > ans，我们就要在开一个新的包裹。     if (curWeight > ans) {  curPack ++ ;  // 新的包裹的初始重量为：这个物品的重量  curWeight = val;     } } // 如果包裹的数量小于等于m，则说明这个ans，是符合条件的。 return curPack <= m;    }}

数论

质数

试除法判定质数

这是最暴力的方法。

但是我们可以把时间复杂度优化到O(根号n)

一个数的因数都是成对出现的：例如12的因数有3和4,2和6

所以我们可以只枚举较小的那一个，即根下n，假设较小的为d，较大的为n/d；

import java.util.*;public class Main { static boolean check(long x) { if (x < 2) return false; for (int i = 2; i <= x / i; i ++ ) {     if (x % i == 0) return false; } return true;    }    public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for (int i = 0; i < n; i ++ ) {     long x = in.nextLong();     if (check(x)) System.out.println("Yes");     else System.out.println("No"); }    } }

埃式筛【时间复杂度O(nloglogn)】

import java.util.*;public class Main {    static int[] primes = new int[1000010];    static int cnt;    static boolean[] st = new boolean[1000010]; public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); for (int i = 2; i <= n; i ++ ) {     // st[i] = false,代表i是质数     if (!st[i]) {  primes[cnt ++ ] = i;  // 将质数i的倍数都是合数  for (int j = i * 2; j <= n; j += i) {      st[j] = true;  }     } }     System.out.println(cnt);    }}

找素数

public class 找素数埃式筛 {    static int[] primes = new int[10000010];    static boolean[] st = new boolean[10000010];    static int cnt;    public static void main(String[] args) { getPrimes(); //System.out.println(cnt); System.out.println(primes[100001]);    }    private static void getPrimes() { for (int i = 2; i <= 10000000; i ++ ) {     if (!st[i]) {  primes[cnt ++ ] = i;  st[i] = true;  for (int j = i * 2; j <= 10000000; j += i) {      st[j] = true;  }     } }    }}

约数

试除法求约数

由于一个数的约数是成对出现的，并且最多只会有一个大于根号n的约数，因此可以把时间复杂度优化到O(根号n)

import java.util.*;public class Main {    static Scanner in = new Scanner(System.in);    // TreeSet，去重并且自动排序    static Set<Integer> set = new TreeSet<>();    static void get(int x) { set.clear(); for (int i = 1; i <= x / i; i ++ ) {     if (x % i == 0) {  set.add(i);  set.add(x / i);     } } set.stream().forEach(item -> System.out.print(item + " ")); System.out.println();    }    public static void main(String[] args) { int n = in.nextInt(); while (n -- > 0) {     int x = in.nextInt();     get(x); }     }}

最大公约数

直接上模板

import java.util.*;public class Main {    static Scanner in = new Scanner(System.in); static int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a;    }    public static void main(String[] args) { int n = in.nextInt(); while (n -- > 0) {     int a = in.nextInt();     int b = in.nextInt();     System.out.println(gcd(a, b)); }    }}

快速幂

在求n的m次方的时候，如果我们采用采用暴力的方法，当m的数据很大的时候，是会超时的，溢出的。

long quickMi(long n, long m, long p) {    long res = 1;    while (m != 0) { if ((m & 1) == 1) {     res = res * n % p; } m >>= 1; n = n * n % p;    }    return res;}

import java.util.*;public class Main {    static Scanner in = new Scanner(System.in); static int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a;    }    public static void main(String[] args) { int n = in.nextInt(); while (n -- > 0) {     int a = in.nextInt();     int b = in.nextInt();     System.out.println(gcd(a, b)); }    }}

快速幂

在求n的m次方的时候，如果我们采用采用暴力的方法，当m的数据很大的时候，是会超时的，溢出的。

long quickMi(long n, long m, long p) {    long res = 1;    while (m != 0) { if ((m & 1) == 1) {     res = res * n % p; } m >>= 1; n = n * n % p;    }    return res;}