LeetCode、1143. 最长公共子序列【中等,二维DP】
文章目录
- 前言
- LeetCode、1143. 最长公共子序列【中等,二维DP】
- 题目链接与分类
- 思路
- 2022年暑假学习思路及题解
- 二维DP解决
- 资料获取
前言
博主介绍:✌目前全网粉丝2W+,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者、专注于Java后端技术领域。
涵盖技术内容:Java后端、算法、分布式微服务、中间件、前端、运维、ROS等。
博主所有博客文件目录索引:博客目录索引(持续更新)
视频平台:b站-Coder长路
LeetCode、1143. 最长公共子序列【中等,二维DP】
题目链接与分类
题目内容:给定两个字符串str1和str2,输出两个字符串的最长公共子序列。如果最长公共子序列为空,则返回"-1"。目前给出的数据,仅仅会存在一个最长的公共子序列
题目链接:
- 牛客:最长公共子序列(二)
- leetcode:LeetCode、1143. 最长公共子序列
分类:动态规划/二维DP
思路
2022年暑假学习思路及题解
思路:dp+递归。①nxn遍历,来进行计算dp中每个格子的可连接
示例:把思路理清楚了就ok。
"1A2C3D4B56", "B1D23A456A"
结果:123456
下图中每个格子的左边是dp的值,右边红色的是方向数组b的值。左下角包含有思路解决:

