当前位置: 首页 > news >正文

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的值。左下角包含有思路解决:

image-20220725143004707

复杂度分析:

  • 空间复杂度: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];}
}

image-20240207140554874


资料获取

大家点赞、收藏、关注、评论啦~

精彩专栏推荐订阅:在下方专栏👇🏻

  • 长路-文章目录汇总(算法、后端Java、前端、运维技术导航):博主所有博客导航索引汇总
  • 开源项目Studio-Vue—校园工作室管理系统(含前后台,SpringBoot+Vue):博主个人独立项目,包含详细部署上线视频,已开源
  • 学习与生活-专栏:可以了解博主的学习历程
  • 算法专栏:算法收录

更多博客与资料可查看👇🏻获取联系方式👇🏻,🍅文末获取开发资源及更多资源博客获取🍅


整理者:长路 时间:2024.2.7

相关文章:

LeetCode、1143. 最长公共子序列【中等,二维DP】

文章目录 前言LeetCode、1143. 最长公共子序列【中等&#xff0c;二维DP】题目链接与分类思路2022年暑假学习思路及题解二维DP解决 资料获取 前言 博主介绍&#xff1a;✌目前全网粉丝2W&#xff0c;csdn博客专家、Java领域优质创作者&#xff0c;博客之星、阿里云平台优质作者…...

162基于matlab的多尺度和谱峭度算法对振动信号进行降噪处理

基于matlab的多尺度和谱峭度算法对振动信号进行降噪处理&#xff0c;选择信号峭度最大的频段进行滤波&#xff0c;输出多尺度谱峭度及降噪结果。程序已调通&#xff0c;可直接运行。 162 matlab 信号处理 多尺度谱峭度 (xiaohongshu.com)...

Android Studio六大基本布局的概览和每个布局的关键特性以及实例分析

1. 线性布局 (LinearLayout) 描述: 线性布局是一种按指定方向(水平或垂直)排列其子视图的布局容器。通过android:orientation属性可设置为horizontal或vertical。 关键属性: android:orientation: 指定布局方向。android:layout_weight: 子视图权重,用于分配剩余空间。示…...

【go语言】一个简单HTTP服务的例子

一、Go语言安装 Go语言&#xff08;又称Golang&#xff09;的安装过程相对简单&#xff0c;下面是在不同操作系统上安装Go语言的步骤&#xff1a; 在Windows上安装Go语言&#xff1a; 访问Go语言的官方网站&#xff08;golang.org&#xff09;或者使用国内镜像站点&#xff0…...

LeetCode Python - 15.三数之和

目录 题目答案运行结果 题目 给你一个整数数组 nums &#xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k &#xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请 你返回所有和为 0 且不重复的三元组。 注意&#xff1a;答案中不可…...

C#中implicit和explicit

理解: 使用等号代替构造函数调用的效果以类似重载操作符的形式定义用于类型转换的函数前者类型转换时候直接写等号赋值语法,后者要额外加目标类型的强制转换stirng str -> object o -> int a 可以 int a (int)(str as object)转换通过编译,但没有转换逻辑所以运行会报错…...

探讨java系统中全局唯一ID实现方案

为什么需要全局唯一ID 我们这里引用美团 Leaf 的场景介绍&#xff1a;在复杂分布式系统中&#xff0c;往往需要对大量的数据和消息进行唯一标识。如在美团点评的金融、支付、餐饮、酒店、猫眼电影等产品的系统中&#xff0c;数据日渐增长&#xff0c;对数据分库分表后需要有一…...

微信小程序(四十四)鉴权组件插槽-登入检测

注释很详细&#xff0c;直接上代码 新增内容&#xff1a; 1.鉴权组件插槽的用法 2.登入检测示范 源码&#xff1a; app.json {"usingComponents": {"auth":"/components/auth/auth"} }app.js App({globalData:{//定义全局变量isLoad:false} })…...

【ES】--ES集成热更新自定义词库(字典)

目录 一、问题描述二、具体实施1、Tomcat实现远程扩展字典2、验证生效3、ES配置远程扩展字典4、为何不重启ES能实现热更新 一、问题描述 问题现象: 前面完成了自定义分词器词库集成到ES中。在实际项目中词库是时刻在变更的&#xff0c;但又不希望重启ES&#xff0c;对此我们应…...

能源管理师——为能源可持续发展护航

能源管理师是在能源管理领域具有专业知识和技能的专业人士&#xff0c;他们的工作对于实现能源的有效利用和可持续发展至关重要。 能源管理师的主要职责是协助企业或组织进行能源管理&#xff0c;包括能源规划、能源审计、节能措施的实施和能源绩效的评估等。他们通过对能源使…...

设计模式理解:单例模式+工厂模式+建设者模式+原型模式

迪米特法则&#xff1a;Law of Demeter, LoD, 最少知识原则LKP 如果两个软件实体无须直接通信&#xff0c;那么就不应当发生直接的相互调用&#xff0c;可以通过第三方转发该调用。其目的是降低类之间的耦合度&#xff0c;提高模块的相对独立性。 所以&#xff0c;在运用迪米特…...

DataX源码分析 writer

系列文章目录 一、DataX详解和架构介绍 二、DataX源码分析 JobContainer 三、DataX源码分析 TaskGroupContainer 四、DataX源码分析 TaskExecutor 五、DataX源码分析 reader 六、DataX源码分析 writer 七、DataX源码分析 Channel 文章目录 系列文章目录前言DataX的Writer写入流…...

