当前位置:网站首页>Violent recursion to dynamic programming 06 (the sword refers to Offer II 095. Longest common subsequence)
Violent recursion to dynamic programming 06 (the sword refers to Offer II 095. Longest common subsequence)
2022-08-03 02:33:00 【Taotao can't learn English】
1143.最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度.
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串.
例如,“ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列.两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列.
若这两个字符串没有公共子序列,则返回 0.
示例 1:
输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace”,它的长度为 3.
示例 2:
输入:text1 = “abc”, text2 = “abc”
输出:3
解释:最长公共子序列是 “abc”,它的长度为 3.
示例 3:
输入:text1 = “abc”, text2 = “def”
输出:0
解释:两个字符串没有公共子序列,返回 0.
提示:
- 1 <= text1.length <= 1000
- 1 <= text2.length <= 1000
输入的字符串只含有小写英文字符.
暴力递归
I can't tell,Whoever said it, please say it in the comment area.
public int longestCommonSubsequence(String text1, String text2) {
return getLongLest(text1, text1.length() - 1, text2, text2.length() - 1);
}
private int getLongLest(String text1, int text1Index, String text2Str, int text2tIndex) {
if (text1Index == 0 && text2tIndex == 0) {
//Compares the current bits for equality
return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : 0;
} else if (text1Index == 0) {
//When the left ends, the left does not move more than the right
return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : getLongLest(text1, text1Index, text2Str, text2tIndex - 1);
} else if (text2tIndex == 0) {
//When the right side ends, the right side does not move more than the left side
return text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 : getLongLest(text1, text1Index - 1, text2Str, text2tIndex);
} else {
//都不為0
int p1 = getLongLest(text1, text1Index, text2Str, text2tIndex - 1);
int p2 = getLongLest(text1, text1Index - 1, text2Str, text2tIndex);
//No end is more than the middle
int p3 = text1.charAt(text1Index) == text2Str.charAt(text2tIndex) ? 1 + getLongLest(text1, text1Index - 1, text2Str, text2tIndex - 1) : Integer.MIN_VALUE;
return Math.max(p1, Math.max(p2, p3));
}
}
动态规划
This is much better to say
Initialize the first bit first,相等则为1,否则为0,初始化第一行,用aCompare with each one,相等则为1,Otherwise, the previous number,Why for the previous number?Think for yourself,比如a和a比是1,那a和ab比呢,也是1啊.纵向也一样;
然后从ij1开始比,Because the two are compared to each other,If the current bits are not equal,Take the maximum value from the left and the top,If the current bits are equal,Also and top left + 1 Take the maximum value.That is, the current position is moved one position backward,Naturally use the number at that position + 1 了.
public int longestCommonSubsequence2(String text1, String text2) {
int m = text1.length();
int n = text2.length();
char[] s1 = text1.toCharArray();
char[] s2 = text2.toCharArray();
int[][] dp = new int[m][n];
//first initialization
dp[0][0] = s1[0] == s2[0] ? 1 : 0;
//Row and column initialization
for (int i = 1; i < m; i++) {
dp[i][0] = s1[i] == s2[0] ? 1 : dp[i - 1][0];
}
for (int i = 1; i < n; i++) {
dp[0][i] = s1[0] == s2[i] ? 1 : dp[0][i - 1];
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
int left = dp[i][j - 1];
int up = dp[i - 1][j];
int cur = s1[i] == s2[j] ? 1 + dp[i - 1][j - 1] : 0;
dp[i][j] = Math.max(left, Math.max(up, cur));
}
}
return dp[m - 1][n - 1];
}
边栏推荐
- random.nextint()详解
- 投资的思考
- 236. 二叉树的最近公共祖先
- C语言:链表
- 提高测试覆盖率的四大步骤
- 吴恩达深度学习deeplearning.ai——第一门课:神经网络与深度学习——第一节:深度学习概论
- Auto.js 特殊定位控件方法 不能在ui线程执行阻塞操作,请使用setTimeout代替
- Go高性能之方法接收器 - 指针vs值
- Carefully organize 16 MySQL usage specifications to reduce problems by 80% and recommend sharing with the team
- 可编程逻辑控制器(PLC) : 基础、类型和应用
猜你喜欢
随机推荐
12-security退出.md
JSP第一篇 -----JSP九大内置对象(隐式对象)和四大域对象
绿色版-SQL环境搭建
vue3的keepAlive缓存组件
[NCTF2019]SQLi-1||SQL注入
作业8.2 线程同步互斥机制——互斥锁
线上交流丨稀疏神经网络:实践和理论(青源Talk第23期 汪张扬)
图文详细解决IDEA使用Debug模式启动项目一直转圈圈跑起不来(亲测可以)
8-jwt工具类
面试题 08.07. 无重复字符串的排列组合 ●●
电压传感器: 工作原理、类型及电路图
Auto.js 特殊定位控件方法 不能在ui线程执行阻塞操作,请使用setTimeout代替
php提示Array to string conversion
SAP ABAP OData 服务如何支持修改(Update)操作试读版
流程控制for和while循环语句
GoLang 使用 goroutine 停止的几种办法
49. 字母异位词分组-排序法
中科磁业IPO过会:年营收5.5亿 吴中平家族持股85%
Violence recursion to dynamic programming 08 (pony go chess)
优秀论文以及思路分析02