常见算法模板

2024-04-10数据结构与算法17 分钟155 次阅读
AI 摘要salmon-ai

本文详细解析了常见算法模板的核心用法与Java实现,包括IO优化、GCD/LCM、快速幂、素数筛与质因数分解、斐波那契、DFS/BFS、并查集、组合与排列枚举、

IO

字符串输入、输出

数据量少,可以使用 import java.util.Scanner;

java 复制代码
Scanner sc = new Scanner(System.in);

数据量多,则使用 import java.io.* 下的 BufferedReader,利用 StringTokenizer 读取大量字符串(缓冲流),会很高效。

java 复制代码
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
String s=st.nextToken();

输出只需几行,可以直接使用 sout

java 复制代码
System.out.println("aaaa");

如果需要大量打印,则可以使用 import java.io.* 下的 PrintWriter 会更高效。

java 复制代码
PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
pw.print("hhh");

数学

最大公约数(GCD)

同时能整除整数 a 和 b 的 最大整数,比如:15 和 81 的最大公约数是 3,0 和 44 的最大公约数是 44,-17 和 289 的最大公约数是 -17。

java 复制代码
private static int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

最小公倍数(LCM)

a 与 b 相乘,然后除以它们的最大公约数。

java 复制代码
private static int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

private static int gcm(int a, int b) {
	return a / gcd(a, b) * b; // 先做除法再做乘法防止溢出
}

快速幂

比暴力计算快,特别是指数很大的情况,通过位运算快速计算,同时避免溢出。

java 复制代码
/**
 * 如果无需取模,则把模板中的取模去掉即可
 * 
 * @param a
 * @param n
 * @param mod
 */
private static long fastPow(long a, long n, long mod) {
	long ans = 1;
	a %= mod;
	while (n > 0) {
		if ((n & 1) == 1) {
			ans = (ans * a) % mod;
		}
		a = (a * a) % mod;
		n >>= 1;
	}
	return ans;
}

素数

只能被 1 和自己本身整除的正整数是素数,注意:1 不是素数,最小素数是 2。

java 复制代码
/**
 * 判断一个数是不是素数
 * 
 * @param n
 * @return
 */
private static boolean isPrime(int n) {
	if (n <= 1) {
		return false; // 1 不是素数
	}
	for (int i = 2; i <= Math.sqrt(n); i++) {
		 
		if (n % i == 0) {
			return false;
		}
	}
	return true;
}

埃氏筛,如果需要获取某个范围内的素数或者质数,可以考虑这个方法

java 复制代码
static int[] primes; // 存放素数
static boolean[] noPrime; // 标记是否非素数
static int cnt; // 素数个数

/**
 * 如果需要获取某个范围内的素数或者质数,可以考虑这个方法
 * 
 * @param n
 */
private static void getPrime(int n) {
	primes = new int[n + 1];
	noPrime = new boolean[n + 1];
	// 先初始化所有数都是素数
	Arrays.fill(noPrime, false);
	// 0和1不是素数
	noPrime[0] = true;
	noPrime[1] = true;
	// 注意这里包含 n
	for (int i = 2; i <= n; i++) {
		// 如果该数还未被标记为是否素数
		if (!noPrime[i]) {
			primes[cnt++] = i; // 标记为素数
			// 计算以 i 为倍速的数,都不是素数
			for (int j = i * 2; i <= n; j += i) {
				noPrime[j] = true; // 标记为不是素数
			}
		}
	}
}

分解质因子

把 n 分解成最小的质因数,如:3=33 = 3、4=2×24 = 2 \times 2、5=55 = 5、6=2×36 = 2 \times3、7=77 = 7、8=2×2×38 = 2 \times 2 \times 3 、9=3×39 = 3 \times 3、10=2×510 = 2 \times 5。

java 复制代码
static int[] p = new int[20]; // 记录因子,p[1]是最小因子。一个 int 数的质因子最多有 10 几个
static int[] c = new int[40]; // 记录第 i 个因子的个数,一个因子的个数最多有 30 几个

public static void main(String[] args) throws IOException {
	fenjie(2, 10);
}


/**
 * 将 a 到 b所有整数的质因子分解
 * 
 * @param a
 * @param b
 */
private static void fenjie(int a, int b) {
	for (int i = a; i <= b; i++) {
		int m = factor(i); // 得到质因子的个数
		System.out.print(i + "=");
		// 从最小质因子开始,第 j 个因子
		for (int j = 1; j <= m; j++) {
			// 第 j 个因子的个数
			for (int k = 1; k <= c[j]; k++) {
				System.out.print(p[j]);
				if (k != c[j]) {
					System.out.print("*");
				}
			}
			if (j < m) {
				System.out.print("*");
			}
		}
		System.out.println();
	}
}

