当前位置:网站首页>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];
}
边栏推荐
猜你喜欢
智能合约安全-可重入攻击(SW107-Reentrancy)
Greenplum数据库故障分析——can not listen port
Auto.js special positioning control method cannot perform blocking operations on the ui thread, please use setTimeout instead
在表格数据上,为什么基于树的模型仍然优于深度学习?
从一文中了解SSRF的各种绕过姿势及攻击思路
作业8.2 线程同步互斥机制——互斥锁
机电设备制造企业,如何借助ERP系统做好客供料管理?
文树勋率长沙市人大常委会主任会议成员莅临麒麟信安调研数字经济发展情况
吴恩达深度学习deeplearning.ai——第一门课:神经网络与深度学习——第一节:深度学习概论
SAP ABAP Gateway Client 里 OData 测试的 PUT, PATCH, MERGE 请求有什么区别
随机推荐
Last Common Ancestor (LCA) Study Notes | P3379 【Template】Least Common Ancestor (LCA) Problem Solution
30岁测试开发年薪不足80万,还要被面试官diss混得太差?
【图像分类】2021-EfficientNetV2 CVPR
一个人的精力
从 npm 切换到 pnpm,真香!
js显示隐藏手机号
GoLang 使用 goroutine 停止的几种办法
【TypeScript笔记】01 - TS初体验 && TS常用类型
【深度学习】基于tensorflow的小型物体识别训练(数据集:CIFAR-10)
软件测试从业多年,自认为技术不错,裸辞:一晃 ,失业3个月了~
ASP.NET网络版进销存管理系统源码【源码免费分享】
fifa将采用半自动越位技术计算进球
flutter 每个要注意的点
random.nextint()详解
alibaba数据同步组件canal的实践整理
淘宝商品销量接口/淘宝商品销量监控接口/商品累计销量接口代码对接分享
暴力递归到动态规划 08(小马走象棋)
【SQL】—数据库操作、表操作
OpenWRT设置ipv6网络
[NCTF2019]SQLi-1||SQL注入