左神高阶进阶班4 （尼姆博弈问题、k伪进制、递归到动态规划、优先级结合的递归套路、子串的递归套路，子序列的递归套路，动态规划的压缩技巧）

目录

【案例1  尼姆博弈问题】

【题目描述】

【思路解析】

【代码实现】

【案例2   k伪进制问题】

【题目描述】

【思路解析】

【代码实现】

【案例3   最大路径和】

【题目描述】

【思路解析】

【代码实现】

【案例4 优先级的递归套路】

【题目描述】

 【思路解析】

【代码实现】

【案例5  子串的递归套路 动态规划的空间压缩技巧】

【题目描述】

 【思路解析】

【代码实现】

【案例6 子序列的递归问题】

【问题描述】

 【思路解析】

【代码实现】

大家觉得写得可以的话，可以加入QQ群907575059.

【案例1  尼姆博弈问题】

【题目描述】

【思路解析】

异或和 指初始情况下，所有的铜板堆数量的异或和。

如果有1堆铜板，先手必赢，此时异或和不为0.

如果有2堆铜板，（1）两堆铜板数量相同，先手必输，此时异或和为0（2）两堆铜板数量不同，先手必胜，此时异或和不为0.

如果继续下去，我们可以发现我们最后怎么才能赢，就是拿过之后，必须保证异或和为0。当拿空时，异或和也为0。所以可以得出结论，当初始时异或和不为0，先手赢，但是如果硬币异或和不为0，后手赢。

【代码实现】

/*** @ProjectName: study3* @FileName: Ex1* @author:HWJ* @Data: 2023/9/23 16:46* 尼姆博弈问题*/
public class Ex1 {public static void main(String[] args) {}public static void getWin(int[] num){int xor = num[0];for (int i = 1; i < num.length; i++) {xor ^= num[i];}if (xor == 0){System.out.println("后手赢！");}else {System.out.println("先手赢！");}}
}

【案例2   k伪进制问题】

【题目描述】

【思路解析】

k伪进制和k进制的区别就在于它每个位置上必须有值，值的范围在 [1,k]之间，所以有个普遍想法就是先开始每个位置上尽量放1（从右至左），直到放不了了，然后从那个位置开始往右重新填数。

假如将103用7伪进制表示：1 1 1，只能填三个位置，剩下46，然后用这三个位置继续表示46即可。

【代码实现】

package AdvancedPromotion4;import java.util.HashMap;/*** @ProjectName: study3* @FileName: Ex2* @author:HWJ* @Data: 2023/9/23 16:56*/
public class Ex2 {public static void main(String[] args) {char[] chars = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};kConversion(123, chars);}public static void kConversion(int num, char[] chars) {int len = chars.length;HashMap<Integer, Integer> map = new HashMap<>();int max = 0;for (int i = 0; Math.pow(len, i) <= num; i++) {num -= (int) Math.pow(len, i);map.put(i, 1);max = i;}for (int i = max; i >= 0; i--) {int a = num / (int) Math.pow(len, i);num %= (int) Math.pow(len, i);map.put(i, map.get(i) + a);}StringBuilder str = new StringBuilder();for (int i = max; i >= 0; i--) {str.append(chars[map.get(i) - 1]);}System.out.println(str);}}

【案例3   最大路径和】

【题目描述】

【思路解析】

它不一定要达到最右边才会得到它的最长长度，即它可能在二维数组的任一位置得到最长长度。遍历数组每一个位置得到信息（包括没使用能力的最大长度，和使用能力的最大长度）。

但是每个位置又依靠它的左上位置，，左位置，左下位置，则需要使用递归。可以改为记忆化搜索和动态规划的版本。此题因为不存在枚举行为，所以记忆化搜索和动态规划的时间复杂度和空间复杂度相似。

【代码实现】