/**
 * 返回当前 n 的因子的个数
 * 
 * @param n
 * @return
 */
private static int factor(int n) {
	int m = 0;
	// 逐个检查 2 到根号n 中所有的素数
	for (int i = 2; i <= Math.sqrt(n); i++) {
		// 如果 i 能整除 n,就是最小质因子
		if (n % i == 0) {
			++m;
			p[m] = i; // 记录 i 为 n 的质因子
			c[m] = 0; // 初始因子 i 的个数
			// 循环获取当前这个因子在 n 中有多少个,直到余数不为 0
			while (n % i == 0) {
				n /= i; // 去掉 n 中重复的因子 i
				c[m]++; // 累加因子 i 个个数
			}
		}
	}
	// 走到这里 n 还大于1,说明它是素数
	if (n > 1) {
		m++;
		p[m] = n; // 素数的因子为自己本身
		c[m] = 1; // 这个位置的数的因子只有 1 个
	}
	return m;
}
image.png

因式分解

java 复制代码

大数分解

java 复制代码

斐波那契数列

image.png
java 复制代码
static final int N = 31;
static int[] f = new int[N];

public static void main(String[] args) throws IOException {
	f[0] = 0;
	f[1] = 1;
	for (int i = 2; i < N; i++) {
		f[i] = f[i - 1] + f[i - 2];
	}
	System.out.print(f[9]);
}

搜索

dfs

java 复制代码
boolean check(参数)
{
    if(满足条件)
        return true;
    return false;
}
boolean pd(参数){
    相应操作
}
void dfs(int step)
{
        判断边界pd()
        {
            不在边界内,即回溯
        }
        尝试每一种可能
        {
               满足check条件

               标记

               继续下一步dfs(step+1)

               恢复初始状态(回溯的时候要用到)
        }
}

bfs

java 复制代码
boolean check(参数)
{
    if(满足条件)
        return true;
    return false;
}
boolean pd(参数){
    相应操作
}
void bfs()
{
    1. 把根节点放入队列尾端
    2. 每次从队列中取出一个节点
    3. Check 判断是不是答案,如果是结束算法 return;
    4. 把当前取出的节点扩展,如果扩展后的节点经Pd()后符合要求,就放入队列,不符合就不放。
    5. 转到步骤2,循环执行
}

如果所有节点被扩展完了,没有找到答案就无解。

并查集

  • 判断图的连通性
  • 区间问题
  • 连续子序列问题
  • 最小生成树 kruskal 算法
java 复制代码
static final int MAXN = 200;
static int[] father = new int[MAXN + 1];

/**
 * 查找根节点
 */
private static void findRoot() {
	for (int i = 1; i <= MAXN; i++) {
		// 根节点的自身
		if (father[i] == i) {

		}
	}
}

/**
 * 初始化并查集
 * 
 * @param n
 */
private static void init() {
	// 初始化每个节点的根节点为自己
	for (int i = 0; i <= MAXN; i++) {
		father[i] = i;
	}
}

/**
 * 合并 x、y节点
 * 
 * @param x
 * @param y
 */
private static void merge(int x, int y) {
	int a = find(x);
	int b = find(y);
	if (a != b) {
		// 往根节点小的合并
//		if (a > b) {
//			father[a] = b;
//		} else {
//			father[b] = a;
//		}
		// 一般这样即可
		father[b] = a;
	}
}

/**
 * 查找x的根节点
 * 
 * @param x
 * @return
 */
private static int find(int x) {
	if (father[x] == x) {
		return x;
	}
	father[x] = find(father[x]);
	return father[x];
}

枚举

组合型枚举

在 n 个元素中随机选取出 m 个元素的问题。我们需要确定选择了哪 m 个元素,这就是组合型枚举。

java 复制代码
import java.util.Scanner;
import java.util.Vector;
public class Main {

    static int n;
    static int m; // 选m个数
    static Vector<Integer> chosen = new Vector<Integer>();

    private static void calc(int x) {
	// 当前元素选够,或者当前选择的元素,加上剩余未选的元素还不够要求,那就没必要走下去了
        if (chosen.size() > m || chosen.size() + (n - x + 1) < m) //剪枝
            return;
        if (chosen.size() == m) { //选够了m个数输出
            String ansTem = "";
            for (int i = 0; i < chosen.size(); i++)
                System.out.print(chosen.get(i)+" ");
            System.out.println("");
            return;
        }
	// 包含这个元素的组合情况
        chosen.addElement(x);
        calc(x + 1);
	// 不包含这个元素的组合情况
        chosen.remove((Object)x);
        calc(x + 1);
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        m = in.nextInt();
        calc(1);
    }
}

