首页 > 编程语言 >class086 动态规划中得到具体决策方案的技巧【算法】

class086 动态规划中得到具体决策方案的技巧【算法】

时间:2024-01-02 13:36:00浏览次数:47  
标签:技巧 int class086 算法 static import new public dp


class086 动态规划中得到具体决策方案的技巧【算法】

算法讲解086【必备】动态规划中得到具体决策方案的技巧

class086 动态规划中得到具体决策方案的技巧【算法】_java

code1 最长公共子序列

// 最长公共子序列其中一个结果
// 给定两个字符串str1和str2
// 输出两个字符串的最长公共子序列
// 如果最长公共子序列为空,则输出-1
// 测试链接 : https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

dp[i][j]:s1前i个和s2前j个的最长公共子序列
dp[i][j]=dp[i-1][j-1],s1[i]==s2[j]
dp[i][j]=max(dp[i-1][j],dp[i][j-1]

package class086;

// 最长公共子序列其中一个结果
// 给定两个字符串str1和str2
// 输出两个字符串的最长公共子序列
// 如果最长公共子序列为空,则输出-1
// 测试链接 : https://www.nowcoder.com/practice/4727c06b9ee9446cab2e859b4bb86bb8
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;

// 讲解067 - 题目3,最长公共子序列长度
public class Code01_LCS {

	public static int MAXN = 5001;

	public static int[][] dp = new int[MAXN][MAXN];

	public static char[] ans = new char[MAXN];

	public static char[] s1;

	public static char[] s2;

	public static int n, m, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		s1 = br.readLine().toCharArray();
		s2 = br.readLine().toCharArray();
		n = s1.length;
		m = s2.length;
		lcs();
		if (k == 0) {
			out.println(-1);
		} else {
			for (int i = 0; i < k; i++) {
				out.print(ans[i]);
			}
			out.println();
		}
		out.flush();
		out.close();
		br.close();
	}

	public static void lcs() {
		dp();
		k = dp[n][m];
		if (k > 0) {
			for (int len = k, i = n, j = m; len > 0;) {
				if (s1[i - 1] == s2[j - 1]) {
					ans[--len] = s1[i - 1];
					i--;
					j--;
				} else {
					if (dp[i - 1][j] >= dp[i][j - 1]) {
						i--;
					} else {
						j--;
					}
				}
			}
		}
	}

	// 填好dp表
	public static void dp() {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= m; j++) {
				if (s1[i - 1] == s2[j - 1]) {
					dp[i][j] = 1 + dp[i - 1][j - 1];
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
	}

}

code2 1125. 最小的必要团队

// 最小的必要团队
// 作为项目经理,你规划了一份需求的技能清单req_skills
// 并打算从备选人员名单people中选出些人组成必要团队
// 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表
// 所谓必要团队,就是在这个团队中
// 对于所需求的技能列表req_skills中列出的每项技能,团队中至少有一名成员已经掌握
// 请你返回规模最小的必要团队,团队成员用人员编号表示
// 你可以按 任意顺序 返回答案,题目数据保证答案存在
// 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/

把技能转为编码
把每个人的技能转为状态码
考察所有人
分为要第i号人,和不要第i号人

package class086;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

// 最小的必要团队
// 作为项目经理,你规划了一份需求的技能清单req_skills
// 并打算从备选人员名单people中选出些人组成必要团队
// 编号为i的备选人员people[i]含有一份该备选人员掌握的技能列表
// 所谓必要团队,就是在这个团队中
// 对于所需求的技能列表req_skills中列出的每项技能,团队中至少有一名成员已经掌握
// 请你返回规模最小的必要团队,团队成员用人员编号表示
// 你可以按 任意顺序 返回答案,题目数据保证答案存在
// 测试链接 : https://leetcode.cn/problems/smallest-sufficient-team/
public class Code02_SmallestSufficientTeam {

	public static int[] smallestSufficientTeam(String[] skills, List<List<String>> people) {
		int n = skills.length;
		int m = people.size();
		HashMap<String, Integer> map = new HashMap<>();
		int cnt = 0;
		for (String s : skills) {
			// 把所有必要技能依次编号
			map.put(s, cnt++);
		}
		// arr[i] : 第i号人掌握必要技能的状况,用位信息表示
		int[] arr = new int[m];
		for (int i = 0, status; i < m; i++) {
			status = 0;
			for (String skill : people.get(i)) {
				if (map.containsKey(skill)) {
					// 如果当前技能是必要的
					// 才设置status
					status |= 1 << map.get(skill);
				}
			}
			arr[i] = status;
		}
		int[][] dp = new int[m][1 << n];
		for (int i = 0; i < m; i++) {
			Arrays.fill(dp[i], -1);
		}
		int size = f(arr, m, n, 0, 0, dp);
		int[] ans = new int[size];
		for (int j = 0, i = 0, s = 0; s != (1 << n) - 1; i++) {
			// s还没凑齐
			if (i == m - 1 || dp[i][s] != dp[i + 1][s]) {
				// 当初的决策是选择了i号人
				ans[j++] = i;
				s |= arr[i];
			}
		}
		return ans;
	}

	// arr : 每个人所掌握的必要技能的状态
	// m : 人的总数
	// n : 必要技能的数量
	// i : 当前来到第几号人
	// s : 必要技能覆盖的状态
	// 返回 : i....这些人,把必要技能都凑齐,至少需要几个人
	public static int f(int[] arr, int m, int n, int i, int s, int[][] dp) {
		if (s == (1 << n) - 1) {
			// 所有技能已经凑齐了
			return 0;
		}
		// 没凑齐
		if (i == m) {
			// 人已经没了,技能也没凑齐
			// 无效
			return Integer.MAX_VALUE;
		}
		if (dp[i][s] != -1) {
			return dp[i][s];
		}
		// 可能性1 : 不要i号人
		int p1 = f(arr, m, n, i + 1, s, dp);
		// 可能性2 : 要i号人
		int p2 = Integer.MAX_VALUE;
		int next2 = f(arr, m, n, i + 1, s | arr[i], dp);
		if (next2 != Integer.MAX_VALUE) {
			// 后续有效
			p2 = 1 + next2;
		}
		int ans = Math.min(p1, p2);
		dp[i][s] = ans;
		return ans;
	}

}

code3 最长递增子序列 T386911 最长上升子序列输出解

// 最长递增子序列字典序最小的结果
// 给定数组arr,设长度为n
// 输出arr的最长递增子序列
// 如果有多个答案,请输出其中字典序最小的
// 注意这道题的字典序设定(根据提交的结果推论的):
// 每个数字看作是单独的字符,比如120认为比36的字典序大
// 保证从左到右每个数字尽量小
// 测试链接 : https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927
// 测试链接 : https://www.luogu.com.cn/problem/T386911
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

从右看就是最长递减子序列
ends数组,找到以ends[i]开头的递增序列长度

package class086;

// 最长递增子序列字典序最小的结果
// 给定数组arr,设长度为n
// 输出arr的最长递增子序列
// 如果有多个答案,请输出其中字典序最小的
// 注意这道题的字典序设定(根据提交的结果推论的):
// 每个数字看作是单独的字符,比如120认为比36的字典序大
// 保证从左到右每个数字尽量小
// 测试链接 : https://www.nowcoder.com/practice/30fb9b3cab9742ecae9acda1c75bf927
// 测试链接 : https://www.luogu.com.cn/problem/T386911
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.Arrays;

// 讲解072 - 最长递增子序列及其扩展
public class Code03_LIS {

	public static int MAXN = 100001;

	public static int[] nums = new int[MAXN];

	public static int[] dp = new int[MAXN];

	public static int[] ends = new int[MAXN];

	public static int[] ans = new int[MAXN];

	public static int n, k;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			for (int i = 0; i < n; i++) {
				in.nextToken();
				nums[i] = (int) in.nval;
			}
			lis();
			for (int i = 0; i < k - 1; i++) {
				out.print(ans[i] + " ");
			}
			out.println(ans[k - 1]);
		}
		out.flush();
		out.close();
		br.close();
	}

	// nums[...]
	public static void lis() {
		k = dp();
		Arrays.fill(ans, 0, k, Integer.MAX_VALUE);
		for (int i = 0; i < n; i++) {
			if (dp[i] == k) {
				// 注意这里
				// 为什么不用判断直接设置
				// 有讲究,课上重点讲了
				ans[0] = nums[i];
			} else {
				if (ans[k - dp[i] - 1] < nums[i]) {
					// 注意这里
					// 为什么只需要判断比前一位(ans[k-dp[i]-1])大即可
					// 有讲究,课上重点讲了
					ans[k - dp[i]] = nums[i];
				}
			}
		}
	}

	// dp[i] : 必须以i位置的数字开头的情况下,最长递增子序列长度
	// 填好dp表 + 返回最长递增子序列长度
	public static int dp() {
		int len = 0;
		for (int i = n - 1, find; i >= 0; i--) {
			find = bs(len, nums[i]);
			if (find == -1) {
				ends[len++] = nums[i];
				dp[i] = len;
			} else {
				ends[find] = nums[i];
				dp[i] = find + 1;
			}
		}
		return len;
	}

	// ends[有效区]从大到小的
	// 二分的方式找<=num的最左位置
	public static int bs(int len, int num) {
		int l = 0, r = len - 1, m, ans = -1;
		while (l <= r) {
			m = (l + r) / 2;
			if (ends[m] <= num) {
				ans = m;
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		return ans;
	}

}

code4 P1759 通天之潜水

// 潜水的最大时间与方案
// 一共有n个工具,每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限,所以只能背重量不超过m的工具
// 因为力气有限,所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定(根据提交的结果推论的):
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案"1 120"比下标方案"1 2"字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

dp[i][j][k]:[1…n]重量不超过j,阻力不超过k,最大提留事件
要第i件:dp[i-1][j][k]
不用第i件:dp[i-1][j-a[i]][k-b[i]]+c[i]

package class086;

// 潜水的最大时间与方案
// 一共有n个工具,每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限,所以只能背重量不超过m的工具
// 因为力气有限,所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定(根据提交的结果推论的):
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案"1 120"比下标方案"1 2"字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

// 讲解069 - 多维费用背包
// 不做空间压缩的版本
// 无法通过全部测试用例
// 这个题必须做空间压缩
// 空间压缩的实现在Code04_Diving2
public class Code04_Diving1 {

	public static int MAXN = 101;

	public static int MAXM = 201;

	public static int[] a = new int[MAXN];

	public static int[] b = new int[MAXN];

	public static int[] c = new int[MAXN];

	public static int[][][] dp = new int[MAXN][MAXM][MAXM];

	public static String[][][] path = new String[MAXN][MAXM][MAXM];

	public static int m, v, n;

	public static void build() {
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				for (int k = 0; k <= v; k++) {
					dp[i][j][k] = 0;
					path[i][j][k] = null;
				}
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			m = (int) in.nval;
			in.nextToken();
			v = (int) in.nval;
			in.nextToken();
			n = (int) in.nval;
			build();
			for (int i = 1; i <= n; i++) {
				in.nextToken();
				a[i] = (int) in.nval;
				in.nextToken();
				b[i] = (int) in.nval;
				in.nextToken();
				c[i] = (int) in.nval;
			}
			compute();
			out.println(dp[n][m][v]);
			out.println(path[n][m][v]);
		}
		out.flush();
		out.close();
		br.close();
	}

	// 普通版本的多维费用背包
	// 为了好懂先实现不进行空间压缩的版本
	public static void compute() {
		String p2;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= m; j++) {
				for (int k = 0; k <= v; k++) {
					// 可能性1 : 不要i位置的货
					// 先把可能性1的答案设置上
					// 包括dp信息和path信息
					dp[i][j][k] = dp[i - 1][j][k];
					path[i][j][k] = path[i - 1][j][k];
					if (j >= a[i] && k >= b[i]) {
						// 可能性2 : 要i位置的货
						// 那么需要:
						// 背包总重量限制j >= a[i]
						// 背包总阻力限制k >= b[i]
						// 然后选了i位置的货,就可以获得收益c[i]了
						// 可能性2收益 : dp[i-1][j-a[i]][k-b[i]] + c[i]
						// 可能性2路径(p2) : path[i-1][j-a[i]][k-b[i]] + " " + i
						if (path[i - 1][j - a[i]][k - b[i]] == null) {
							p2 = String.valueOf(i);
						} else {
							p2 = path[i - 1][j - a[i]][k - b[i]] + " " + String.valueOf(i);
						}
						if (dp[i][j][k] < dp[i - 1][j - a[i]][k - b[i]] + c[i]) {
							dp[i][j][k] = dp[i - 1][j - a[i]][k - b[i]] + c[i];
							path[i][j][k] = p2;
						} else if (dp[i][j][k] == dp[i - 1][j - a[i]][k - b[i]] + c[i]) {
							if (p2.compareTo(path[i][j][k]) < 0) {
								// 如果可能性2的路径,字典序小于,可能性1的路径
								// 那么把路径设置成可能性2的路径
								path[i][j][k] = p2;
							}
						}
					}
				}
			}
		}
	}

}