package AdvancedPromotion4;/*** @ProjectName: study3* @FileName: Ex3* @author:HWJ* @Data: 2023/9/23 20:12*/
public class Ex3 {public static void main(String[] args) {int[][] matrix = {{1, -4, 10}, {3, -2, -1}, {2, -1, 0}, {0, 5, -2}};System.out.println(getMaxLength1(matrix));}public static class Info {public int use;public int no;public Info(int no, int use) {this.use = use;this.no = no;}}// 递归版本public static int getMaxLength1(int[][] matrix) {int res = Integer.MIN_VALUE;for (int j = 0; j < matrix[0].length; j++) {for (int i = 0; i < matrix.length; i++) {Info cur = process1(matrix, i, j);int ans = Math.max(cur.no, cur.use);res = Math.max(ans, res);}}return res;}// 递归版本public static Info process1(int[][] matrix, int i, int j) {if (j == 0) {return new Info(matrix[i][j], -matrix[i][j]);}int preNo = -1;int preUse = -1;Info preLeft = process1(matrix, i, j - 1);if (preLeft.no >= 0) {preNo = preLeft.no;}if (preLeft.use >= 0) {preUse = preLeft.use;}if (i > 0) {Info preUp = process1(matrix, i - 1, j - 1);if (preUp.no >= 0) {preNo = Math.max(preUp.no, preNo);}if (preUp.use >= 0) {preUse = Math.max(preUse, preUp.use);}}if (i < matrix.length - 1) {Info preDown = process1(matrix, i + 1, j - 1);if (preDown.no >= 0) {preNo = Math.max(preDown.no, preNo);}if (preDown.use >= 0) {preUse = Math.max(preUse, preDown.use);}}int use = -1;int no = -1;if (preUse >= 0) {use = preUse + matrix[i][j];}if (preNo >= 0) {no = preNo + matrix[i][j];use = Math.max(use, preNo - matrix[i][j]);}return new Info(no, use);}// 记忆化搜索版本public static int getMaxLength2(int[][] matrix) {int res = Integer.MIN_VALUE;Info[][] map = new Info[matrix.length][matrix[0].length];for (int j = 0; j < matrix[0].length; j++) {for (int i = 0; i < matrix.length; i++) {Info cur = process2(matrix, i, j, map);int ans = Math.max(cur.no, cur.use);res = Math.max(ans, res);}}return res;}// 记忆化搜索版本版本public static Info process2(int[][] matrix, int i, int j, Info[][] map) {if (map[i][j] != null) { // 如果已经得到信息的地方，之间调用之前的信息return map[i][j];}if (j == 0) {map[i][j] = new Info(matrix[i][j], -matrix[i][j]);return map[i][j];}int preNo = -1;int preUse = -1;Info preLeft = process2(matrix, i, j - 1, map);if (preLeft.no >= 0) {preNo = preLeft.no;}if (preLeft.use >= 0) {preUse = preLeft.use;}if (i > 0) {Info preUp = process2(matrix, i - 1, j - 1, map);if (preUp.no >= 0) {preNo = Math.max(preUp.no, preNo);}if (preUp.use >= 0) {preUse = Math.max(preUse, preUp.use);}}if (i < matrix.length - 1) {Info preDown = process2(matrix, i + 1, j - 1, map);if (preDown.no >= 0) {preNo = Math.max(preDown.no, preNo);}if (preDown.use >= 0) {preUse = Math.max(preUse, preDown.use);}}int use = -1;int no = -1;if (preUse >= 0) {use = preUse + matrix[i][j];}if (preNo >= 0) {no = preNo + matrix[i][j];use = Math.max(use, preNo - matrix[i][j]);}map[i][j] = new Info(no, use);return map[i][j];}
}

【案例4 优先级的递归套路】

【题目描述】

 【思路解析】

先用栈实现不含括号的表达式求值，如果遇到运算符，且此时栈顶的运算符不为乘，除，就将运算符之前的数值和运算符加入栈，否则弹出运算符和运算符之前的数值，并且将其和当前数值进行运算后，在再将运算的值和当前运算符加入栈。