排列型枚举

n 个排列情况。

java 复制代码
  static int n;
  static int[] order =new int[20];
  static boolean[] chosen =new boolean[20];

  private static void calc(int x) {
      // 选够了 n 个数输出
      if (x == n + 1) { 
	  // 排列结果
          String ansTem = "";
          for (int i = 1; i <=n ; i++)
              System.out.println(order[i]);
          return;
      }
      for (int i = 1; i <= n; i++) {
	  // 跳过当前排序中已选择的节点
          if (chosen[i]) continue;
          order[x] = i; // 当前排序第 x 个的元素的下标为 i
          chosen[i] =true;
          calc(x + 1); // 找到下一个组合的结点
          chosen[i] = false;
          order[x] = 0; // 取消当前第 x 序号的
      }
  }

  public static void main(String[] args) {
      Scanner in = new Scanner(System.in);
      n = in.nextInt();
      for (int i = 0; i < n; i++) {
          String s = in.next();
          name.addElement(s);
      }
      calc(1);
  }

尺取法

image.png
java 复制代码
// 奇怪的动物园
public class Main {

	static final int MAXN = 10000005;
	static int[] animals = new int[MAXN]; // 记录每一个动物的种类类型
	static int[] looks = new int[MAXN]; // 观看动物的类型的次数
	static int count; // 累计不同动物的类型数

	/**
	 * 插入这种动物类型
	 * 
	 * @param type 动物类型
	 */
	private static void insert(int type) {
		// 如果这种动物之前没有看过,则记录类型数量
		if (looks[type] == 0) {
			count++;
		}
		// 累加这种动物的数量
		looks[type]++;
	}

	/**
	 * 删除这种动物类型
	 * 
	 * @param type 动物类型
	 */
	private static void delete(int type) {
		// 如果删除后这个动物不再记录中,则类型数量减去这种动物的
		if (looks[type] == 1) {
			count--;
		}
		// 减去这种动物的数量
		looks[type]--;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(); // n种动物
		int m = sc.nextInt(); // 最受欢迎的动物种类数量

		for (int i = 1; i <= n; i++) {
			animals[i] = sc.nextInt();
		}

		int ans = n; // 默认观看的动物种类为
		
		// 滑动窗口:每次扩大窗口范围,当满足某个条件时,收缩窗口
		int left = 0, right = 0;
		// 初始左右边界
		// 每次循环右边界移动,扩大窗口范围(可观看的动物)
		for (int l = 1, r = 1; r <= n; r++) {
			// 插入第 r 个动物
			insert(animals[r]);

			while (true) {
				delete(animals[l]);
				// 删了这个动物后,如果不影响,则缩小窗口,看的越多费用越高
				if (count == m) {
					l++;
				} else {
					// 删除了会减少观看种类的数量,则重新加回去
					insert(animals[l]);
					break;
				}
			}
			// 如果观看了 m 种动物,并且区间比之前的小
			if (count == m && r - l + 1 < ans) {
				left = l;
				right = r;
				ans = r - l + 1;
			}
		}
		// 输出最小窗口的左右边界,如果没有找到符合条件的窗口,则输出整个序列
		if (left != 0)
			System.out.println(left + " " + right);
		else
			System.out.println("1 " + n); // 特殊情况,输出 1~n
	}

}

差分前缀和

一维差分与前缀和

image.png
java 复制代码
public class Main {

	static int[] b = new int[8];
	static int[] a = { 0, 1, 2, 3, 4, 5, 7, 2 };

	public static void main(String[] args) {
		// 初始化拆分区间b
		for (int i = 1; i <= 7; i++) {
			b[i] = a[i] - a[i - 1];
		}
		// 对区间 1到 3 做 +5 操作
		b[1] += 5;
		b[3 + 1] -= 5;
		// 对区间 3 到5 做 -4 操作
		b[3] += -4;
		b[5 + 1] -= -4;
		// 则变化后的 a 为:
		// 编号从1开始输出
		for (int i = 1; i < 8; i++) {
			a[i] = b[i] + a[i - 1];
			System.out.printf("a%d = b%d + a%d = %d\n", i, i, i - 1, a[i]);
		}
	}

}

二维差分与前缀和

java 复制代码

二分

整数二分

java 复制代码
// 在单调递增序列 a 中查找>=x的数中最小的一个(即x或x的后继)
while (low < high) {
    int mid = (low + high) / 2;

    if (a[mid] >= x)
      high= mid;
    else
      low = mid + 1;
}

