最长递增子序列,交错字符串

第一题:

代码如下:


int lengthOfLIS(vector<int>& nums)
{//dp[i]表示以第i个元素为结尾的最长子序列的长度int n = nums.size();int res = 1;vector<int> dp(n, 1);for (int i = 1; i < n; ++i){for (int j = 0; j < i; ++j){if (nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);}res = max(res, dp[i]);}return res;
}

思路整理:

使用动态规划,线性dp就可以解决。

具体状态表示:dp[i]表示以第i个位置为结尾的最长子序列的长度。

初始化:因为最长递增子序列的长度至少为1,所以不妨将所有位置的长度都初始化为1。

填写过程以及逻辑:因为第一个位置为结尾的子序列长度为1,所以i从1下标开始,以该位置元素为结尾的序列有两种情况。

<1>该元素跟在其前面的任意一个元素后组成一个递增子序列。

<2>该元素比前面任意一个元素都小,所以只能自己成为单独的一个递增子序列。

因为在初始化时,已经将第二种情况考虑到了,所以每个位置都为1,若是第二种情况,就不必更新了,只考虑第一种情况就行。即

if (nums[i] > nums[j])dp[i] = max(dp[i], dp[j] + 1);

        表示i位置的元素大于j位置的元素时,dp[i]取dp[i]和dp[j] + 1两者之间的最大值。结合状态表示来理解。每当dp[i]更新完之后,可以更新一下最终结果,走完之后,就可以返回最终结果res了。

时空复杂度:时间复杂度O(n * n),空间复杂度O(n)

第二题:

代码如下:

bool isInterleave(string s1, string s2, string s3) 
{//dp[i][j]表示s1的[0,i]部分和s2的[0,j]能否构成s3的[i,j]部分int m = s1.size();int n = s2.size();if (m + n != s3.size())return false;s1 = " " + s1;s2 = " " + s2;s3 = " " + s3;vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));for (int i = 1; i <= n; ++i)//s1为空{if (s2[i] == s3[i]) dp[0][i] = true;elsebreak;}for (int i = 1; i <= m; ++i)//s2为空{if (s1[i] == s3[i]) dp[i][0] = true;elsebreak;}dp[0][0] = true;for (int i = 1; i <= m; ++i){for (int j = 1; j <= n; ++j){dp[i][j] = (s1[i] == s3[i + j] && dp[i - 1][j]|| s2[j] == s3[i + j] && dp[i][j - 1]);}}return dp[m][n];
}

思路整理:

动态规划,用到二维dp。在此之前,需要进行一个问题的转化,其实就是判断字符串s1能否由s2和s3组成。

具体状态表示:dp[i][j]表示s1的[0,i]部分和s2的[0,j]能否构成s3的[i,j]部分。

初始化:dp数组多开一行一列,便于结合状态定义来解决该问题,为了使得字符串位置一一对应,可以选择在字符串前加上空格符来进行占位,不表示额外含义,只是为了好进行对应。默认开辟的空间内都是false,结合状态定义,初始化第一行,即dp[0][i],当s1为空,就只有s2来组成s3,当s2[i] == s3[i]时,dp[0][i] = true,否则就是false,同理初始化第一列,即dp[i][0],当s2为空,只有s1来组成s3,当s1[i] == s3[i]时,dp[i][0] = true,否则就是false。dp[0][0]为true,确保后面的结果正确。

填写过程以及逻辑:如果s1的长度加上s2的长度和s3的长度不一致,那么就说明一定不能组成s3,返回false,否则dp[i][j]为真的情况有两种:

<1>s1[i] == s3[i + j] && dp[i - 1][j] == true,即s1的i位置和s3的i + j位置相同,并且s1的0~i-1位置和s2的0~j位置能构成s3的当前位置的其余部分。

<2>s2[j] == s3[i + j] && dp[i][j - 1] == true,即s2的i位置和s3的i + j位置相同,并且s1的0~i位置和s2的0~j - 1位置能构成s3的当前位置的其余部分。

最终返回dp[m][n]表示s1和s2能否构成s3。

水平有限,欢迎指正。

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

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

相关文章

ArcGIS提取含有计曲线的等高线

喜欢就关注我们吧&#xff01; 今天我么来看看&#xff0c;如何利用DEM提取含有计曲线的等高线&#xff01; 常规的话我们利用DEM提取的等高线都是不带计曲线的&#xff0c;无法把计曲线标注出来&#xff0c;今天我们就来看下&#xff0c;如何处理一下哦&#xff01;提取带有计…

Python内置方法串讲:类型转化与实用技巧

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、类型转化&#xff1a;从A到B的魔法 二、实用技巧&#xff1a;避免类型错误 三、总结 一…

【深度好文】AI企业融合联盟营销,做的好就是最大赢家!

AI工具市场正在迅速发展&#xff0c;现仍有不少企业陆续涌出&#xff0c;那么如何让你的工具受到目标群体的关注呢&#xff1f;这相比是AI工具营销人员一直在思考的问题。 即使这个市场正蓬勃发展&#xff0c;也无法保证营销就能轻易成功。AI工具虽然被越来越多人认可和接受&a…

JAVA类与方法·易错题分析