code4 P1759 通天之潜水

// 潜水的最大时间与方案
// 一共有n个工具,每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限,所以只能背重量不超过m的工具
// 因为力气有限,所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定(根据提交的结果推论的):
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案"1 120"比下标方案"1 2"字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

package class086;

// 潜水的最大时间与方案
// 一共有n个工具,每个工具都有自己的重量a、阻力b、提升的停留时间c
// 因为背包有限,所以只能背重量不超过m的工具
// 因为力气有限,所以只能背阻力不超过v的工具
// 希望能在水下停留的时间最久
// 返回最久的停留时间和下标字典序最小的选择工具的方案
// 注意这道题的字典序设定(根据提交的结果推论的):
// 下标方案整体构成的字符串保证字典序最小
// 比如下标方案"1 120"比下标方案"1 2"字典序小
// 测试链接 : https://www.luogu.com.cn/problem/P1759
// 请同学们务必参考如下代码中关于输入、输出的处理
// 这是输入输出处理效率很高的写法
// 提交以下的code,提交时请把类名改成"Main",可以直接通过

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;

// 本文件做了空间压缩优化
// 可以通过全部测试用例
public class Code04_Diving2 {

	public static int MAXN = 101;

	public static int MAXM = 201;

	public static int[] a = new int[MAXN];