实现这个后我们考虑一个信息结构process（str，i）返回两个数值a，b  a表示从i开始到停止地方得到的运算结果，b表示它在哪里停止。遇到右括号或者到边界就停止。

【代码实现】

package AdvancedPromotion4;import java.util.LinkedList;/*** @ProjectName: study3* @FileName: Ex4* @author:HWJ* @Data: 2023/9/23 20:49*/
public class Ex4 {public static void main(String[] args) {String str = "48*((70-65)-43)+8*1";System.out.println(getNum(str));}public static int getNum(String str) {return process(str, 0)[0];}// 将每一个括号里面包含的运算式记作为一个整体进行计算。public static int[] process(String str, int index) {LinkedList<String> list = new LinkedList<>();int num = 0;while (index < str.length() && str.charAt(index) != ')') {if (str.charAt(index) >= '0' && str.charAt(index) <= '9') {num = num * 10 + str.charAt(index) - '0';index++;} else if (str.charAt(index) == '(') {  // 这里遇到左括号int[] ans = process(str, index + 1);index = ans[1] + 1; // 此次运算的结束位置num = ans[0]; // 括号里运算式总体的运算结果。} else { // 遇到运算符addNum(list, num);list.addLast(String.valueOf(str.charAt(index++)));num = 0;}}addNum(list, num);return new int[]{totalNum(list), index};}// 当栈顶运算符为乘或除时，暂时对运算式进行计算。public static void addNum(LinkedList<String> list, int num) {if (!list.isEmpty()) {int cur = 0;String operator = list.pollLast();if (operator.equals("+") || operator.equals("-")) {list.addLast(operator);} else {cur = Integer.valueOf(list.pollLast());num = operator.equals("*") ? num * cur : cur / num;}}list.addLast(String.valueOf(num));}// 处理完后整个栈里只剩下数值和加减运算符public static int totalNum(LinkedList<String> list) {int res = 0;boolean add = true;String cur = null;int num = 0;while (!list.isEmpty()) {cur = list.pollFirst();if (cur.equals("+")) {add = true;}else if(cur.equals("-")){add = false;}else {num = Integer.valueOf(cur);res += add ? num : (-num);}}return res;}
}

【案例5  子串的递归套路 动态规划的空间压缩技巧】

【题目描述】

 【思路解析】

因为子串一定是在字符串中连续的字符子串。两个字符串的最长公共子串可能以str1的任意位置结尾和str2的任意位置结尾，但是因为是公共子串则要求两个的对应位置字符相同，所以如果str1以i结尾和str2以j结尾的公共子串长度取决于str1以i - 1结尾和str2以j - 1结尾的公共子串长度 + 1.（str1以i结尾和str2以j结尾的字符相同）

根据标红的对应关系可知，dp[i][j]只依赖与dp[i-1][j-1]，所以我们可以不必要创建一个二维数组来进行dp。例如如下规则来对动态规划空间进行压缩。

107421
1311853
15141296

以上数字代表优化后的填表技巧，当填3时，我们只记录2，填4时只记录3.将整个表优化为一个变量。

【代码实现】

package AdvancedPromotion4;/*** @ProjectName: study3* @FileName: Ex5* @author:HWJ* @Data: 2023/9/23 21:27*/
public class Ex5 {public static void main(String[] args) {String str1 = "kaaabcFght";String str2 = "ksaaabmFght";System.out.println(getSameLen1(str1, str2));System.out.println(getSameLen2(str1, str2));}public static int getSameLen1(String s1, String s2){int[][] dp = new int[s1.length()][s2.length()];char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int res = 0;for (int i = 0; i < str1.length; i++) {for (int j = 0; j < str2.length; j++) {if (i == 0 || j == 0){if (str1[i] == str2[j]){dp[i][j] = 1;res = Math.max(dp[i][j], res);}}else {if (str1[i] == str2[j]){dp[i][j] = dp[i - 1][j - 1] + 1;res = Math.max(dp[i][j], res);}}}}return res;}public static String  getSameLen2(String s1, String s2){int len = 0;char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int max = 0;int end = 0;int row = 0;int col = s2.length() - 1;while (row < s1.length()){len = 0;int i = row;int j = col;while (i < s1.length() && j < s2.length()){if (str1[i] == str2[j]){len++;if (len > max){max = len;end = i;}}else {len = 0;}i++;j++;}if (col > 0){col--;}else {row++;}}return s1.substring(end - max + 1, end + 1);}
}