// 在单调递增序列 a 中查找<=x的数中最大的一个(即x或x的前驱)
while (low < high) {
    int mid = (low + high + 1) / 2;

    if (a[mid] <= x)
      low = mid;
    else
      high = mid - 1;
}

实数二分

java 复制代码
//令eps 为小于题目精度一个数即可。

//比如有些题目说保留4位小数,0.0001 这种的。那么eps 就可以设置为五位小数的任意一个数 0.00001- 0.00009 等等都可以。一般为了保证精度我们选取精度 /100 的那个小数,即设置  eps= 0.0001/100 =1e-6。

while (l + eps < r) {
    double mid = (l + r) / 2;

    if (pd(mid))
      r = mid;
  else
      l = mid;
}

// 实数域二分,规定循环次数法

//通过循环一定次数达到精度要求,这个一般log2N< 精度即可。N为循环次数,在不超过时间复杂度的情况下,可以选择给N乘一个系数使得精度更高。

for (int i = 0; i < 100; i++) {

    double mid = (l + r) / 2;
    if (pd(mid))
      r = mid;
  else
      l = mid;
}

M次方根

java 复制代码
import java.util.Scanner;

// M次方根
public class Main {

	static int n;
	// 题目要精确到九位小数,这里我用9位去算,避免影响7位的精度
	static double eps = 1e-9;

	private static boolean pd(double x, int m) {
		double sum = 1;
		// 计算 x 的 m 次方
		while (m-- > 0) {
			sum *= x;
		}
		// 如果 x 的 m 次方大于 n,说明这个数满足条件
		if (sum >= n) {
			return true;
		}

		return false;
	}

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int m = sc.nextInt();

		// 定义二分上下界
		double l = 0;
		double r = n;

		double mid = 0;

		// 实数二分
		while (l + eps < r) {
			mid = (l + r) / 2;
			// 判断该数的 m 次方是否大于等于 n
			if (pd(mid, m)) {
				// 大于等于n,让这个数作为上限,继续缩小范围
				r = mid;
			} else {
				// m次方 小于 n,说明该数太小,应作为下限,缩小范围
				l = mid;
			}
		}
		// 左右指针相遇,输出结果
		System.out.printf("%.7f\n", l);
		// 当然,题目可以直接用数学工具解决这题
//		 System.out.printf("%.7f\n", Math.pow(n, (double) 1 / m));
	}
}

贪心

java 复制代码
while(Q.hasNextStep) {
    // 选择新的最好的选择	
    Select(Q.nowBestSelect);
    Q.NextStep
}

Select(Q.nowBestSelect);

LIS 最长公共子序列

image.png
简单理解就是, i 和 j 位置的元素不是公共子序列,故不选它,那么当前存储的最优解来自上一次未考虑第 i 个元素与第 j 个元素时的最优解,也就是:dp[i - 1][j]、dp[i][j - 1],找到两者的最大值作为当前长度为 i 和 j 时最优解。

java 复制代码
int[][] dp = new int[Max][Max];

dp[0][0] = 0;
for (int i = 0; i < n; i++) {
	for (int j = 0; j < m; j++) {
		if (a[i] == b[j]) {
			dp[i + 1][j + 1] = dp[i][j] + 1;
		} else {
			dp[i + 1][j + 1] = Math.max(dp[i + 1][j], dp[i][j + 1]);
		}
	}
}

System.out.print(dp[n][m]);

LIS 最长递增子序列

这题是一道递增序列的例题,从数组找出最长的递增子序列。故理解代码即可。

java 复制代码
import java.util.Scanner;

// 蓝桥骑士
public class Main {

	static int N;
	static int[] arr;
	static int[] dp; // 存储处理到第 i 个元素时的最长递增子序列长度

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		arr = new int[N];
		dp = new int[N];
		for (int i = 0; i < N; i++) {
			arr[i] = sc.nextInt();
			// 初值,每个位置的递增子序列长度为1
			dp[i] = 1;
		}

		// 找到终点为 i 的最长递增子序列长度
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < i; j++) {
				// 如果前 i 个元素中,比终点 i 位置的元素值小
				// 那它对于终点 i 是递增的
				// 且终点为 j 时的最优解加上当前的 i 如果比现在的最优解好,则更新。
				if (arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
					dp[i] = dp[j] + 1;
				}
			}
		}
		System.out.print(dp[N - 1]);
	}
}

LCS 最近公共祖先

java 复制代码

背包问题

0/1背包

java 复制代码
// 初始化细节
//装满
Arrays.fill(dp, -0x3f3f3f3f);
dp[0]=0;

//不装满
Arrays.fill(dp, 0);