复杂度分析:
- 空间复杂度:O(n2)
- 时间复杂度:O(n2)
import java.util.*;public class Solution {private String x;private String y;/*** longest common subsequence* @param s1 string字符串 the string* @param s2 string字符串 the string* @return string字符串*/public String LCS (String s1, String s2) {this.x = s1;this.y = s2;char[] sArr1 = s1.toCharArray();char[] sArr2 = s2.toCharArray();int[][] dp = new int[sArr1.length + 1][sArr2.length + 1];int[][] d = new int[sArr1.length + 1][sArr2.length + 1];for (int i = 1; i <= sArr1.length; i++) {for (int j = 1; j <= sArr2.length; j++) {//比较两个字符if (sArr1[i - 1] == sArr2[j - 1]) {//若是相同dp[i][j] = dp[i - 1][j - 1] + 1;d[i][j] = 1;}else {if (dp[i - 1][j] > dp[i][j - 1]) {dp[i][j] = dp[i - 1][j];d[i][j] = 2;}else {dp[i][j] = dp[i][j - 1];d[i][j] = 3;}}}}String ans = ans(s1.length(), s2.length(), d);if (ans.isEmpty()) {return "-1";}return ans;}//递归获取最长子序列public String ans(int i, int j, int[][] d) {String res = "";if (i == 0 || j == 0) {return res;}if (d[i][j] == 1) {res += ans(i - 1,j - 1, d);res += x.charAt(i - 1);}else if (d[i][j] == 2) {res += ans(i - 1,j, d);}else {res += ans(i, j - 1, d);}return res;}
}
二维DP解决
时间:2024.2.7
题目链接:1143. 最长公共子序列
思路:在本题中是找的最长公共子序列,并不是子串,此时我们可以从选不选的问题上延申出来。
定义:dp(i, j),本身这个值表示第一个字串前i个,第二个字串前j个的最长公共子序列数量。对于当前元素i,j来说,若是当前选不选i或者j,又或者是选i和j,那么是有四种状态的。
dp(i - 1, j):当前i不选,j选,即第一个字串前i-1个,第二个字串前j个中最长公共子序列数量。
dp(i, j - 1):当前i选,j不选,即第一个字串前i个,第二个字串前j-1个中最长公共子序列数量。
dp(i - 1, j - 1):当前i不选,j不选,即第一个字串前i-1个,第二个字串前j-1个中最长公共子序列数量。
dp(i, j)::当前i选,j选,即第一个字串前i个,第二个字串前j个中最长公共子序列数量。
递推方程:从dp(i, j)定值来看,我们是根据第1个子串的第i个字符与第2个子串的第j个字符是否相等来作为条件。
dp(i, j) = Math.max(dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)); 【ch1[i] != ch2[j]】
dp(i, j) = dp(i - 1, j - 1) + 1; 【ch1[i] == ch2[j]】
题解:
复杂度分析:时间复杂度O(n*m);空间复杂度O(n*m)
class Solution {public int longestCommonSubsequence(String text1, String text2) {int n = text1.length(), m = text2.length();int[][] dp = new int[n + 1][m + 1];for (int i = 1; i <= n; i ++) {char text1Ch = text1.charAt(i - 1);for (int j = 1; j <= m; j ++) {char text2Ch = text2.charAt(j - 1);//若是两个字符相等if (text1Ch == text2Ch) {dp[i][j] = dp[i - 1][j - 1] + 1;}else {dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}}}return dp[n][m];}
}

资料获取
大家点赞、收藏、关注、评论啦~
精彩专栏推荐订阅:在下方专栏👇🏻
- 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
- 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
- 学习与生活-专栏:可以了解博主的学习历程
- 算法专栏:算法收录
更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅
整理者:长路 时间:2024.2.7
相关文章:
LeetCode、1143. 最长公共子序列【中等,二维DP】
文章目录 前言LeetCode、1143. 最长公共子序列【中等,二维DP】题目链接与分类思路2022年暑假学习思路及题解二维DP解决 资料获取 前言 博主介绍:✌目前全网粉丝2W,csdn博客专家、Java领域优质创作者,博客之星、阿里云平台优质作者…...
162基于matlab的多尺度和谱峭度算法对振动信号进行降噪处理
基于matlab的多尺度和谱峭度算法对振动信号进行降噪处理,选择信号峭度最大的频段进行滤波,输出多尺度谱峭度及降噪结果。程序已调通,可直接运行。 162 matlab 信号处理 多尺度谱峭度 (xiaohongshu.com)...
Android Studio六大基本布局的概览和每个布局的关键特性以及实例分析
1. 线性布局 (LinearLayout) 描述: 线性布局是一种按指定方向(水平或垂直)排列其子视图的布局容器。通过android:orientation属性可设置为horizontal或vertical。 关键属性: android:orientation: 指定布局方向。android:layout_weight: 子视图权重,用于分配剩余空间。示…...
【go语言】一个简单HTTP服务的例子
一、Go语言安装 Go语言(又称Golang)的安装过程相对简单,下面是在不同操作系统上安装Go语言的步骤: 在Windows上安装Go语言: 访问Go语言的官方网站(golang.org)或者使用国内镜像站点࿰…...
LeetCode Python - 15.三数之和
目录 题目答案运行结果 题目 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k ,同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意:答案中不可…...
C#中implicit和explicit
理解: 使用等号代替构造函数调用的效果以类似重载操作符的形式定义用于类型转换的函数前者类型转换时候直接写等号赋值语法,后者要额外加目标类型的强制转换stirng str -> object o -> int a 可以 int a (int)(str as object)转换通过编译,但没有转换逻辑所以运行会报错…...
探讨java系统中全局唯一ID实现方案
为什么需要全局唯一ID 我们这里引用美团 Leaf 的场景介绍:在复杂分布式系统中,往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中,数据日渐增长,对数据分库分表后需要有一…...
微信小程序(四十四)鉴权组件插槽-登入检测
注释很详细,直接上代码 新增内容: 1.鉴权组件插槽的用法 2.登入检测示范 源码: app.json {"usingComponents": {"auth":"/components/auth/auth"} }app.js App({globalData:{//定义全局变量isLoad:false} })…...
【ES】--ES集成热更新自定义词库(字典)
目录 一、问题描述二、具体实施1、Tomcat实现远程扩展字典2、验证生效3、ES配置远程扩展字典4、为何不重启ES能实现热更新 一、问题描述 问题现象: 前面完成了自定义分词器词库集成到ES中。在实际项目中词库是时刻在变更的,但又不希望重启ES,对此我们应…...
能源管理师——为能源可持续发展护航
能源管理师是在能源管理领域具有专业知识和技能的专业人士,他们的工作对于实现能源的有效利用和可持续发展至关重要。 能源管理师的主要职责是协助企业或组织进行能源管理,包括能源规划、能源审计、节能措施的实施和能源绩效的评估等。他们通过对能源使…...
设计模式理解:单例模式+工厂模式+建设者模式+原型模式
迪米特法则:Law of Demeter, LoD, 最少知识原则LKP 如果两个软件实体无须直接通信,那么就不应当发生直接的相互调用,可以通过第三方转发该调用。其目的是降低类之间的耦合度,提高模块的相对独立性。 所以,在运用迪米特…...
DataX源码分析 writer
系列文章目录 一、DataX详解和架构介绍 二、DataX源码分析 JobContainer 三、DataX源码分析 TaskGroupContainer 四、DataX源码分析 TaskExecutor 五、DataX源码分析 reader 六、DataX源码分析 writer 七、DataX源码分析 Channel 文章目录 系列文章目录前言DataX的Writer写入流…...
为自己的项目媒体资源添加固定高度
为自己的项目媒体资源添加固定高度 未媒体资源添加固定高度,不仅有利于确定懒加载后的切确位置,还可以做骨架屏、loading动画等等,但是因为历史数据中很多没有加高度的媒体资源,所以一直嫌麻烦没有做。 直到这个季度有一个自上而…...
家政小程序系统源码开发:引领智能生活新篇章
随着科技的飞速发展,小程序作为一种便捷的应用形态,已经深入到我们生活的方方面面。尤其在家庭服务领域,家政小程序的出现为人们带来了前所未有的便利。它不仅简化了家政服务的流程,提升了服务质量,还为家政服务行业注…...
多表查询
目录 统计出一张数据表中的数据量 查询 dept 表中的数据量 查询 emp 表中的数据量 实现 emp 与 dept 的多表查询 笛卡尔积 消除笛卡尔积 把数据表 emp 的别名定为 e,数据表 dept 的别名定为 d,然后在查询中分别使用 e 和 d 代替这两个表 Oracle从…...
PHP开发日志 ━━ 深入理解三元操作与一般条件语句的不同
概况 三元运算符的功能与“if…else”流程语句一致。 在一般情况下,三元操作替换if条件语句可以精简代码,并且更为直观,但是在下面的情况中使用三元操作将会返回警告。 借图: 案例 比如原代码: class classA{publ…...
多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测
多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测 目录 多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预…...
vue3-内置组件-Suspense
Suspense (实验性功能) <Suspense> 是一项实验性功能。它不一定会最终成为稳定功能,并且在稳定之前相关 API 也可能会发生变化。 <Suspense> 是一个内置组件,用来在组件树中协调对异步依赖的处理。它让我们可以在组件树上层等待下层的多个嵌…...
Rust入门:如何在windows + vscode中关闭程序codelldb.exe
在windows中用vscode单步调试rust程序的时候,发现无论是按下stop键,还是运行完程序,调试器codelldb.exe一直霸占着主程序不退出,如果此时对代码进行修改,后续就没法再编译调试了。 目前我也不知道要怎么处理这个事&am…...
git错误整理
remote: Support for password authentication was removed on August 13, 2021. 参考:这篇即可 GnuTLS recv error (-110): The TLS connection was non-properly terminated. 执行下面的指令: git config --global http.sslVerify false...
【Oracle APEX开发小技巧12】
有如下需求: 有一个问题反馈页面,要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据,方便管理员及时处理反馈。 我的方法:直接将逻辑写在SQL中,这样可以直接在页面展示 完整代码: SELECTSF.FE…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
376. Wiggle Subsequence
376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...
工程地质软件市场:发展现状、趋势与策略建议
一、引言 在工程建设领域,准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具,正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
嵌入式学习笔记DAY33(网络编程——TCP)
一、网络架构 C/S (client/server 客户端/服务器):由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序,负责提供用户界面和交互逻辑 ,接收用户输入,向服务器发送请求,并展示服务…...
JS手写代码篇----使用Promise封装AJAX请求
15、使用Promise封装AJAX请求 promise就有reject和resolve了,就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...
【SpringBoot自动化部署】
SpringBoot自动化部署方法 使用Jenkins进行持续集成与部署 Jenkins是最常用的自动化部署工具之一,能够实现代码拉取、构建、测试和部署的全流程自动化。 配置Jenkins任务时,需要添加Git仓库地址和凭证,设置构建触发器(如GitHub…...
【Linux手册】探秘系统世界:从用户交互到硬件底层的全链路工作之旅
目录 前言 操作系统与驱动程序 是什么,为什么 怎么做 system call 用户操作接口 总结 前言 日常生活中,我们在使用电子设备时,我们所输入执行的每一条指令最终大多都会作用到硬件上,比如下载一款软件最终会下载到硬盘上&am…...
Docker拉取MySQL后数据库连接失败的解决方案
在使用Docker部署MySQL时,拉取并启动容器后,有时可能会遇到数据库连接失败的问题。这种问题可能由多种原因导致,包括配置错误、网络设置问题、权限问题等。本文将分析可能的原因,并提供解决方案。 一、确认MySQL容器的运行状态 …...
