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

news/2024/6/21 6:36:52/文章来源:https://blog.csdn.net/weixin_64450655/article/details/139302294

第一题:

代码如下:


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.ldbm.cn/p/430624.html

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

相关文章

huggingface的self.state与self.control来源(TrainerState与TrainerControl)

文章目录 前言一、huggingface的trainer的self.state与self.control初始化调用二、TrainerState源码解读(self.state)1、huggingface中self.state初始化参数2、TrainerState类的Demo 三、TrainerControl源码解读(self.control)总结 前言 在 Hugging Face 中&#xff0c;self.s…

Matlab|基于PMU相量测量单元进行电力系统电压幅值和相角状态估计

主要内容 程序采用三种方法对14节点和30节点电力系统状态进行评估&#xff1a; ①PMU同步相量测量单元结合加权最小二乘法&#xff08;WLS&#xff09;分析电力系统的电压幅值和相角状态&#xff1b; ②并采用牛顿-拉夫逊方法进行系统潮流计算&#xff0c;结果作为理论分…

【Linux进程篇】Linux进程管理——进程创建与终止

W...Y的主页 &#x1f60a; 代码仓库分享&#x1f495; 目录 进程创建 fork函数初识 写时拷贝 fork常规用法 fork调用失败的原因 进程终止 进程退出场景 _exit函数 exit函数 return退出 进程创建 fork函数初识 在linux中fork函数时非常重要的函数&#xff0c;它从已…

【已解决】使用token登录机制,token获取不到,blog_list.html界面加载不出来

Bug产生 今天使用token完成用户登录信息的存储的时候被卡了大半天。 因为登录的功能写的已经很多了&#xff0c;所以今天就没有写一点验一点&#xff0c;而是在写完获取博客列表功功能&#xff0c;验证完它的后端后&#xff0c;了解完令牌的基本使用以及Jwt的基本使用方式——…

基于文本来推荐相似酒店

基于文本来推荐相似酒店 查看数据集基本信息 import pandas as pd import numpy as np from nltk.corpus import stopwords from sklearn.metrics.pairwise import linear_kernel from sklearn.feature_extraction.text import CountVectorizer from sklearn.feature_extrac…

C语言 指针——指针变量的定义、初始化及解引用

目录 指针 内存如何编址&#xff1f; 如何对变量进行寻址&#xff1f; 用什么类型的变量来存放变量的地址? 如何显示变量的地址?​编辑 使用未初始化的指针会怎样&#xff1f; NULL是什么&#xff1f; 如何访问指针变量指向的存储单元中的数据&#xff1f; 指针变量的…

电脑录屏怎么录?7个电脑录屏软件免费版强势来袭,赶快收藏!

电脑录屏怎么录&#xff1f;相信很多小伙伴们都不知道怎么在Windows电脑上录屏吧&#xff1f;在当今社会&#xff0c;随着互联网的快速发展&#xff0c;越来越多的小伙伴们开始通过制作视频内容来分享知识、展示技能或者记录生活。电脑录屏成为了一种简单高效的方式&#xff0c…

Python OCR 文字识别使用模型:读光-文字识别-行识别模型-中英-通用领域

介绍 什么是OCR&#xff1f; OCR是“Optical Character Recognition”的缩写&#xff0c;中文意为“光学字符识别”。它是一种技术&#xff0c;可以识别和转换打印在纸张或图像上的文字和字符为机器可处理的格式&#xff0c;如计算机文本文件。通过使用OCR技术&#xff0c;可…

2024.05.29学习记录

1、css面经复习 2、代码随想录二刷 3、rosebush upload组件初步完成

0基础认识C语言(理论+实操 2)

小伙伴们大家好&#xff0c;今天也要撸起袖子加油干&#xff01;万事开头难&#xff0c;越学到后面越轻松~ 话不多说&#xff0c;开始正题~ 前提回顾&#xff1a; 接上次博客&#xff0c;我们学到了转义字符&#xff0c;最后留下两个转义字符不知道大家有没有动手尝试了一遍&a…