for (int i = 0; i < n; i++) //遍历每一件物品
{
      for (int j = C; j >= c[i]; j--)
            //遍历背包容量,表示在上一层的基础上,容量为J时,第i件物品装或不装的最优解;
           dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}

System.out.println(dp[C]);

完全背包

java 复制代码
//装满
Arrays.fill(dp, -0x3f3f3f3f);
dp[0]=0;

//不装满
Arrays.fill(dp, 0);

for (int i = 0; i < n; i++) //遍历每一件物品
{
	for(int j=c[i];j<=C;j++)
      		//遍历背包容量,表示在上一层的基础上,容量为J时,第i件物品装或不装的最优解;
                dp[j] = max(dp[j - c[i]] + w[i], dp[j]);
}
System.out.println(dp[C]);

多重背包

java 复制代码
//装满
Arrays.fill(dp, -0x3f3f3f3f);
dp[0]=0;

//不装满
Arrays.fill(dp, 0);

//遍历每一个物品
for(int i=0;i<n;i++) {
    //遍历物品的数量
    for(int j=0;j<=s[i];j++) {
        //当做01背包来处理
        for(int k=C;k>=c[i];k--) {
            //取01背包情况的dp[k]和dp[k-c[i]]+w[i]的最大值
            dp[k]=max(dp[k],dp[k-c[i]]+w[i]);
        }
    }
}
System.out.println(dp[C]);

最短路径

Floyd

求多源最短路径

java 复制代码
for(int k=1; k<=n; k++)         //floyd的三重循环
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)      // k循环在i、j循环外面
            dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);

Dijkstra

求单源最短路径,无负权值

java 复制代码
import java.util.*;
import java.io.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static final int N = 300005;
    static ArrayList<Edge>[] e = new ArrayList[N];
    static int n, m;
    static int[] pre = new int[N];
    static long[] dis = new long[N];
    static boolean[] done = new boolean[N];

    static class Edge {
        int from, to;
        long w;

        Edge(int a, int b, long c) {
            from = a;
            to = b;
            w = c;
        }
    }

    static class SNode implements Comparable<SNode> {
        int id;
        long n_dis;

        SNode(int b, long c) {
            id = b;
            n_dis = c;
        }

        public int compareTo(SNode o) {
            return Long.compare(n_dis, o.n_dis);
        }
    }

    static void printPath(int s, int t) {
        if (s == t) {
            System.out.print(s + " ");
            return;
        }
        printPath(s, pre[t]);
        System.out.print(t + " ");
    }

    static void dijkstra() {
        int s = 1;
        PriorityQueue<SNode> Q = new PriorityQueue<>();
        Arrays.fill(dis, INF);
        dis[s] = 0;
        Q.offer(new SNode(s, dis[s]));
        while (!Q.isEmpty()) {
            SNode u = Q.poll();
            if (done[u.id])
                continue;
            done[u.id] = true;
            for (Edge y : e[u.id]) {
                if (done[y.to])
                    continue;
                if (dis[y.to] > y.w + u.n_dis) {
                    dis[y.to] = y.w + u.n_dis;
                    Q.offer(new SNode(y.to, dis[y.to]));
                    pre[y.to] = u.id;
                }
            }
        }
        // printPath(s, n);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        for (int i = 1; i <= n; i++)
            e[i] = new ArrayList<>();
        for (int i = 1; i <= m; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            long w = Long.parseLong(st.nextToken());
            e[u].add(new Edge(u, v, w));
            // e[v].add(new Edge(v, u, w)); //本题是单向道路
        }
        dijkstra();
        for (int i = 1; i <= n; i++) {
            if (dis[i] >= INF)
                System.out.print("-1 ");
            else
                System.out.print(dis[i] + " ");
        }
    }
}

SPFA

求单源最短路径,无负权环

java 复制代码
import java.util.*;

public class Main {
    static final long INF = 0x3f3f3f3f3f3f3f3fL;
    static final int N = 5010;

    static long[] dist = new long[N];
    static int[] inq = new int[N];
    static List<edge>[] e = new ArrayList[N];

    static class edge {
        int to;
        long w;

        public edge(int tt, long ww) {
            to = tt;
            w = ww;
        }
    }