	public static int[] b = new int[MAXN];

	public static int[] c = new int[MAXN];

	public static int[][] dp = new int[MAXM][MAXM];

	public static String[][] path = new String[MAXM][MAXM];

	public static int m, v, n;

	public static void build() {
		for (int i = 0; i <= m; i++) {
			for (int j = 0; j <= v; j++) {
				dp[i][j] = 0;
				path[i][j] = null;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			m = (int) in.nval;
			in.nextToken();
			v = (int) in.nval;
			in.nextToken();
			n = (int) in.nval;
			build();
			for (int i = 1; i <= n; i++) {
				in.nextToken();
				a[i] = (int) in.nval;
				in.nextToken();
				b[i] = (int) in.nval;
				in.nextToken();
				c[i] = (int) in.nval;
			}
			compute();
			out.println(dp[m][v]);
			out.println(path[m][v]);
		}
		out.flush();
		out.close();
		br.close();
	}

	// 多维费用背包的空间压缩版本
	// 请务必掌握空间压缩技巧
	// 之前的课讲了很多遍了
	public static void compute() {
		String p2;
		for (int i = 1; i <= n; i++) {
			for (int j = m; j >= a[i]; j--) {
				for (int k = v; k >= b[i]; k--) {
					if (path[j - a[i]][k - b[i]] == null) {
						p2 = String.valueOf(i);
					} else {
						p2 = path[j - a[i]][k - b[i]] + " " + String.valueOf(i);
					}
					if (dp[j][k] < dp[j - a[i]][k - b[i]] + c[i]) {
						dp[j][k] = dp[j - a[i]][k - b[i]] + c[i];
						path[j][k] = p2;
					} else if (dp[j][k] == dp[j - a[i]][k - b[i]] + c[i]) {
						if (p2.compareTo(path[j][k]) < 0) {
							path[j][k] = p2;
						}
					}
				}
			}
		}
	}

}

2023-12-22 20:51:34


标签:技巧,int,class086,算法,static,import,new,public,dp
From: https://blog.51cto.com/u_15719556/9068261

相关文章

