牛客热题:最长公共子序列Ⅱ

📟作者主页:慢热的陕西人

🌴专栏链接:力扣刷题日记

📣欢迎各位大佬👍点赞🔥关注🚓收藏,🍉留言

在这里插入图片描述

文章目录

  • 牛客热题:最长公共子序列Ⅱ
    • 题目链接
    • 方法一:动态规划+递归
      • 思路
      • 代码
      • 复杂度

牛客热题:最长公共子序列Ⅱ

题目链接

最长公共子序列(二)_牛客题霸_牛客网 (nowcoder.com)

方法一:动态规划+递归

思路

整体思路:

①先求出最长子序列的长度

②根据长度去寻找对应的字符串

详细步骤:

  • step 1:优先检查特殊情况。
  • step 2:获取最长公共子序列的长度可以使用动态规划,我们以 d p [ i ] [ j ] dp[i][j] dp[i][j]表示在s1中以 i i i结尾,s2中以 j j j结尾的字符串的最长公共子序列长度。
  • step 3:遍历两个字符串的所有位置,开始状态转移:若是 i i i位与 j j j位的字符相等,则该问题可以变成1 + d p [ i − 1 ] [ j − 1 ] dp[i - 1][j - 1] dp[i1][j1],即到此处为止最长公共子序列长度由前面的结果加1。
  • step 4:若是不相等,说明到此处为止的子串,最后一位不可能同时属于最长公共子序列,毕竟它们都不相同,因此我们考虑换成两个子问题, d p [ i − 1 ] [ j ] dp[i - 1][j] dp[i1][j] d p [ i ] [ j − 1 ] dp[i][j - 1] dp[i][j1],我们取较大的一个就可以了,由此感觉可以用递归解决。
  • step 5:但是递归的复杂度过高,重复计算了很多低层次的部分,因此可以用动态规划,从前往后加,由此形成一个表,表从位置1开始往后相加,正好符合动态规划的转移特征。
  • step 6:因为最后要返回该序列,而不是长度,所以在构造表的同时要以另一个二维矩阵记录上面状态转移时选择的方向,我们用1表示来自左上方,2表示来自左边,3表示来自上边。
  • step 7:获取这个序列的时候,根据从最后一位开始,根据记录的方向,不断递归往前组装字符,只有来自左上的时候才添加本级字符,因为这种情况是动态规划中两个字符相等的情况,字符相等才可用!

代码