    static void spfa(int s) {
        Arrays.fill(dist, INF);
        dist[s] = 0;
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
        inq[s] = 1;
        while (!q.isEmpty()) {
            int u = q.poll();
            inq[u] = 0;
            if (dist[u] == INF) continue;
            for (int i = 0; i < e[u].size(); i++) {
                int v = e[u].get(i).to;
                long w = e[u].get(i).w;
                if (dist[v] > dist[u] + w) {
                    dist[v] = dist[u] + w;
                    if (inq[v] == 0) {
                        q.add(v);
                        inq[v] = 1;
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt();
        for (int i = 1; i <= n; i++) {
            e[i] = new ArrayList<>();
        }
        for (int i = 1; i <= m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            long w = in.nextLong();
            e[u].add(new edge(v, w));
        }
        spfa(s);
        for (int i = 1; i <= n; i++) {
            if (dist[i] == INF) System.out.print("-1 ");
            else System.out.print(dist[i] + " ");
        }
    }
}

最小生成树

Prim

最小生成树(稠密图,很多边)

java 复制代码
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

	// 定义常量 INF 表示无穷大
	private static final int INF = 0x3f3f3f3f;
	// 定义常量 MAXN 表示顶点的最大数量
	private static final int MAXN = 1005;

	// 存储与顶点 i 最近的结点编号(边权值最小)
	private static int[] closest = new int[MAXN];
	// 存储已经形成的生成树中某个顶点到 i 的最小权值
	private static int[] lowcost = new int[MAXN];

	// 定义二维数组存储图的边权值
	private static int[][] G = new int[MAXN][MAXN];
	private static int m; // 顶点数量

	// 定义列表存储 Prim 算法中生成树的边权值
	private static List<Integer> demo = new ArrayList<>();

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		// 读取顶点数量 m 和边的数量 n
		m = sc.nextInt();
		int n = sc.nextInt();

		// 读取每条边的起点、终点和权值,并存储到二维数组 G 中
		for (int i = 0; i < n; ++i) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			int c = sc.nextInt();
			G[b][a] = G[a][b] = c;
		}

		// 调用 prim 方法求解最小生成树的权值并输出
		System.out.println(prim());

		// 输出存储在 demo 中的边权值
		for (int i = 0; i < m - 1; i++) {
			System.out.print(demo.get(i) + " ");
		}
	}

	// Prim 算法实现
	private static int prim() {
		// 初始化数组 lowcost 和 closest
		for (int i = 0; i < m; i++) {
			// 存储已经形成的生成树中某个顶点到 i 的最小权值
			// 默认无穷大
			lowcost[i] = INF;
			// 存储与顶点 i 最近的结点编号
			closest[i] = 0;
		}

		// 将第一个顶点加入生成树中,标记为 -1,表示在集合 U 中
		closest[0] = -1;

		int num = 0; // 处理第几条边
		int ans = 0; // 最小生成树的总权值
		int e = 0; // e 为最新加入最小生成树的的点

		// 每次加入一条边,直到加入 m-1 条边为止
		// (最小生成树,那总边数是节点数-1)
		while (num < m - 1) {
			int min_w = INF; // 当前找到的边的最小权值
			int min_num = -1; // 当前找到的最小权值的节点编号

			// 找到当前集合 U 中与集合 V 中最近的顶点
			for (int i = 0; i < m; i++) {
				// 如果 i 已经加入最小生成树,则不处理
				if (closest[i] != -1) {
					// 找到 e 与 i 的边的权值
					int temp = G[e][i];
					// 如果当前边的最短路径比之前最小生成树到 i 的最短路径小,则更新
					if (temp < lowcost[i]) {
						// 更新最小生成树到节点 i 的最短路径为 temp
						lowcost[i] = temp;
						// 更新 i 最近的(权值最小的邻接点) 为 e
						closest[i] = e;
					}
					// 如果当前边的权值,比之前记录的权值小,则更新
					if (lowcost[i] < min_w) {
						min_num = i; // 更新 e 最近节点的编号
						min_w = lowcost[min_num]; // 更新当前的最小权值
					}
				}
			}
			// 将找到的最小权值加入 demo 中
			ans += min_w;
			// 用于之后打印与每个顶点相邻的边的最小权值
			demo.add(min_w);
			// 下次从该顶点找到权值最小的边的节点
			e = min_num;
			// 将找到的顶点标记为已加入生成树的状态,即在集合 U 中
			closest[e] = -1;
			num++;
		}
		// 返回最小生成树的总权值
		return ans;
	}

}

Kruskal

最小生成树(稀疏图,比较少的边)

java 复制代码
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m;
    static int[] father; // 记录并查集中每个节点的父节点
    static Node[] Q; // 存储边的信息,包括起点、终点和权值

    static class Node {
        int x; // 边的起点
        int y; // 边的终点
        int k; // 边的权值

