1143. 最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。
一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
- 例如,
"ace"是"abcde"的子序列,但"aec"不是"abcde"的子序列。
两个字符串的 公共子序列 是这两个字符串所共同拥有的子序列。
示例 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, text2.length <= 1000text1和text2仅由小写英文字符组成。
总结:如果需要确定 保证某种次序,就需要确定以....结尾的序列。
//如果 许需要保证 答案序列 需要维持 顺序,只要符合条件就可以加进去的。定义为 在0-i区间的字符串是否符合。
class Solution {
public:int longestCommonSubsequence(string text1, string text2) {//求递增序列的时候,因为要求序列有序,所以必须确定序列最后一个元素的值,才能比较新加入序列的元素是不是递增的。求相等序列的时候,如果求连续相等子序列,则还是要确定序列最后一个元素的值;但是本题求的是不必连续的相等子序列,就不需要知道序列最后一个元素的值,只要知道范围内相等的序列长度就行,新来的相等元素可以直接加在序列后面。//dp[i][j]:长度为0- i-1 的text1的字符串 和 长度为0- j-1的text2字符串的最长公共子序列长度为 dp[i][j] 还是从1开始,方便初始化//递推关系:如果 t1[i-1] == t2[i-1] 那么 dp[i][j] = dp[i-1][j-1]+1;//如果 != 那么 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。继承t1的上一个 和t2的上一个 的最大值 t1 = abcde // t2 = ace c和e不相等,那么可以从 t1中的 abc 和 t2的ac找。也可以从t2的ace 和 t1中的 ac找//初始化:考虑 dp[i][0] dp[0][j] 0-1已经越界了,可以理解为t1字符串 和空字符串的交集为0。所以第一行和第一列都为0。因此其他所有行都可以为0,因为会被覆盖vector<vector<int>>dp(text1.size()+1,vector<int>(text2.size()+1,0));for(int i = 1;i <= text1.size();i++){for(int j = 1;j <= text2.size();j++){if(text1[i-1] == text2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;}else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);}}return dp[text1.size()][text2.size()];}
};
相关文章:
1143. 最长公共子序列
给定两个字符串 text1 和 text2,返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ,返回 0 。 一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以…...
EASYEXCEL(一)
1.读取excel 读监听器 Slf4j public class StudentReadListener extends AnalysisEventListener<Student> {// 每读一样,会调用该invoke方法一次Overridepublic void invoke(Student data, AnalysisContext context) {System.out.println("data "…...
竞赛YOLOv7 目标检测网络解读
文章目录 0 前言1 yolov7的整体结构2 关键点 - backbone关键点 - head3 训练4 使用效果5 最后 0 前言 世界变化太快,YOLOv6还没用熟YOLOv7就来了,如果有同学的毕设项目想用上最新的技术,不妨看看学长的这篇文章,学长带大家简单的…...
第一类曲线积分@对弧长的曲线积分
文章目录 abstract对弧长的曲线积分曲线形构件的质量第一类曲线积分曲线积分存在性利用曲线积分的定义描述曲线形构件质量问题推广曲线积分可加性闭曲线积分 曲线积分性质曲线积分的计算方法证明(部分推导) 小结曲线弧显函数形式方程下的曲线积分公式推广例例例 abstract 在积…...
【TypeScript】常见数据结构与算法(二):链表
文章目录 链表结构(LinkedList)链表以及数组的缺点数组链表的优势 什么是链表?封装链表相关方法源码链表常见面试题237-删除链表中的节点206 - 反转链表 数组和链表的复杂度对比 链表结构(LinkedList) 链表以及数组的缺点 链表…...
原型模式 (Prototype Pattern)
定义: 原型模式(Prototype Pattern)是一种创建型设计模式,它用于创建重复的对象,同时保持性能。这种模式的核心思想是通过复制一个已存在的实例来创建新的实例,而不是新建实例并对其进行初始化。原型模式适…...
项目总结报告(案例模板)
软件项目总结报告模板套用: 项目概要项目工作分析经验与教训改进建议可纳入的项目过程资产 --------进主页获取更多资料-------...
C++ Qt QByteArray用法介绍
作者:令狐掌门 技术交流QQ群:675120140 csdn博客:https://mingshiqiang.blog.csdn.net/ 文章目录 一、QByteArray的基本用法1、初始化和赋值2、访问和修改元素3、 常用方法4、数据转换二、QByteArray与文件操作三、QByteArray与网络编程四、QByteArray数据编码1、Base64 编解…...
蓝桥杯物联网竞赛_STM32L071_3_Oled显示
地位: 对于任何一门编程语言的学习,print函数毫无疑问是一种最好的调试手段,调试者不仅能通过它获取程序变量的运行状态而且通过对其合理使用获取程序的运行流程,更能通过关键变量的输出帮你验证推理的正确与否,朴素的…...
python-opencv轮廓检测(外轮廓检测和全部轮廓检测,计算轮廓面积和周长)
python-opencv轮廓检测(外轮廓检测和全部轮廓检测,计算轮廓面积和周长) 通过cv2.findContours,我们可以进行轮廓检测,当然也有很多检测模式,我们可以通过选择检测模式,进行外轮廓检测ÿ…...
LeetCode [简单] 1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回…...
C++设计模式之工厂模式(下)——抽象工厂模式
抽象工厂模式 介绍示例示例使用运行结果抽象工厂模式的优缺点优点缺点 总结 介绍 抽象工厂模式是一种创建型设计模式,它提供了一种封装一组相关或相互依赖对象的方式,而无需指定它们具体的类。它允许客户端使用抽象接口来创建一系列相关的对象ÿ…...
2023亚太杯数学建模A题思路分析 - 采果机器人的图像识别技术
1 赛题 问题A 采果机器人的图像识别技术 中国是世界上最大的苹果生产国,年产量约为3500万吨。与此同时,中国也是世 界上最大的苹果出口国,全球每两个苹果中就有一个,全球超过六分之一的苹果出口 自中国。中国提出了一带一路倡议…...
关于Flink的旁路缓存与异步操作
1. 旁路缓存 1. 什么是旁路缓存? 将数据库中的数据,比较经常访问的数据,保存起来,以减少和硬盘数据库的交互 比如: 我们使用mysql时 经常查询一个表 , 而这个表又一般不会变化,就可以放在内存中,查找时直接对内存进行查找,而不需要再和mysql交互 2. 旁路缓存例子使用 dim层…...
MyBatis-Plus的分页插件和乐观锁插件
MyBatis-Plus: 探索分页查询和乐观锁插件 在现代的Web应用开发中,高效的数据处理是不可或缺的一部分。MyBatis-Plus,作为MyBatis的增强版,提供了多种插件来简化和优化数据库操作。在这篇博客中,我们将重点介绍两个非常实用的插件…...
批量将本地N个英文Html文档进行中文翻译-操作篇
Unity3D特效百例案例项目实战源码Android-Unity实战问题汇总游戏脚本-辅助自动化Android控件全解手册再战Android系列Scratch编程案例软考全系列Unity3D学习专栏蓝桥系列ChatGPT和AIGC 👉关于作者 专注于Android/Unity和各种游戏开发技巧,以及各种资源分…...
解决cad找不到vcruntime140.dll的方法,实测有效的5个的方法
最近,我在使用CAD软件时遇到了一个困扰我已久的问题:由于找不到vcruntime140.dll文件而导致CAD无法正常运行。经过一番努力和尝试,我终于找到了解决这个问题的方法。那么,如何解决vcruntime140.dll丢失的问题呢?本文将…...
2023亚太杯数学建模C题:我国新能源电动汽车的发展趋势,思路模型代码
问题C 我国新能源电动汽车的发展趋势 赛题思路:获取思路见文末名片,第一时间更新 新能源汽车是指以先进技术原理、新技术、新结构的非常规汽车燃料为动力来源( 非常规汽车燃料指汽油、柴油以外的燃料),将先进技术进行汽车动力控制…...
英语学习-爆破音
英文爆破音有:[p],[b],[t],[d],[k],[g]。 同时爆破音的发音会根据前后音的不同,发音不同,具体如下: ⒈ [p],[b],[t],[d],[k],[g] 中的任何两个音素相邻时,前面的发不完全爆破音,后面的就要完全地爆破。如…...
【Vue】图片切换
上一篇: vue的指令 https://blog.csdn.net/m0_67930426/article/details/134599378?spm1001.2014.3001.5502 本篇所需要的指令有: v-on v-bind v-show <!DOCTYPE html> <html lang"en"> <head><meta charset"…...
java_网络服务相关_gateway_nacos_feign区别联系
1. spring-cloud-starter-gateway 作用:作为微服务架构的网关,统一入口,处理所有外部请求。 核心能力: 路由转发(基于路径、服务名等)过滤器(鉴权、限流、日志、Header 处理)支持负…...
边缘计算医疗风险自查APP开发方案
核心目标:在便携设备(智能手表/家用检测仪)部署轻量化疾病预测模型,实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练
前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1):从基础到实战的深度解析-CSDN博客,但实际面试中,企业更关注候选人对复杂场景的应对能力(如多设备并发扫描、低功耗与高发现率的平衡)和前沿技术的…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...
Neo4j 集群管理:原理、技术与最佳实践深度解析
Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...
C++中string流知识详解和示例
一、概览与类体系 C 提供三种基于内存字符串的流,定义在 <sstream> 中: std::istringstream:输入流,从已有字符串中读取并解析。std::ostringstream:输出流,向内部缓冲区写入内容,最终取…...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
