力扣 | 最长公共子序列 | 动态规划 | 最长公共子序列长度、最长公共子序列

文章目录

  • 一、1143. 最长公共子序列
  • 二、求最长公共子序列
  • 三、变式
    • 一、1035. 不相交的线
    • 二、1312. 让字符串成为回文串的最少插入次数

一、1143. 最长公共子序列

LeetCode:1143. 最长公共子序列
这是一道典型的二维动态规划问题,甚至面试都能被面到。
在这里插入图片描述
这算是一个很简单的动态规划题,很容易想到解决方案:

定义dp数组,dp[i][j]表示text1i个字符和text2j个字符的最长公共子序列。

text1[i - 1] == text2[j - 1]时,显然有dp[i][j] = dp[i - 1][j - 1] + 1

text1[i - 1] != text2[j - 1]时,我们不能简单的认为dp[i][j] = dp[i - 1][j - 1] ,因为这样的话你并没有考虑新加入的两个字符对结果的影响,比如 a b c d 和 a b d c abcd和abdc abcdabdc,他们最后一个字符不相同,但是第二个字符串的最后一个字符和第一个字符串的第三个字符相同,因此dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]),即将新加入的两个字符的影响也考虑进去。

时间复杂度: O ( n m ) O(nm) O(nm)

class Solution {
public:int longestCommonSubsequence(string text1, string text2) {vector<vector<int>> dp(text1.size() + 1,vector<int>(text2.size() + 1, 0));int n = text1.size(), m = text2.size();for(int i = 1; i <= n; ++ i){for(int j = 1; j <= m; ++ 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[n][m];}
};

二、求最长公共子序列

这个问题在南大计科面试G组中有被问到

实际上和之前的区别是,这里需要求出子序列具体是什么。而我们知道对于两个字符串而言,他们的最长公共子序列是相同的。

动态规划:
由于公共子序列是相当于两个字符串而言的,因此我们不能只保存一个字符串中公共子序列的信息,因为你不知道它相对于另一方的那段而言的。

为了进行状态转移和最终得到子序列,我们需要求出text1[i]text2[j]的最长公共子序列的末尾下标。使用pair<int,int> sdp[n][m];

text1[i] == text2[j]时,sdp[i][j] = {i,j};
text1[i] != text2[j]时,if dp[i - 1][j] > dp[i][j - 1] then sdp[i][j] = sdp[i - 1][j] else sdp[i][j] = sdp[i][j - 1];

string LCS(string a, string b){string t;vector<vector<int>> dp(a.size() + 1, vector<int>(b.size() + 1, 0));vector<vector<pair<int, int>>> sdp(a.size() + 1, vector<pair<int, int>>(b.size() + 1, {0, 0}));for(int i = 1; i <= a.size(); ++ i){for(int j = 1; j <= b.size(); ++ j){if(a[i - 1] == b[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;sdp[i][j] = {i, j};}else{if(dp[i - 1][j] > dp[i][j - 1]){sdp[i][j] = sdp[i - 1][j];dp[i][j] = dp[i - 1][j];}else{sdp[i][j] = sdp[i][j - 1];dp[i][j] = dp[i][j - 1];}}}}for(pair<int, int> i = sdp[a.size()][b.size()]; i.first >= 1 && i.second >= 1; ){t.push_back(a[i.first - 1]);i = sdp[i.first - 1][i.second - 1];}reverse(t.begin(), t.end());return t;
}

利用dp信息回溯:
实际上,从后往前看,每次遇到的两个字符串中第一个相同的字符一定是公共子序列上的。因此我们从后往前遍历,我们如何判断呢?如果a[i]是公共子序列上的字符而b[j]不是,那么必然有dp[i - 1][j] < dp[i][j - 1],也就是a[i]被去除之后公共子序列少了一个,因此b[j]无用的话,直接--j这样可以找到和a[i]相同的字符串。同理如果dp[i - 1][j] > dp[i][j - 1],说明b[j]是公共子序列上的一员,而a[i]不是,因此可以直接--i

string LCS(string a, string b) {int n = a.size(), m = b.size();vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));// 填充 dp 数组for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {if (a[i - 1] == b[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;} else {dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);}}}// 回溯构建 LCSstring t;int i = n, j = m;while (i > 0 && j > 0) {if (a[i - 1] == b[j - 1]) {t.push_back(a[i - 1]);--i; --j;} else if (dp[i - 1][j] > dp[i][j - 1]) {--i;} else {--j;}}reverse(t.begin(), t.end());return t;
}

三、变式

一、1035. 不相交的线

LeetCode:1035. 不相交的线
在这里插入图片描述
这个题完全就是最长公共子序列问题,代码都不用改。

二、1312. 让字符串成为回文串的最少插入次数

LeetCode:1312. 让字符串成为回文串的最少插入次数
在这里插入图片描述
困难题,确实很难想,直观想法是从左右两边开始往中间遍历,依次判断字符是否相等来判断是否需要插入,如果相等则不需要,如果不相等则需要,但这样是不行的因为不相等的时候插入哪个字符呢?这很难判断。原因在于这俩其中有一个字符很可能与往中间去的某个字符相匹配,因此需要插入的是另一个。

回文序列实际上就是两边回文相同的序列,现在要求的实际上就是要求插入之后两边相同。那么我们选择一个转变后答案的回文中心的位置(我们在插入前并不知道是哪个,但他一定存在),然后是不是使得两边不同的字符串变成同一个就行了。

这实际上就是看公共子序列有多少个了,我们可以考察这样的问题:

将字符串 s t r 1 和 s t r 2 变成相同的需要插入多少字符 将字符串str1和str2变成相同的需要插入多少字符 将字符串str1str2变成相同的需要插入多少字符

这不是编辑距离吗? 不是!编辑距离可以增删改,这里只能增加。当然仔细思考可以发现,使用动态规划他们俩大同小异。

这个问题可以转化成最长公共子序列问题,求出 s t r 1 和 s t r 2 最长公共子序列长度 k str1和str2最长公共子序列长度k str1str2最长公共子序列长度k,然后答案就是len(str1)+len (str2)-2k。You ask why?变成相同,原来相同的是不是就不用动了,可以当作一个板子隔开字符串的各个部分,然后各个部分都是互不相同的,然后互相添加对方相同的部分即可。 那为什么要利用这些相同的呢? 不利用的话就谁都不和谁相同,直接没相同的了。understand?

那么最后这个困难题,就可以转换成,以每个可能的回文中心为中点,求两边字符串的最长公共子序列了,求出来之后就可以求出来插入多少个两边就会相同,并且在所有回文中心中取最小即可。(我们不知道哪个回文中心最好使)

时间复杂度: O ( n 2 ) O(n^2) O(n2)

class Solution {
public:int minInsertions(string s) {int n = s.size();vector<vector<int>> dp(n + 1,vector<int>(n + 2, 0));int num = 0x3f3f3f3f;for(int i = 1; i <= n; ++ i){for(int j = n; j >= i; -- j){if(s[i - 1] == s[j - 1]){dp[i][j] = dp[i - 1][j + 1] + 1;}else{dp[i][j] = max(dp[i - 1][j], dp[i][j + 1]);}if(i == j || i == j - 1)//两种回文序列的情况,一个是奇数,一个是偶数。num = min(i + (n + 1) - j - 2 * dp[i][j], num);}}return num;}
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/407294.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

c++ | 模板进阶

前言 本篇博客讲解c中的模板的一些其他知识 &#x1f493; 个人主页&#xff1a;普通young man-CSDN博客 ⏩ 文章专栏&#xff1a;C_普通young man的博客-CSDN博客 ⏩ 本人giee: 普通小青年 (pu-tong-young-man) - Gitee.com 若有问题 评论区见&#x1f4dd; &#x1f389;欢…

推荐一个国内Midjourney镜像站,限时充值享5折优惠 结尾附实测图片

作为一名绘画爱好者&#xff0c;你是否曾梦想过将脑海中的画面转化为现实&#xff1f;现在&#xff0c;有了群嘉智创平台&#xff08;ai.qunzjia.cn&#xff09;&#xff0c;这一切都将成为可能。群嘉智创是国内领先的AI对话与Midjourney绘画服务平台&#xff0c;通过接入国内多…

[Meachines] [Easy] Legacy nmap 漏洞扫描脚本深度发现+MS08-067

信息收集 IP AddressOpening Ports10.10.10.4TCP:135,139,445 $ nmap -p- 10.10.10.4 --min-rate 1000 -sC -sV -Pn PORT STATE SERVICE VERSION 135/tcp open msrpc Microsoft Windows RPC 139/tcp open netbios-ssn Microsoft Windows n…

论文阅读1 Scaling Synthetic Data Creation with 1,000,000,000 Personas

Scaling Synthetic Data Creation with 1,000,000,000 Personas 链接&#xff1a;https://github.com/tencent-ailab/persona-hub/ 文章目录 Scaling Synthetic Data Creation with 1,000,000,000 Personas1. 摘要2. 背景2.1 什么是数据合成2.2 为什么需要数据合成2.3 10亿种人…

基于Kotlin Multiplatform的鸿蒙跨平台开发实践

一、 背景 在 2023 年的华为开发者大会&#xff08;HDC&#xff09;上&#xff0c;华为预告了一个全新的鸿蒙系统 Harmony Next 版本。与之前的鸿蒙系统不同&#xff0c;Harmony Next完全摒弃了对 AOSP 的兼容&#xff0c;彻底基于 OpenHarmony 开源鸿蒙实现。这意味着该系统将…

在idea中的git选择某一次记录拉出一个新分支

一 创建新分支 1.1 操作步骤 需求&#xff1a;需要在图中标红的历史记录&#xff0c;从此记录拉出一个分支 1.右键【new branch】 2.起一个新的名字&#xff1a; 3.新分支代码

《图解设计模式》笔记(四)分开考虑

九、Bridge模式&#xff1a;将类的功能层次结构与实现层次结构分离 类的两个层次结构和作用 类的功能层次结构&#xff1a;希望增加新功能时 父类有基本功能&#xff0c;在子类中增加新功能 Something父类 …├─SomethingGood子类 想要再增加新功能 Something父类 …├─So…

LeetCode.55.跳跃游戏(贪心算法思路)

题目描述&#xff1a; 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 输…

Docker容器镜像及其打包

容器镜像分类 1. 系统类镜像 2. 应⽤镜像 搜索镜像 # 默认docker.hub docker search centos 下载镜像 docker pull centos 默认下载最新版本 1. 打包 [rootdocker001 ~]# systemctl start docker.service [rootdocker001 ~]# docker save -o centos.tar centos:latest [root…

基于SpringBoot的线上教学平台系统

你好呀&#xff0c;我是计算机学姐码农小野&#xff01;如果有相关需求&#xff0c;可以私信联系我。 开发语言 Java 数据库 MySQL 技术 SpringBoot框架&#xff0c;Java语言 工具 IDEA/Eclipse、Navicat、Maven 系统展示 首页 管理员功能模块 学员功能模块 前台首页…

Ozon在奥伦堡州开设首个配送中心,Ozon还有机会赚钱吗?

Ozon平台成立于1998年&#xff0c;是俄罗斯唯一上市的B2C电商平台&#xff0c;在俄罗斯电商市场中占据着到达62%的市场份额&#xff0c;具有强大的市场影响力和吸引力。Ozon拥有数千万的活跃用户&#xff0c;覆盖了俄罗斯各个年龄段和消费层次的群体&#xff0c;而且Ozon拥有俄…

“精准学”官宣将公布中国首个语音端到端大模型

教育科技公司“精准学”宣布&#xff0c;公司已在AI语音交互技术上取得领先性的突破&#xff0c;成功训练了中国首个语音端到端大模型“心流知镜-s(V02)”&#xff0c;可直接实现语音输入-语音输出的交互&#xff0c;使其更适配辅学场景&#xff0c;使大模型达到“真人老师”级…

当《黑神话:悟空》遇上openKylin,国产力量的极致碰撞!

了解更多银河麒麟操作系统全新产品&#xff0c;请点击访问 麒麟软件产品专区&#xff1a;https://product.kylinos.cn 开发者专区&#xff1a;https://developer.kylinos.cn 文档中心&#xff1a;https://documentkylinos.cn 万众瞩目的国产3A游戏巨作《黑神话&#xff1a;悟…

【人工智能】如何在白嫖的阿里云PAI平台上跑模型?

在“交互式建模&#xff08;DSW&#xff09;”中新建实例&#xff0c;阿里云自带的示例镜像是很少的&#xff0c;所以我们只需要筛选出适合你的项目的CUDA版本就好。DSW实例可以看作是一个Linux虚拟机&#xff0c;之后我们在实例中新建另一个Python环境使用即可。 新建完实例后…

DevExpress中Blazor部分学习

DevExpress中Blazor学习 1 DevExpress版本2 学习步骤2.1 查看Dev相应的Demo2.2 创建第一个相关应用2.3 使用XPO进行相关数据操作2.4 Dev Blazor使用XPO操作 3 学习中遇到问题及解决方案3.1 打开Dev相关Demo报错 1 DevExpress版本 安装较新的DevExpress&#xff0c;我这边使用的…

基于FreeRTOS的STM32多功能手表

前言 项目背景 项目演示 使用到的硬件 项目原理图 目前版本实现的功能 设计到的freertos知识 实现思路 代码讲解 初始化GPIO引脚、配置时钟 蜂鸣器初始化以及软件定时器创建 系统默认创建的defaultTaskHandle 创建七个Task&#xff0c;代表七个功能 ShowTimeTask …

京东软件测试岗面试题(干货)含答案+文档

&#x1f345; 点击文末小卡片&#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 前面看到了一些面试题&#xff0c;总感觉会用得到&#xff0c;但是看一遍又记不住&#xff0c;所以我把面试题都整合在一起&#xff0c;都是来自各路大佬的分享&am…

自然语言处理系列三十三》 语义相似度》同义词词林》算法原理

注&#xff1a;此文章内容均节选自充电了么创始人&#xff0c;CEO兼CTO陈敬雷老师的新书《自然语言处理原理与实战》&#xff08;人工智能科学与技术丛书&#xff09;【陈敬雷编著】【清华大学出版社】 文章目录 自然语言处理系列三十三同义词词林算法原理代码实战 总结 自然语…

LLama 3 跨各种 GPU 类型的基准测试

2024 年 4 月 18 日&#xff0c;AI 社区对 Llama 3 70B 的发布表示欢迎&#xff0c;这是一款最先进的大型语言模型 &#xff08;LLM&#xff09;。该型号是 Llama 系列的下一代产品&#xff0c;支持广泛的用例。该模型 istelf 在广泛的行业平台上表现良好&#xff0c;并提供了新…

基于STM32开发的智能室内照明系统

目录 引言环境准备工作 硬件准备软件安装与配置系统设计 系统架构硬件连接代码实现 系统初始化光照强度监测与处理照明控制与状态指示Wi-Fi通信与远程控制应用场景 智能家居照明管理办公室和公共场所的智能照明常见问题及解决方案 常见问题解决方案结论 1. 引言 随着智能家居…