        public Node(int x, int y, int k) {
            this.x = x;
            this.y = y;
            this.k = k;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt(); // 顶点数量
        m = scanner.nextInt(); // 边的数量

        father = new int[n + 1]; // 初始化并查集
        Q = new Node[m]; // 初始化边的数组

        int cont = 0, sum = 0, st = 0; // cont用于统计边的数量,sum为最小生成树的权值,st为边的数量

        // 读取边的信息,并统计所有边的权值总和
        for (int i = 0; i < m; i++) {
            int x = scanner.nextInt(); // 边的起点
            int y = scanner.nextInt(); // 边的终点
            int k = scanner.nextInt(); // 边的权值
            Q[i] = new Node(x, y, k); // 将边的信息存储到数组中
            cont += k; // 统计边的权值总和
        }

        Arrays.sort(Q, (a, b) -> a.k - b.k); // 根据边的权值进行排序

        for (int i = 1; i <= n; i++)
            father[i] = i; // 初始化并查集,每个顶点的父节点都是自己

        // 遍历所有边,并使用并查集找出最小生成树
        for (int i = 0; i < m; i++) {
            int tx = find(Q[i].x); // 找到起点的根节点
            int ty = find(Q[i].y); // 找到终点的根节点
            if (tx != ty) { // 如果起点和终点的根节点不相同,说明加入这条边不会形成环
                sum += Q[i].k; // 将这条边的权值加入到最小生成树的权值中
                st++; // 边的数量加一
                father[tx] = ty; // 将起点的根节点指向终点的根节点,表示它们在同一个连通分量中
                if (st == n - 1) // 如果边的数量等于顶点数量减一,说明最小生成树已经构建完成
                    break;
            }
        }

        System.out.println(sum); // 输出最小生成树的权值
    }

    // 并查集的查找函数,用于查找节点的根节点
    static int find(int x) {
        if (father[x] == x) // 如果节点的父节点就是它自己,说明它是根节点
            return x;
        return father[x] = find(father[x]); // 否则递归查找父节点,同时进行路径压缩
    }

}

#构建二叉树

前序遍历+中序遍历构建二叉树

快速记忆:

  • 前序的左右指针相遇或者中序的左右指针相遇,则终止。
  • 否则拿到当前前序指针范围内的第一个节点,作为根节点
  • 找到这个节点在中序遍历的位置(index)
  • 接着算出当前中序的左边剩下那部份未处理(leftSize=index-inStart)
  • 然后左节点的部分:中序 inStart = 原来的(inStart),而结束下标则为当前根节点(inEnd = Index),前序的起始下标则在原来基础上右移一位(preStart = preStart+1),终点则是当前右移后的起点加上中序左边剩余部分(preEnd=preStart+1+leftSize)。
  • 右边则是:inStart:index+1,inEnd:不变,preStart:preStart+1+leftSize,preEnd:不变。
java 复制代码
class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;

	TreeNode(int x) {
		val = x;
	}
}


	/**
	 * 根据前序中序构建二叉树
	 * 
	 * @param inorder  中序遍历
	 * @param inStart  中序开始的下标
	 * @param inEnd    中序结束的下标
	 * @param preorder 前序遍历
	 * @param preStart 前序开始的下标
	 * @param preEnd   前序结束的下标
	 * @return
	 */
	private static TreeNode buildTreeByPreAndInHelper(int[] inorder, int inStart, int inEnd, int[] preorder,
			int preStart, int preEnd) {
		System.out.println(preStart);
		if (preStart >= preEnd || inStart >= inEnd) {
			return null;
		}
		// 每次取前序遍历的第一个元素作为根节点
		TreeNode root = new TreeNode(preorder[preStart]);
		System.out.println(root.val + " " + preStart);
		// 从中序遍历中找到当前根节点的下标
		int index;
		for (index = inStart; index < inEnd; index++) {
			if (inorder[index] == root.val) {
				break;
			}
		}
		int leftSize = index - inStart;

		root.left = buildTreeByPreAndInHelper(
		inorder, 
		inStart, 
		index, 
		preorder, 
		preStart + 1, 
		preStart + leftSize+1);

		root.right = buildTreeByPreAndInHelper(
		inorder, 
		index + 1, 
		inEnd, 
		preorder, 
		preStart + 1 + leftSize, 
		preEnd);

		return root;
	}

中序遍历+后序遍历构建二叉树

快速记忆:中序部分下标的变化是是一样的,只不过后序是从后序的右指针位置获取根节点,以及左右节点的指针分别为:

  • 起始指针 ~ 起始指针 + leftSize
  • 起始指针+leftSize ~ 终点指针 - 1(左移)