string x = "";string ans(int i, int j, vector<vector<int>>& b){string res = "";if(i == 0 || j == 0){return res;}if(b[i][j] == 1){res += ans(i - 1, j - 1, b);res += x[i - 1];}else if(b[i][j] == 2){res += ans(i - 1, j, b);}else if(b[i][j] == 3){res += ans(i, j - 1, b);}return res;}string LCS(string s1, string s2) {//特殊情况:其中一个字符串为空if(s1.size() == 0 || s2.size() == 0){return "-1";}int len1 = s1.size();int len2 = s2.size();x = s1;//dp[i][j],表示第一个字符串第i位,第二个字符串第j位为止的最长公共子序列vector<vector<int>> dp(len1 + 1, vector<int>(len2 + 1, 0));//动态规划数组相加的方向vector<vector<int>> b(len1 + 1, vector<int>(len2 + 1, 0));//遍历两个字符串每个位置求得最长长度for(int i = 1; i <= len1; ++i)for(int j = 1; j <= len2; ++j){if(s1[i - 1] == s2[j - 1]){dp[i][j] = dp[i - 1][j - 1] + 1;//来自左上方b[i][j] = 1;}else {if(dp[i - 1][j] > dp[i][j - 1]){dp[i][j] = dp[i - 1][j];//来自左方b[i][j] = 2;}else{dp[i][j] = dp[i][j - 1];//来自右方b[i][j] = 3;}}}string res = ans(len1, len2, b);return res == "" ? "-1" : res;}

复杂度

  • 时间复杂度:O(n2),构造辅助数组dp与b,两层循环,递归是有方向的递归,因此只是相当于遍历了二维数组
  • 空间复杂度:O(n2),辅助二维数组dp与递归栈的空间最大为O(n2)

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

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

相关文章

网络安全形势与WAF技术分享

我一个朋友的网站&#xff0c;5月份时候被攻击了&#xff0c;然后他找我帮忙看看&#xff0c;我看他的网站、网上查资料&#xff0c;不看不知道&#xff0c;一看吓一跳&#xff0c;最近几年这网络安全形势真是不容乐观&#xff0c;在网上查了一下资料&#xff0c;1、中国信息通…

vue2的form利用插槽修改错误提示UI

1. 需求 很多时候我们使用el-form想修改下错误提示的UI&#xff0c;比如table中使用form校验这类场景下错误提示的UI调整就非常重要。 2. 了解文档 Form-Item Scoped Slot name说明error自定义表单校验信息的显示方式&#xff0c;参数为 { error } 3.实际使用 html里使用…

Python Flask实现蓝图Blueprint配置和模块渲染

Python基础学习&#xff1a; Pyhton 语法基础Python 变量Python控制流Python 函数与类Python Exception处理Python 文件操作Python 日期与时间Python Socket的使用Python 模块Python 魔法方法与属性 Flask基础学习&#xff1a; Python中如何选择Web开发框架&#xff1f;Pyth…

数据结构笔记 4 树和二叉树

二叉树和完全二叉树的区别&#xff1f; 二叉树和完全二叉树的主要区别在于它们的结构特性和节点排列方式&#xff1a; 1. **二叉树**&#xff1a; - 是一种数据结构&#xff0c;其中每个节点最多有两个子节点&#xff0c;通常称为左子节点和右子节点。 - 节点的子节点数量…

git凭证

默认是manager # 将凭证缓存到内存中&#xff0c;默认缓存15分钟 git config --global credential.helper cache# 将凭证存储到磁盘上的纯文本文件中 git config --global credential.helper store# 使用 Git 凭证管理器 git config --global credential.helper manager-core查…

图文详解Windows系统下搭建mysql开发环境——mysql Community 8 和 navicat Premium 17 的安装和使用

在正式开始学习使用MySQL之前&#xff0c;我们有必要先搭建一个良好的开发环境&#xff0c;让我们的学习和工作效率事半功倍。 本文涉及到的软件百度云盘&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1jj_YajEv8adeEjMrXLhOTQ?pwd1023 提取码&#xff1a;1023 目录 …

元宇宙数字藏品交易所,未来发展的大趋势

随着科技的飞速进步&#xff0c;元宇宙以其独特的魅力为数字世界绘制了一幅前所未有的宏伟蓝图。在这一宏大的背景下&#xff0c;数字藏品交易所作为连接虚拟与现实的桥梁&#xff0c;正以其卓越的优势&#xff0c;引领着数字藏品市场迈向新的高度。 首先&#xff0c;元宇宙为…

三十六篇:未来架构师之道:掌握现代信息系统典型架构

未来架构师之道&#xff1a;掌握现代信息系统典型架构 1. 引言 在企业的数字化转型浪潮中&#xff0c;信息系统架构的角色变得日益重要。它不仅承载了企业的IT战略&#xff0c;更是确保企业在复杂、动态的市场环境中稳定运行的关键。作为信息系统的骨架&#xff0c;一个精心设…

HTML5+CSS3+JS小实例:网格图库

实例:网格图库 技术栈:HTML+CSS+JS 效果: 源码: 【HTML】 <!DOCTYPE html> <html lang="zh-CN"><head><meta charset="UTF-8"><meta name="viewport" content="width=device-width, initial-scale=1.0&…

Python中猴子补丁是什么,如何使用

1、猴子补丁奇遇记 &#x1f412; 在Python的世界深处&#xff0c;隐藏着一种神秘而又强大的技巧——猴子补丁&#xff08;Monkey Patching&#xff09;。这是一项允许你在程序运行时动态修改对象&#xff08;如模块、类或函数&#xff09;的行为的技术。它得名于其“快速修补…

算法导论实战(六)(算法导论习题三十四、三十五章)

&#x1f308; 个人主页&#xff1a;十二月的猫-CSDN博客 &#x1f525; 系列专栏&#xff1a; &#x1f3c0;算法启示录 &#x1f4aa;&#x1f3fb; 十二月的寒冬阻挡不了春天的脚步&#xff0c;十二点的黑夜遮蔽不住黎明的曙光 前言 算法导论的知识点学习将持续性更新在算…

Docker 基础使用(2) 镜像与容器

文章目录 镜像的含义镜像的构成镜像的作用镜像的指令容器的含义容器的状态容器的指令 Docker 基础使用&#xff08;0&#xff09;基础认识 Docker 基础使用 (1) 使用流程概览 Docker 基础使用&#xff08;2&#xff09; 镜像与容器 Docker 基础使用&#xff08;3&#xff09; 存…

2024年【天津市安全员C证】免费试题及天津市安全员C证试题及解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 天津市安全员C证免费试题是安全生产模拟考试一点通生成的&#xff0c;天津市安全员C证证模拟考试题库是根据天津市安全员C证最新版教材汇编出天津市安全员C证仿真模拟考试。2024年【天津市安全员C证】免费试题及天津市…

VBA excel 表格将多行拆分成多个表格或 文件 或者合并 多个表格

excel 表格 拆分 合并 拆分工作表按行拆分为工作表工作表按行拆分为工作薄 合并操作步骤 拆分 为了将Excel中的数万行数据拆分成多个个每个固定行数的独立工作表&#xff0c;并且保留每个工作表的表头&#xff0c;你可以使用以下VBA脚本。这个脚本会复制表头到每个新的工作表&…

行心科技中禄松波携手,开启智能健康新时代

在2024年第34届健博会暨中国大健康产业文化节的盛大舞台上&#xff0c;广州市行心信息科技有限公司&#xff08;以下简称“行心科技”&#xff09;与浙江中禄松波生物工程有限公司&#xff08;以下简称“中禄松波”&#xff09;宣布达成战略合作&#xff0c;共同推动医康养产业…

socket通信(C语言+Python)

在socket文件夹下创建server.c和client.c。 服务端代码&#xff08;server.c&#xff09;&#xff1a; #include <stdio.h> #include <Winsock2.h> void main() {WORD wVersionRequested;WSADATA wsaData;int err;wVersionRequested MAKEWORD( 1, 1 );err WSAS…

探索 Noisee AI 的奇妙世界与变现之旅

日赚800&#xff0c;利用淘宝/闲鱼进行AI音乐售卖实操 如何让AI生成自己喜欢的歌曲-AI音乐创作的正确方式 抖音主播/电商人员有福了&#xff0c;利用Suno创作产品宣传&#xff0c;让产品动起来-小米Su7 用sunoAI写粤语歌的方法&#xff0c;博主已经亲自实践可行 五音不全也…

通道堵塞自动识别摄像机

通道堵塞自动识别摄像机是一种利用先进的人工智能和图像识别技术来监测和识别通道堵塞情况的装置&#xff0c;广泛应用于交通管制、商场管理等领域。这项技术的出现极大地提高了通道管理的效率和准确性&#xff0c;为改善人们的出行体验和商场营运提供了新的解决方案。 传统的通…

Vue3【十一】08使用toRefs和toRef

08使用toRefs和toRef toRefs()函数将person对象中的name和age属性转换为响应式引用&#xff0c;并返回一个对象&#xff0c;对象中的name和age属性都是响应式引用&#xff0c;具有响应式功能。 toRef()函数将person对象中的name属性转换为响应式引用&#xff0c;并返回一个响应…

Doris Connector 结合 Flink CDC 实现 MySQL 分库分表

1. 概述 在实际业务系统中为了解决单表数据量大带来的各种问题&#xff0c;我们通常采用分库分表的方式对库表进行拆分&#xff0c;以达到提高系统的吞吐量。 但是这样给后面数据分析带来了麻烦&#xff0c;这个时候我们通常试将业务数据库的分库分表同步到数据仓库时&#x…