为自己的项目媒体资源添加固定高度

为自己的项目媒体资源添加固定高度 未媒体资源添加固定高度&#xff0c;不仅有利于确定懒加载后的切确位置&#xff0c;还可以做骨架屏、loading动画等等&#xff0c;但是因为历史数据中很多没有加高度的媒体资源&#xff0c;所以一直嫌麻烦没有做。 直到这个季度有一个自上而…...

家政小程序系统源码开发:引领智能生活新篇章

随着科技的飞速发展&#xff0c;小程序作为一种便捷的应用形态&#xff0c;已经深入到我们生活的方方面面。尤其在家庭服务领域&#xff0c;家政小程序的出现为人们带来了前所未有的便利。它不仅简化了家政服务的流程&#xff0c;提升了服务质量&#xff0c;还为家政服务行业注…...

多表查询

目录 统计出一张数据表中的数据量 查询 dept 表中的数据量 查询 emp 表中的数据量 实现 emp 与 dept 的多表查询 笛卡尔积 消除笛卡尔积 把数据表 emp 的别名定为 e&#xff0c;数据表 dept 的别名定为 d&#xff0c;然后在查询中分别使用 e 和 d 代替这两个表 Oracle从…...

PHP开发日志 ━━ 深入理解三元操作与一般条件语句的不同

概况 三元运算符的功能与“if…else”流程语句一致。 在一般情况下&#xff0c;三元操作替换if条件语句可以精简代码&#xff0c;并且更为直观&#xff0c;但是在下面的情况中使用三元操作将会返回警告。 借图&#xff1a; 案例 比如原代码&#xff1a; class classA{publ…...

多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测

多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测 目录 多维时序 | Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现RF-Adaboost随机森林结合Adaboost多变量时间序列预…...

vue3-内置组件-Suspense

Suspense (实验性功能) <Suspense> 是一项实验性功能。它不一定会最终成为稳定功能&#xff0c;并且在稳定之前相关 API 也可能会发生变化。 <Suspense> 是一个内置组件&#xff0c;用来在组件树中协调对异步依赖的处理。它让我们可以在组件树上层等待下层的多个嵌…...

Rust入门:如何在windows + vscode中关闭程序codelldb.exe

在windows中用vscode单步调试rust程序的时候&#xff0c;发现无论是按下stop键&#xff0c;还是运行完程序&#xff0c;调试器codelldb.exe一直霸占着主程序不退出&#xff0c;如果此时对代码进行修改&#xff0c;后续就没法再编译调试了。 目前我也不知道要怎么处理这个事&am…...

git错误整理

remote: Support for password authentication was removed on August 13, 2021. 参考&#xff1a;这篇即可 GnuTLS recv error (-110): The TLS connection was non-properly terminated. 执行下面的指令&#xff1a; git config --global http.sslVerify false...

Linux 文件类型,目录与路径,文件与目录管理

文件类型 后面的字符表示文件类型标志 普通文件&#xff1a;-&#xff08;纯文本文件&#xff0c;二进制文件&#xff0c;数据格式文件&#xff09; 如文本文件、图片、程序文件等。 目录文件&#xff1a;d&#xff08;directory&#xff09; 用来存放其他文件或子目录。 设备…...

系统设计 --- MongoDB亿级数据查询优化策略

系统设计 --- MongoDB亿级数据查询分表策略 背景Solution --- 分表 背景 使用audit log实现Audi Trail功能 Audit Trail范围: 六个月数据量: 每秒5-7条audi log&#xff0c;共计7千万 – 1亿条数据需要实现全文检索按照时间倒序因为license问题&#xff0c;不能使用ELK只能使用…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

企业如何增强终端安全?

在数字化转型加速的今天&#xff0c;企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机&#xff0c;到工厂里的物联网设备、智能传感器&#xff0c;这些终端构成了企业与外部世界连接的 “神经末梢”。然而&#xff0c;随着远程办公的常态化和设备接入的爆炸式…...

热烈祝贺埃文科技正式加入可信数据空间发展联盟

2025年4月29日&#xff0c;在福州举办的第八届数字中国建设峰会“可信数据空间分论坛”上&#xff0c;可信数据空间发展联盟正式宣告成立。国家数据局党组书记、局长刘烈宏出席并致辞&#xff0c;强调该联盟是推进全国一体化数据市场建设的关键抓手。 郑州埃文科技有限公司&am…...

深度解析:etcd 在 Milvus 向量数据库中的关键作用

目录 &#x1f680; 深度解析&#xff1a;etcd 在 Milvus 向量数据库中的关键作用 &#x1f4a1; 什么是 etcd&#xff1f; &#x1f9e0; Milvus 架构简介 &#x1f4e6; etcd 在 Milvus 中的核心作用 &#x1f527; 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...

Java中栈的多种实现类详解

Java中栈的多种实现类详解&#xff1a;Stack、LinkedList与ArrayDeque全方位对比 前言一、Stack类——Java最早的栈实现1.1 Stack类简介1.2 常用方法1.3 优缺点分析 二、LinkedList类——灵活的双端链表2.1 LinkedList类简介2.2 常用方法2.3 优缺点分析 三、ArrayDeque类——高…...