【动态规划-最长公共子序列(LCS)】【hard】力扣1092. 最短公共超序列
给你两个字符串 str1 和 str2,返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个,则可以返回满足条件的 任意一个 答案。
如果从字符串 t 中删除一些字符(也可能不删除),可以得到字符串 s ,那么 s 就是 t 的一个子序列。
示例 1:
输入:str1 = “abac”, str2 = “cab”
输出:“cabac”
解释:
str1 = “abac” 是 “cabac” 的一个子串,因为我们可以删去 “cabac” 的第一个 "c"得到 “abac”。
str2 = “cab” 是 “cabac” 的一个子串,因为我们可以删去 “cabac” 末尾的 “ac” 得到 “cab”。
最终我们给出的答案是满足上述属性的最短字符串。
示例 2:
输入:str1 = “aaaaaaaa”, str2 = “aaaaaaaa”
输出:“aaaaaaaa”
提示:
1 <= str1.length, str2.length <= 1000
str1 和 str2 都由小写英文字母组成。
class Solution {
public:string shortestCommonSupersequence(string str1, string str2) {int m = str1.size(), n = str2.size();vector<vector<int>> dp(m+1, vector<int>(n+1));for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {if (str1[i - 1] == str2[j - 1]) {// 如果当前字符相等,则在前一个 LCS 的基础上加 1dp[i][j] = dp[i - 1][j - 1] + 1;} else {// 否则,取前一个状态的最大值dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}int i = str1.size();int j = str2.size();string result = "";// 通过回溯 dp 数组来构建resultwhile (i > 0 && j > 0) {if (str1[i - 1] == str2[j - 1]) {// 如果字符相等,则是 result 的一部分result = str1[i - 1] + result;i--;j--;} else if (dp[i - 1][j] > dp[i][j - 1]) {// 如果字符不等,加入 str1 的字符result = str1[i - 1] + result;i--;} else {// 或者加入 str2 的字符result = str2[j - 1] + result;j--;}}while (i > 0) {result = str1[i - 1] + result;i--;}while (j > 0) {result = str2[j - 1] + result;j--;}return result;}
};
时间复杂度:O(n×m)
空间复杂度:O(n×m)
这道题的思路是先找到最短公共子序列LCS,然后我们知道了最短公共子序列后,就可以进而根据str1和str2还有dp进行回溯来构建出最短公共超序列result。
这道题的前面部分就是在求关于LCS的dp数组,可以参考模板力扣1143(主页有)。
这道题的难点我觉得是在回溯dp来构建result上面。
根据题目给的例子:
我们定义两个指针i和j分别指向str1和str2的最后一个元素。
当两个元素相等的时候,说明他们是LCS的一部分,所以将这个元素推入result中,由于str1和str2都包含这个元素,所以i和j都要-1。
当两个元素不相等的时候,我们就要将较不容易影响LCS的字符推入到result中,比如dp[i - 1][j] > dp[i][j - 1],也就是str[i-1]相对str[j-1]从字符串推入到result后,能尽可能保证剩下的字符串的LCS尽可能的大。
举个例子:
输入:str1 = “abac”, str2 = “cab”
在第一次判断的过程中,指针i指向str1的c,指针j指向str2的b,由于str1和str2的LCS是ab,那么b作为LCS的一部分,那么推入b就会影响到LCS(如果推入b后,那么构造LCS就没有意义,构造LCS的目的是让指针在都指向LCS的部分的时候,可以只推入一个元素,然后同时让i和j都-1)。所以我们推入c到result。
然后我们还要处理剩余部分,当某个字符串遍历完后,那么还会有一个字符串没有将元素推入到result中,这时候我们遍历完这个没遍历完的字符串,将其剩余部分推入result。
相关文章:
【动态规划-最长公共子序列(LCS)】【hard】力扣1092. 最短公共超序列
给你两个字符串 str1 和 str2,返回同时以 str1 和 str2 作为 子序列 的最短字符串。如果答案不止一个,则可以返回满足条件的 任意一个 答案。 如果从字符串 t 中删除一些字符(也可能不删除),可以得到字符串 s &#x…...
图片编辑为底片,智能工具助力,创作精彩视觉作品
在当今数字化时代,图像编辑已成为表达创意和美化视觉作品的重要手段。借助智能工具,即使是初学者也能轻松驾驭图片编辑。接下为大家展示图片编辑为底片图片的效果。 1.打开“首助编辑高手”,选择这里“图片批量处理”版块页面上 2.导入保存有…...
机器学习/数据分析--用通俗语言讲解时间序列自回归(AR)模型,并用其预测天气,拟合度98%+
时间序列在回归预测的领域的重要性,不言而喻,在数学建模中使用及其频繁,但是你真的了解ARIMA、AR、MA么?ACF图你会看么?? 时间序列数据如何构造???,我打过不少…...
回溯算法之值子集和问题详细解读(附带Java代码解读)
子集和问题(Subset Sum Problem) 是一个经典的组合优化问题。问题可以这样描述: 给定一个整数集合和一个目标整数 target,我们需要从集合中选出若干个整数,使它们的和等于 target。如果这样的子集存在,返回…...
mysql游标的使用
说明: 虽然我们也可以通过筛选条件 WHERE 和 HAVING,或者是限定返回记录的关键字 LIMIT 返回一条记录,但是,却无法在结果集中像指针一样,向前定位一条记录、向后定位一条记录,或者是 随意定位到某一条记录 …...
linux udev详解
1.概念介绍 1.1sysfs文件系统 Linux 2.6以后的内核引入了sysfs文件系统,sysfs被看成是与proc、devfs和devpty同类别的文件系统,该文件系统是一个虚拟的文件系统,它可以产生一个包括所有系统硬件的层级视图,与提供进程和状态信息…...
EventSource和websocket该用哪种技术
EventSource(也称为Server-Sent Events, SSE)和WebSocket都是实现实时通信的技术,但是它们的设计目的和使用场景有所不同。在选择使用哪种技术时,需要根据具体的应用需求来决定。下面是一些关键点,可以帮助你做出选择&…...
通信工程学习:什么是三网融合
三网融合 三网融合,又称“三网合一”,是指电信网、广播电视网、互联网在高层业务应用上的深度融合。这一概念在近年来随着信息技术的快速发展而逐渐受到重视,并成为推动信息化社会建设的重要力量。以下是对三网融合的详细解释: 一…...
自定义类型结构体(上)
目录 结构体类型的声明结构体的概念结构体的声明特殊的声明结构的自引用 结构体变量的创建和初始化结构成员访问操作符 结构体类型的声明 结构体的概念 结构体是一些值的集合,这些值称为成员变量。结构的每个成员可以是不同类型的变量 举个例子:杰克的英语只考了6…...
b站-湖科大教书匠】4 网络层 - 计算机网络微课堂
【b站-湖科大教书匠】4 网络层 - 计算机网络微课堂_湖科大的计算机网络网课-CSDN博客...
国际 Android WPS Office v18.13 解锁版
WPS Office 移动版,设计不断优化,性能再次提升!融入Google Android最新设计标准,Material Design设计风格,完美支持沉浸式!简化文档操作,全新移动办公力作。全新界面更清晰舒适,功能…...
【中间件学习】Git的命令和企业级开发
一、Git命令 1.1 创建Git本地仓库 仓库是进行版本控制的一个文件目录。我们要想对文件进行版本控制,就必须创建出一个仓库出来。创建一个Git本地仓库对应的命令是 git init ,注意命令要在文件目录下执行。 hrxlavm-1lzqn7w2w6:~/gitcode$ pwd /home/hr…...
FTP连接池与多线程FTP上传下载算法(Java)
设计一个能够处理FTP连接池在多线程环境下,尤其是涉及到故障重连时避免竞争条件的算法,需要综合考虑线程同步、连接状态管理和重试机制。以下是一个设计思路和实现方案: 设计思路 连接池管理: 维护一个连接池,其中包含多个FTP连接对象。每个FTP连接对象需有状态标记(如…...
Spring Cloud微服务详解
Spring Cloud微服务详解 在当今的数字化时代,微服务架构已成为构建大型、复杂应用系统的主流方式。Spring Cloud,作为微服务领域的一颗璀璨明星,以其强大的功能和灵活的架构,吸引了无数开发者的目光。本文将深入探讨Spring Cloud…...
QT学习笔记1.2(QT的应用)
QT原生用于c的开发, 主要应用于电脑、桌面手机桌面软件的开发,主要是widget样式模板。 Qt Widgets、Qt Quick 和 Qt for Python 是 Qt 框架中的三种不同的技术,分别用于不同的应用场景。以下是它们的详细介绍和对比: 1. Qt Widg…...
数学建模算法与应用 第1章 线性规划
第1章 线性规划 线性规划是数学规划领域的重要分支,广泛应用于资源配置、生产计划、物流管理等领域。它主要用于解决如何在满足一定约束条件下,使目标函数(如成本、利润等)达到最大或最小的问题。第一章将介绍线性规划的基本概念…...
使用 systemd 设置 PHP 程序为服务
使用 systemd 设置 PHP 程序为服务 在现代 Linux 系统中,systemd 是用于管理和控制服务的标准工具。通过 systemd,我们可以轻松地将 PHP 程序配置为后台运行的系统服务,从而实现自动化启动、重启和日志记录等功能。本文将介绍如何为 PHP 程序…...
HRNET模型实现钢板表面缺陷检测
关于深度实战社区 我们是一个深度学习领域的独立工作室。团队成员有:中科大硕士、纽约大学硕士、浙江大学硕士、华东理工博士等,曾在腾讯、百度、德勤等担任算法工程师/产品经理。全网20多万粉丝,拥有2篇国家级人工智能发明专利。 社区特色…...
28 基于51单片机的两路电压检测(ADC0808)
目录 一、主要功能 二、硬件资源 三、程序编程 四、实现现象 一、主要功能 基于51单片机,通过ADC0808获取两路电压,通过LCD1602显示 二、硬件资源 基于KEIL5编写C代码,PROTEUS8.15进行仿真,全部资源在页尾,提供…...
SpringBootTest Mockito 虚实结合编写测试
SpringBootTest & Mockito 虚实结合测试 起因 单一使用mockito,会出现很多mock困难的问题,导致测试编写过程太长,太恶心 单一使用springboottest,会遇到需要外部接口的地方,这个时候就非得去真实调用才行。也很恶…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
全球首个30米分辨率湿地数据集(2000—2022)
数据简介 今天我们分享的数据是全球30米分辨率湿地数据集,包含8种湿地亚类,该数据以0.5X0.5的瓦片存储,我们整理了所有属于中国的瓦片名称与其对应省份,方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...
拉力测试cuda pytorch 把 4070显卡拉满
import torch import timedef stress_test_gpu(matrix_size16384, duration300):"""对GPU进行压力测试,通过持续的矩阵乘法来最大化GPU利用率参数:matrix_size: 矩阵维度大小,增大可提高计算复杂度duration: 测试持续时间(秒&…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
基于Java+MySQL实现(GUI)客户管理系统
客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息,对客户进行统一管理,可以把所有客户信息录入系统,进行维护和统计功能。可通过文件的方式保存相关录入数据,对…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