MySQL8找不到my.ini配置文件以及报sql_mode=only_full_group_by解决方案

一、找不到my.ini配置文件 MySQL 8 安装或启动过程中&#xff0c;如果系统找不到my.ini文件&#xff0c;通常意味着 MySQL服务器没有找到其配置文件。在Windows系统上&#xff0c;MySQL 8 预期使用my.ini作为配置文件&#xff0c;而不是在某些情况下用到的my.cnf文件。 通过 …

自定义注解+AOP切面实现日志记录

自定义注解&#xff1a; Target(ElementType.METHOD)// 作用在方法上 Retention(RetentionPolicy.RUNTIME) Documented Inherited // 子类可以继承此注解 public interface OperationLog { } aop切面&#xff1a; Slf4j Aspect Component public class OperationAspect {Au…

格式化字符串

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 格式化字符串是指先制定一个模板&#xff0c;在这个模板中预留几个空位&#xff0c;然后再根据需要填上相应的内容。这些空位需要通过指定的符号标记…

tomcat学习--部署java项目

主流开发项目&#xff0c;springboot框架下&#xff0c;jar部署java传统的tomcat发布war包 一 什么是tomcat&#xff1f; 是一个用于运行java程序的软件&#xff0c;发布的时候&#xff1a;开发将源码使用maven打包&#xff0c;生产war包 二 安装tomcat tomcat是java写的&a…

基于GO 写的一款 GUI 工具,M3u8视频下载播放器-飞鸟视频助手

M3u8视频下载播放器-飞鸟视频助手 M3u8视频飞鸟视频助手使用m3u8下载m3u8 本地播放 软件下载地址m3u8嗅探 M3u8视频 M3u8视频格式是为网络视频播放设计&#xff0c;视频网站多数采用 m3u8格式。如腾讯&#xff0c;爱奇艺等网站。 m3u8和 mp4的区别&#xff1a; 一个 mp4是一个…

网络模型—BIO、NIO、IO多路复用、信号驱动IO、异步IO

一、用户空间和内核空间 以Linux系统为例&#xff0c;ubuntu和CentOS是Linux的两种比较常见的发行版&#xff0c;任何Linux发行版&#xff0c;其系统内核都是Linux。我们在发行版上操作应用&#xff0c;如Redis、Mysql等其实是无法直接执行访问计算机硬件(如cpu&#xff0c;内存…

STL库--stack

目录 stack的定义 stack容器内元素的访问 stack常用函数实例解析 stack的常见用途 stack的定义 其定义的写法和其他STL容器相同&#xff0c;typename可以任意基本类型或容器&#xff1a; stack<typename> name; stack容器内元素的访问 由于栈本身就是一种后进先出…

Facebook开户 | 如何检查公共主页的状态

想要了解你的Facebook公共主页的状态吗&#xff1f; Facebook公共主页是让广告主与粉丝互动、传播信息的绝佳平台&#xff0c;但是大家知道如何检查并维护自己的主页状态吗&#xff1f;别担心&#xff0c;Facebook提供了一系列简单易用的工具来帮助大家实现这一目标。 *Page Q…

如何恢复被盗的加密货币?

本世纪&#xff0c;网络犯罪的首要目标是加密货币。 这要归功于加密货币的日益普及和价值&#xff0c;网络犯罪分子已经认识到经济收益的潜力&#xff0c;并将重点转向利用这种数字资产中的漏洞。 在今天的文章中&#xff0c;我们将讨论加密货币恢复和被盗加密货币恢复。 我们…

爬虫案例-亚马逊反爬分析-验证码突破(x-amz-captcha)

总体概览&#xff1a;核心主要是需要突破该网站的验证码&#xff0c;成功后会返回我们需要的参数后再去请求一个中间页&#xff08;类似在后台注册一个session&#xff09;&#xff0c;最后需要注意一下 IP 是不能随意切换的 主要难点&#xff1a; 1、梳理整体反爬流程 2、验证…