当前位置: 首页 > news >正文

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

第一题:

代码如下:


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。

水平有限,欢迎指正。

相关文章:

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

第一题&#xff1a; 代码如下&#xff1a; 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]…...

力扣:344. 反转字符串

344. 反转字符串 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间&#xff0c;你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 1&#xff1a; 输入&#xff1a;s ["…...

linux Inodes满导致数据库宕机

项目经理反馈集群环境中有个节点无法使用了需要支援下&#xff0c;同时发过来截图说明磁盘还是有空的。 登录系统后直接发现问题 orcl2:/home/oracledb2> sqlplus / as sysdba SQL*Plus: Release 11.2.0.4.0 Production on Wed May 29 13:59:21 2024 Copyright (c) 1982,…...

【STL】C++ stack(栈) 基本使用

目录 一 stack常见构造 1 空容器构造函数&#xff08;默认构造函数&#xff09; 2. 使用指定容器构造 3 拷贝构造函数 二 其他操作 1 empty 2 size 3 top 4 push && pop 5 emplace 6 swap 三 总结 一 stack常见构造 1 空容器构造函数&#xff08;默认构造…...

轻量级 K8S 环境 安装minikube

文章目录 操作系统DockerDocker CE 镜像源站使用官方安装脚本自动安装 &#xff08;仅适用于公网环境&#xff09;安装校验Docker代理docker permission denied while trying to connect to the Docker daemon socket minikubekubectl工具minikube dashboardminikube 基本命令参…...

市场巨变,移动开发行业即将迎来“第二春”?

随着鸿蒙生态的不断壮大&#xff0c;越来越多的企业开始加入其中&#xff0c;对鸿蒙OS开发工程师的需求也越来越迫切。 年初时还只有200个APP宣布加入鸿蒙生态&#xff0c;而最近华为也已经官宣&#xff0c;已经有4000多个应用加入鸿蒙&#xff0c;短短三个月就增加了20倍。 …...

DependencyCheck工具使用

1、工具下载地址 Releases jeremylong/DependencyCheck GitHub 2、工具使用 ./dependency-check.sh --disableRetireJS --disableNodeJS --project test -s /test/ -o /home/clog/test/report10 --noupdate...

oracle翻页查询的小坑记录

oracle的查询&#xff0c;因为能获取到查询结果的rownum&#xff0c;就想着直接在查询条件后面做翻页&#xff0c;而且首页确实是正常查询到了。后面才发现翻页是空的。。。 这是因为rownum排序是在查询结果才分配的。所以应该把查询结果作为子查询&#xff0c;在外查询应用排序…...

学习笔记——动态路由协议——OSPF(OSPF基本术语)

OSPF基本术语 1、链路状态(LS)与链路状态通告(LSA) 链路(LINK)&#xff1a;路由器上的一个接口。 状态(State)&#xff1a;描述接口以及其与邻居路由器之间的关系。 (1)链路状态(LS) OSPF是一种链路状态协议&#xff0c;所谓的链路状态&#xff0c;其实就是路由器的接口状态…...

子集和问题(回溯法)

目录 ​​​​ 前言 一、算法思路 二、分析过程 三、代码实现 伪代码&#xff1a; C&#xff1a; 总结 前言 【问题描述】考虑定义如下的PARTITION问题中的一个变型。给定一个n个整数的集合X{x1,x2,…,xn}和整数y&#xff0c;找出和等于y的X的子集Y。 一、算法思路 基本思想&am…...

【NumPy】全面解析arange函数:高效创建数值范围数组

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

[ C++ ] 深入理解模板( 初 阶 )

函数模板 函数模板格式 template <typename T1, typename T2,......,typename Tn> 返回值类型 函数名(参数列表){} 注意&#xff1a; typename是用来定义模板参数关键字&#xff0c;也可以使用class(切记&#xff1a;不能使用struct代替class) 函数模板的实例化 模板参数…...