  • Python编程技能的技巧和建议
    Python是一门强大且灵活的编程语言,但要成为一名精通的Python开发者,需要不断提升自己的编码技巧。本文将介绍15个能够帮助大家提高Python编程技能的技巧和建议,从而让你的键盘飞起,编写更高效和可维护的Python代码。使用列表推导式列表推导式是一种精简创建列表的方式,它可以在一行代......
  • 软件开发算法为王,编程语言各取所好——我看IT圈茶余饭后的“鄙视链”
    IT圈茶余饭后的“鄙视链”IT圈茶余饭后的“鄙视链”,简直就是一场瞬间的情感大戏!“我们写xxx的看不起写xxxx“,无处不见这种互相鄙视的情绪就像一场刺激的游戏,每个人都觉得自己是鄙视链的最顶端。快来看看这个IT圈里的“鄙视链”究竟是怎样的吧!一、书店感受前几天到广西壮族自治区首......
  • 恢复删除的文件:掌握这些技巧,轻松找回丢失的数据
    现代社会中,数据的重要性不言而喻,随着科技的不断发展,我们的工作、生活和学习都越来越依赖电子设备。然而,高度数字化的时代,文件丢失问题时有发生。意外删除、格式化、系统崩溃等都可能导致重要文件丢失,给我们带来许多烦恼和损失。这种情况下,如果能掌握文件恢复方法,将可以及时挽救损失......
  • Linux系统命令和使用技巧
    1、处理特殊的文件名假设Linux系统中有一个文件名叫“-ee”,如果我们想对它进行操作,例如要删除它,按照一般的删除方法在命令行中输入rm-ee命令,界面会提示我们是“无效选项”(invalidoption),原来由于文件名的第一个字符为“-”,Linux把文件名当作选项了,我们可以使用“--”符号来解决这......
  • 【教3妹学编程-算法题】收集足够苹果的最小花园周长
    3妹:“在小小的花园里面挖呀挖呀挖,种小小的种子开小小的花”2哥 :3妹也会唱这首儿歌呀,这首儿歌在五一期间很火啊。3妹:是呀,小朋友们都喜欢唱,我这个200多个月的大朋友也喜欢唱,哈哈2哥 :甜美的歌声加上黄老师甜美的外表,很治愈!3妹:“在特别大的花园里面挖呀挖呀挖,种特别大的种子开......
  • 流行的机器学习算法——线性回归
    线性回归(LinearRegression)是非常流行的机器学习算法。线性回归可以用来确定两种或两种以上变量之间的定量关系。具体来说,线性回归算法可以根据一组样本数据,拟合出一个线性模型,并通过对该模型的参数进行估计和预测,达到对未知数据进行预测的目的。这种算法最常用的技术是最小二乘法(L......
  • 【教3妹学编程-算法题】一年中的第几天
    3妹:“太阳当空照,花儿对我笑,小鸟说早早早,你为什么背上炸药包”2哥 :3妹,什么事呀这么开森。3妹:2哥你看今天的天气多好啊,经过了一周多的寒潮,天气总算暖和些了。2哥:是啊,都说一九二九不出手,三九四九冰上走,这才一九就已经可以冰上走了。3妹:上海这边虽然也挺冷了,但是还算好,想想北方都已经......
  • 代码随想录算法训练营第二十天|654.最大二叉树,617.合并二叉树,700.二叉搜索树中的搜索,9
    一、654.最大二叉树题目链接:LeetCode654.最大二叉树学习:思路:前序遍历方法参数:(int[]nums,intstart,intend)返回类型:TreeNode终止条件:if(end-start==0)returnnull;if(end-start==1)returnnewTreeNode(nums[start]);单层递归逻辑:寻找数组中的最大......
  • Bellman-Ford算法实现带有负权边的单源最短路
    Bellman-Ford算法对于Dijkstra算法,不妨给出这样一个例子graphLRA((A))-->|1|C((C))A-->|2|D((D))D-->|-4|C根据Dijkstra算法的流程,选取A为源点。更新与A邻接的顶点,有C和D。选取已更新顶点中距离A的最小值,显然选择边权为1的边所连接的顶点C,并将C收入最短路集合S中,此......
  • 文心一言 VS 讯飞星火 VS chatgpt (169)-- 算法导论13.2 2题
    二、用go语言,证明:在任何一棵有n个结点的二叉搜索树中,恰有n-1种可能的旋转。文心一言:要证明在任何一棵有n个结点的二叉搜索树中,恰有n-1种可能的旋转,我们可以按照以下步骤逐步推导:二叉搜索树的性质:在二叉搜索树中,任意一个结点的左子树上的所有结点值都小于该结点值,而右子......