【案例6 子序列的递归问题】

【问题描述】

 【思路解析】

因为子串一定是在字符串中满足原顺序的字符序列，可以不连续。

所以对任意dp[i][j]表示以i位置结尾的str1，表示以j位置结尾的str2的两个子串上最长公共子序列的长度。

对于这个最长公共子序列有4种可能性：

（1）最长公共子序列包含i位置，包含j位置。

（2）最长公共子序列不包含i位置，包含j位置。

（3）最长公共子序列包含i位置，不包含j位置。

（4）最长公共子序列不包含i位置，不包含j位置。

【代码实现】

package AdvancedPromotion4;/*** @ProjectName: study3* @FileName: Ex6* @author:HWJ* @Data: 2023/9/23 22:04*/
public class Ex6 {public static void main(String[] args) {String str1 = "kaaabcFght";String str2 = "ksaaabmFght";System.out.println(getSameLen(str1, str2));}public static int getSameLen(String s1, String s2){int[][] dp = new int[s1.length()][s2.length()];char[] str1 = s1.toCharArray();char[] str2 = s2.toCharArray();int res = 0;for (int i = 0; i < str1.length; i++) {for (int j = 0; j < str2.length; j++) {if (i == 0 && j == 0){if (str1[i] == str2[j]){dp[i][j] = 1;res = dp[i][j];}}else {if (i == 0){dp[i][j] = dp[i][j - 1];res = Math.max(dp[i][j], res);}else if(j == 0){dp[i][j] = dp[i - 1][j];res = Math.max(dp[i][j], res);}else {int p1 = dp[i][j - 1];int p2 = dp[i - 1][j];int p3 = dp[i - 1][j - 1] + (str1[i] == str2[j] ? 1 : 0);dp[i][j] = Math.max(p1, Math.max(p2, p3));res = Math.max(dp[i][j], res);}}}}return res;}
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/139768.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

黑马JVM总结（二十三）

黑马JVM总结（二十三）

&#xff08;1&#xff09;字节码指令-init 方法体内有一些字节&#xff0c;对应着将来要由java虚拟机执行方法内的代码&#xff0c;构造方法里5个字节代码&#xff0c;main方法里有9个字节的代码 java虚拟机呢内部有一个解释器&#xff0c;这个解释器呢可以识别平台无关的字…
阅读更多...
整合车辆出险报告Api接口，轻松管理车险理赔！

整合车辆出险报告Api接口，轻松管理车险理赔！

随着车辆保有量的不断增加&#xff0c;车辆出险的情况也越来越普遍。对于车主来说&#xff0c;如何高效地管理车险理赔&#xff0c;处理保险事故是非常重要的。这时候我们就可以借助整合车辆出险报告API接口&#xff0c;实现快速定位理赔信息&#xff0c;轻松管理车险理赔。 一…
阅读更多...
MongoDB（一） windows 和 linux 之 Ubuntu 安装

MongoDB（一） windows 和 linux 之 Ubuntu 安装

数据库分类 一、关系型数据库&#xff08;RDBMS&#xff09; mysql 、Oracle、DB2、SQL Server 关系数据库中全都是表 二、非关系型数据库&#xff08;NO SQL&#xff09; MongoDB、Redis 键值对数据库 文档数据库MongoDB 下载 mongoDB https://www.mongodb.com/try/downloa…
阅读更多...
自动化测试的定位及一些思考

自动化测试的定位及一些思考

大家对自动化的理解&#xff0c;首先是想到Web UI自动化&#xff0c;这就为什么我一说自动化&#xff0c;公司一般就会有很多人反对&#xff0c;因为自动化的成本实在太高了&#xff0c;其实自动化是分为三个层面的&#xff08;UI层自动化、接口自动化、单元测试&#xff09;&a…
阅读更多...
【论文写作】符号：矩阵、向量的乘法、内积、点积等

【论文写作】符号：矩阵、向量的乘法、内积、点积等

【论文写作】符号&#xff1a;矩阵、向量乘法、内积、点积等 文章目录 【论文写作】符号&#xff1a;矩阵、向量乘法、内积、点积等1. 矩阵乘法1.1 矩阵乘积1.2 矩阵哈德玛乘积1.3 矩阵克罗内克积 2. 向量乘法2.1 向量点积、内积2.2 向量Hadamard积2.3 向量外积2.4 向量叉积 1.…
阅读更多...
[论文笔记]Prefix Tuning

[论文笔记]Prefix Tuning

引言 今天带来微调LLM的第二篇论文笔记Prefix-Tuning。 作者提出了用于自然语言生成任务的prefix-tuning(前缀微调)的方法，固定语言模型的参数而优化一些连续的任务相关的向量，称为prefix。受到了语言模型提示词的启发，允许后续的token序列注意到这些prefix，当成虚拟toke…
阅读更多...
Go的error接口

Go的error接口

从本书的开始&#xff0c;我们就已经创建和使用过神秘的预定义error类型&#xff0c;而且没有解释它究竟是什么。实际上它就是interface类型&#xff0c;这个类型有一个返回错误信息的单一方法&#xff1a; type error interface { Error() string } 创建一个error最简单的方…
阅读更多...
高效查询大量快递信息，轻松掌握技巧

高效查询大量快递信息，轻松掌握技巧

在如今快节奏的生活中&#xff0c;快递已经成为我们日常不可或缺的一部分。然而&#xff0c;对于一些忙碌的人来说&#xff0c;单个查询每一个快递单号可能会浪费太多时间。因此&#xff0c;我们需要一款可以帮助我们批量查询快递的软件。 在市场上&#xff0c;有很多款专门用于…
阅读更多...
网络知识——局域网和交换机

网络知识——局域网和交换机

定义&#xff1a; 局域网&#xff08;Local Area Network&#xff0c;简称LAN&#xff09;是指在某一区域内由多台计算机互联成的计算机组。广域网&#xff08;Wide Area Network&#xff0c;简称WAN&#xff09;是指跨越单个建筑物或大型园区&#xff0c;连接分布在特定地理区…
阅读更多...
面向嵌入式系统的轻量级框架分析

面向嵌入式系统的轻量级框架分析

mr-library简介 mr-library 是一个面向嵌入式系统的轻量级框架&#xff0c;提供统一的底层驱动设备模型以及基础服务功能&#xff0c;具有模块化设计、可配置性和扩展性的特点&#xff0c; 可帮助开发者快速构建嵌入式应用程序。 mr-library 框架支持互斥锁、对象管理等基础内…
阅读更多...
Aqs独占/共享模式

Aqs独占/共享模式

独占锁和共享锁的概念 独占锁也叫排他锁&#xff0c;是指该锁一次只能被一个线程所持有。如果线程T对数据A加上排他锁后&#xff0c;则其他线程不能再对A加任何类型的锁。获得排它锁的线程即能读数据又能修改数据。 共享锁是指该锁可被多个线程所持有。如果线程T对数据A加上共…
阅读更多...
Flume最简单使用

Flume最简单使用

文章目录 一、简介1、定义2、基础架构 二、快速入门1、解压Flume2、案例一&#xff1a;监控端口号3、案例二&#xff1a;将空目录下文件 三、Flume进阶1、Flume事务2、Flume Agent内部原理3、案例一&#xff1a;监控日志4、案例二&#xff1a;多路复用和拦截器适应4.1 原理4.2 …
阅读更多...
Linux 操作技巧

Linux 操作技巧

目录 一、shell-命令解释器 二、Linux中的特殊符号 三、命令历史--history 一、shell-命令解释器 shell——壳&#xff0c;命令解释器&#xff0c;负责解析用户输入的命令 ——内置命令&#xff08;shell内置&#xff09; ——外置命令&#xff0c;在文件系统的某个目录下&…
阅读更多...
【学习草稿】背包问题

【学习草稿】背包问题

一、01背包问题 图解详细解析 &#xff08;转载&#xff09; https://blog.csdn.net/qq_37767455/article/details/99086678 &#xff1a;Vi表示第 i 个物品的价值&#xff0c;Wi表示第 i 个物品的体积&#xff0c;定义V(i,j)&#xff1a;当前背包容量 j&#xff0c;前 i 个物…
阅读更多...
2010-2017年WIND分省政府性债务余额面板数据

2010-2017年WIND分省政府性债务余额面板数据

2010-2017年WIND分省政府性债务余额面板数据 1、时间&#xff1a;2010-2017年 2、指标&#xff1a;债务余额 3、范围&#xff1a;30个省 4、来源&#xff1a;wind 5、指标解释&#xff1a;地方政府债务分为一般债务和专项债务。 一般债务对应的是一般公共预算&#xff0c…
阅读更多...
方案：浅析利用AI智能识别与视频监控技术打造智慧水产养殖监管系统

方案：浅析利用AI智能识别与视频监控技术打造智慧水产养殖监管系统

一、方案背景 针对目前水产养殖集约、高产、高效、生态、安全的发展需求&#xff0c;基于智能传感、智慧物联网、人工智能、视频监控等技术打造智慧水产系统&#xff0c;成为当前行业的发展趋势。传统的人工观察水产养殖方式较为单一&#xff0c;难以及时发现人员非法入侵、偷…
阅读更多...
跨域问题解决方案（三种）

跨域问题解决方案（三种）

Same Origin Policy同源策略&#xff08;SOP&#xff09; 具有相同的Origin&#xff0c;也即是拥有相同的协议、主机地址以及端口。一旦这三项数据中有一项不同&#xff0c;那么该资源就将被认为是从不同的Origin得来的&#xff0c;进而不被允许访问。 Cross-origin resource…
阅读更多...
SpringBean的生命周期

SpringBean的生命周期

SpringBean的生命周期 SperingBean的生命周期是从Bean实例化之后&#xff0c;即通过反射创建出对象之后&#xff0c;到Bean成为一个完整对象&#xff0c;最终存储到单例池中&#xff0c;这个过程被称为Spring Bean的生命周期。Spring Bean的生命周期大体上分为三个阶段 Bean的…
阅读更多...
Win7开启触摸键盘方法

Win7开启触摸键盘方法

在Win7系统中&#xff0c;自带有触摸屏幕键盘&#xff0c;能够在屏幕上显示虚拟键盘&#xff0c;让用户可以用指针设备或触屏等进行输入操作&#xff0c;那么Win7系统怎么开启触摸键盘呢&#xff1f;想知道的小伙伴可以跟着我一起来学习一下。 1、首先打开Win7系统的开始菜单&a…
阅读更多...
小程序中如何查看会员的访问记录

小程序中如何查看会员的访问记录

​在小程序中&#xff0c;我们可以通过如下方式来查看会员的访问记录。下面是具体的操作流程&#xff1a; 1. 找到指定的会员卡。在管理员后台->会员管理处&#xff0c;找到需要查看访客记录的会员卡。也支持对会员卡按卡号、手机号和等级进行搜索。 2. 查看会员卡详情。点…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023