UI自动化测试最佳设计模式POM

当使用Selenium进行UI自动化测试时&#xff0c;Page Object Model&#xff08;POM&#xff09;是一种最佳实践的设计模式。POM的核心思想是通过将页面封装成对象&#xff0c;使得测试代码更加清晰、可维护和可重用。 POM的主要组成部分包括页面对象类、元素定位方式和操作方法…...

朋友圈定时发送设置

人日常中不可缺少的一件事&#xff0c;同时也是企业用来触达客户的重要渠道&#xff0c;下面一起来了解下微信朋友圈怎么定时发送呢&#xff1f;...

Spark SQL 中DataFrame DSL的使用

在上一篇文章中已经大致说明了DataFrame APi,下面我们具体介绍DataFrame DSL的使用。DataFrame DSL是一种命令式编写Spark SQL的方式&#xff0c;使用的是一种类sql的风格语法。 文章链接&#xff1a; 一、单词统计案例引入 import org.apache.spark.sql.{DataFrame, SaveMod…...

qt 布局学习笔记

目录 qt下载地址&#xff1a; widget 宽高 管理信息列表源码 c版&#xff1a; pro文件&#xff1a; qt 设置水平布局&#xff0c;里面有两个按钮&#xff0c;每个按钮就变的很宽&#xff0c;怎么设置按钮的精确位置 设置固定大小&#xff1a; 使用弹性空间&#xff08;…...

设计模式复习

一、模式所采用的关系&#xff08;e.g.继承…&#xff09; UML图例 二、各模式的特点、优缺点 1.创建型&#xff08;5种创建型口诀: 抽象工厂 按照 工厂方法&#xff0c;建造 单例 原型&#xff09; 将对象的使用和创建分离&#xff0c;使用对象时无需知道对象的创建细节&a…...

前后端开发入门全攻略:零基础学起

新书上架~&#x1f447;全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我&#x1f446;&#xff0c;收藏下次不迷路┗|&#xff40;O′|┛ 嗷~~ 目录 一、前后端开发概览 二、后端开发基础&#xff1a;Flask框架入门 代码案例&#xff1a;Hel…...

Android Studio无法改变Button背景颜色解决办法

大家好&#xff0c;我是咕噜铁蛋&#xff01;今天我来和大家探讨一个在Android开发中常见但可能让初学者感到困惑的问题——如何在Android Studio中改变Button的背景颜色。这个问题看似简单&#xff0c;但实际操作中可能会遇到一些意想不到的挑战。接下来&#xff0c;我将从多个…...

元宇宙三维互动展厅让体验者进入一个充满奇幻与创意的数字世界

元宇宙数字产品展厅搭建编辑器凭借强大的三维可视化互动功能&#xff0c;为用户带来前所未有的沉浸式数字展览体验。 在元宇宙数字产品展厅搭建编辑器中&#xff0c;用户可以轻松打造逼真的三维展览环境&#xff0c;通过VR虚拟现实技术&#xff0c;仿佛置身于一个充满奇幻与创意…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

unix/linux,sudo,其发展历程详细时间线、由来、历史背景

sudo 的诞生和演化,本身就是一部 Unix/Linux 系统管理哲学变迁的微缩史。来,让我们拨开时间的迷雾,一同探寻 sudo 那波澜壮阔(也颇为实用主义)的发展历程。 历史背景:su的时代与困境 ( 20 世纪 70 年代 - 80 年代初) 在 sudo 出现之前,Unix 系统管理员和需要特权操作的…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

Python Einops库:深度学习中的张量操作革命

Einops&#xff08;爱因斯坦操作库&#xff09;就像给张量操作戴上了一副"语义眼镜"——让你用人类能理解的方式告诉计算机如何操作多维数组。这个基于爱因斯坦求和约定的库&#xff0c;用类似自然语言的表达式替代了晦涩的API调用&#xff0c;彻底改变了深度学习工程…...