java 复制代码
	/**
	 * 根据中序后序构建二叉树
	 * 
	 * @param inorder   中序遍历
	 * @param inStart   中序开始的下标
	 * @param inEnd     中序结束的下标
	 * @param postorder 后序遍历
	 * @param postStart 后序开始的下标
	 * @param postEnd   后序结束的下标
	 * @return
	 */
	private static TreeNode buildTreeByInAndPostHelper(int[] inorder, int inStart, int inEnd, int[] postorder,
			int postStart, int postEnd) {
		// 下标越界,则说明没有可处理的节点
		if (inStart >= inEnd || postStart >= postEnd) {
			return null;
		}

		// 每次取后序遍历中的最后一个节点作为根节点
		int rootVal = postorder[postEnd - 1];
		TreeNode root = new TreeNode(rootVal);

		// 在中序遍历中找到根节点的位置,
		int index;
		for (index = inStart; index < inEnd; index++) {
			if (inorder[index] == rootVal) {
				break;
			}
		}

		// 以中序遍历中的根节点位置为分界线,
		// 左边为左子树,右边为右子树

		// 当前根节点的左子树中节点个数
		int leftSize = index - inStart;

		// 递归构建左子树
		root.left = buildTreeByInAndPostHelper(
		inorder, 
		inStart, 
		index,
 		postorder, 
		postStart, 
		postStart + leftSize);

		// 递归构建右子树
		root.right = buildTreeByInAndPostHelper(
		inorder, 
		index + 1, 
		inEnd,
 		postorder, 
		postStart + leftSize,
		postEnd - 1);

		return root;
	}

前序遍历构建二叉搜索树

java 复制代码
private static TreeNode ininSearchTree(int start, int end, int[] preorder) {
	if (start >= end) {
		return null;
	}
	TreeNode root = new TreeNode();
	root.value = preorder[start];

	// 根据二叉搜索树特性,左子树的值比根节点的小,右子树比根节点的大
	// 找到第一个值比根节点大的,它的右边就是右子树部分
	int index;
	for (index = start + 1; index < end; index++) {
		if (root.value < preorder[index]) {
			break;
		}
	}
	root.left = ininSearchTree(start + 1, index, preorder);
	root.right = ininSearchTree(index, end, preorder);
	return root;
}

二叉树遍历

快速记忆:

  • 前:根(打印 val)左右
  • 中:左根(打印 val)右
  • 后:左右根(打印 val)
  • 层:根放队列,然后顺序放左右节点进队列,接下来一趟循环遍历当前队列中所有节点(顺便打印 val),每个节点判断是否有左右节点,有的话继续放进队列,反复执行此操作,直到没有节点需要处理。

前序遍历

java 复制代码
	/**
	 * 打印前序遍历 (根左右)
	 * 
	 * @param root
	 */
	private static void preOrderTraversal(TreeNode root) {
		if (root != null) {
			System.out.print(root.val + " ");
		}
		if (root.left != null) {
			preOrderTraversal(root.left);
		}

		if (root.right != null) {
			preOrderTraversal(root.right);
		}
	}

中序遍历

java 复制代码
	/**
	 * 打印中序遍历 (左根右)
	 * 
	 * @param root
	 */
	private static void inOrderTraversal(TreeNode root) {
		if (root.left != null) {
			inOrderTraversal(root.left);
		}
		if (root != null) {
			System.out.print(root.val + " ");
		}
		if (root.right != null) {
			inOrderTraversal(root.right);
		}
	}

后序遍历

java 复制代码
	/**
	 * 打印后序遍历 (左右根)
	 * 
	 * @param root
	 */
	private static void postOrderTraversal(TreeNode root) {
		if (root.left != null) {
			postOrderTraversal(root.left);
		}
		if (root.right != null) {
			postOrderTraversal(root.right);
		}
		if (root != null) {
			System.out.print(root.val + " ");
		}
	}

层序遍历

java 复制代码
	/**
	 * 打印层序遍历
	 * 
	 * @param root
	 */
	private static void levelOrderTraversal(TreeNode root) {
		if (root == null) {
			return;
		}
		// 利用队列先进先出的特点,先对当前根节点打印,然后接着存放其左右节点
		// 之后每次进来都重新判断其左右节点非空,并对其进行处理
		// 与层序遍历的逻辑相符
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while (!queue.isEmpty()) {
			int size = queue.size();
//	        System.out.println("size的大小为:"+size);
			for (int i = 0; i < size; i++) {
				TreeNode node = queue.poll();
				System.out.print(node.val + " ");
				if (node.left != null) {
					queue.offer(node.left);
				}
				if (node.right != null) {
					queue.offer(node.right);
				}
			}
		}
	}
觉得有用就点个赞,不用登录也能读

评论

0 条
登录 之后才能评论
—
还没有评论,来说第一句