分析一下作业中关于类与方法写错或者易错的题。 N o . 1 No.1 No.1 下面程序的执行结果是______。 public class Test7 {public static void main(String[] args){new B().display();} } class A{public void draw() {System.out.print("Draw A.");}public void di…

金蝶云星空数据库迁移后,显示 error: 40 - 无法打开到 SQL Server 的连接的解决方法

原因&#xff1a;数据库迁移/或者更新IP后&#xff0c;与之前添加的数据库地址不一致导致无法连接数据库&#xff1b; 解决方法&#xff1a;修改IP为目前数据库的IP&#xff1b; 文件路径&#xff1a;在ManageSite\APP_Data\Common.config中&#xff0c;修改DbServerInstance…

动态规划part03 Day43

LC343整数拆分&#xff08;未掌握&#xff09; 未掌握分析&#xff1a;dp数组的含义没有想清楚&#xff0c;dp[i]表示分解i能够达到的最大乘积&#xff0c;i能够如何分解呢&#xff0c;从1开始遍历&#xff0c;直到i-1&#xff1b;每次要不是j和i-j两个数&#xff0c;要不是j和…

Function Calling学习

Function Calling第一篇 Agent&#xff1a;AI 主动提要求Function Calling&#xff1a;AI 要求执行某个函数场景举例&#xff1a;明天上班是否要带伞&#xff1f;AI反过来问你&#xff0c;明天天气怎么样&#xff1f; Function Calling 的基本流程 Function Calling 完整的官…

adb的常见操作和命令

最近学习adb的时候&#xff0c;整理了一些adb的使用场景&#xff0c;如&#xff1a;adb与设备交互&#xff0c;adb的安装、卸载&#xff0c;adb命令启动&#xff0c;通过命令清除缓存&#xff0c;文件传输和日志操作。 adb的两大作用&#xff1a;在app测试的时候可以提供监控日…

CentOS8搭载正反向解析dns服务器

1.介绍&#xff08;是什么&#xff09; DNS&#xff08;Domain Name System&#xff09;&#xff0c;即域名系统&#xff0c;是一个将域名和 IP 地址相互映射的分布式数据库&#xff0c;它可以将用户输入的域名转换成对应的 IP 地址。DNS 由多个服务器组成&#xff0c;分为多个…

git 学习随笔

git 学习随笔 基本概念 git 对待数据类似快照流的形式而不是类似 cvs 那样的纪录文件随时间逐步积累的差异 git 中所有数据在存储钱都会计算校验和&#xff08;hash) 三种状态&#xff1a;已提交(committed)&#xff0c;已修改(modified)&#xff0c;已暂存(staged)。 add…

【spring】@PathVariable注解学习

PathVariable介绍 PathVariable是Spring框架中的一个注解&#xff0c;主要用于处理RESTful风格URL中的路径变量。在RESTful接口设计中&#xff0c;我们经常将资源的ID或者其他标识信息直接放在URL路径中&#xff0c;而不是作为查询参数。PathVariable注解使得控制器方法能够轻…

【Linux】Linux基本指令2

我们接着上一篇&#xff1a;http://t.csdnimg.cn/bSJx8 我们接着完善ls指令 我们可以直接匹配对应格式的文件匹配出来 1.man指令&#xff08;重要&#xff09;&#xff1a; Linux的命令有很多参数&#xff0c;我们不可能全记住&#xff0c;我们可以通过查看联机手册获取帮助…

原神抽卡点名程序教程(直接下载用)

今天我要给大家分享一个在抖音上特别火的视频——原神抽卡点名程序教程。 &#xff08;要源码的私信扣31&#xff09; 废话不多说&#xff0c;直接上效果图 &#xff1a; 步骤1&#xff1a; 步骤2&#xff1a;&#xff08;写名单&#xff0c;前面加数字代表星级&#xff0c;用…

去除字符串中的空格和特殊字符

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 用户在输入数据时&#xff0c;可能会无意中输入多余的空格&#xff0c;或在一些情况下&#xff0c;字符串前后不允许出现空格和特殊字符&#xff0c;…

【C语言】自定义类型:联合体和枚举

1. 联合体 1.1 联合体的特点 像结构体⼀样&#xff0c;联合体也是由⼀个或者多个成员构成&#xff0c;这些成员可以不同的类型。 但是编译器只为最⼤的成员分配⾜够的内存空间。联合体的特点是所有成员共⽤同⼀块内存空间所以联合体也叫&#xff1a;共⽤体。 union Un {char…

DETR整体模型结构解析

DETR流程 Backbone用卷积神经网络抽特征。最后通过一层1*1卷积转化到d_model维度fm&#xff08;B,d_model,HW&#xff09;。 position embedding建立跟fm维度相同的位置编码(B&#xff0c;d_model,HW&#xff09;。 Transformer Encoder,V为fm&#xff0c;K&#xff0c;Q为fm…

【Python】解决Python报错:TypeError: can only concatenate str (not “int“) to str

&#x1f9d1; 博主简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟&#xff0c;欢迎关注。提供嵌入式方向…

反转!Greenplum 还在,快去 Fork 源码

↑ 关注“少安事务所”公众号&#xff0c;欢迎⭐收藏&#xff0c;不错过精彩内容~ 今早被一条消息刷爆群聊&#xff0c;看到知名开源数仓 Greenplum 的源码仓“删库跑路”了。 要知道 GP 新东家 Broadcom 前几日才刚刚免费开放了 VMware Workstation PRO 17 和 VMware Fusion P…

Selenium 自动化测试工具(1) (Selenium 工作原理,常用API的使用)

文章目录 什么是自动化测试什么是测试工具&#xff1a;Selenium 工作原理(重要)Selenium API定位元素CSS 选择器xpath 定位元素 通过Java代码实现自动化1. 定位元素2. 关闭浏览器3. 获取元素文本4. 鼠标点击与键盘输入5. 清空内容6.打印信息 什么是自动化测试 关于自动化&…

使用C语言实现学生信息管理系统

前言 在我们实现学生信息管理系统的过程中&#xff0c;我们几乎会使用到C语言最常用最重要的知识&#xff0c;对于刚学习完C语言的同学来说是一次很好的巩固机会&#xff0c;其中还牵扯到数据结果中链表的插入和删除内容。 实现学生信息管理系统 文件的创建与使用 对于要实现…