最长递增子序列,交错字符串
第一题:

代码如下:
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。
水平有限,欢迎指正。
相关文章:
最长递增子序列,交错字符串
第一题: 代码如下: 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. 反转字符串 编写一个函数,其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。 不要给另外的数组分配额外的空间,你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。 示例 1: 输入:s ["…...
linux Inodes满导致数据库宕机
项目经理反馈集群环境中有个节点无法使用了需要支援下,同时发过来截图说明磁盘还是有空的。 登录系统后直接发现问题 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 空容器构造函数(默认构造函数) 2. 使用指定容器构造 3 拷贝构造函数 二 其他操作 1 empty 2 size 3 top 4 push && pop 5 emplace 6 swap 三 总结 一 stack常见构造 1 空容器构造函数(默认构造…...
轻量级 K8S 环境 安装minikube
文章目录 操作系统DockerDocker CE 镜像源站使用官方安装脚本自动安装 (仅适用于公网环境)安装校验Docker代理docker permission denied while trying to connect to the Docker daemon socket minikubekubectl工具minikube dashboardminikube 基本命令参…...
市场巨变,移动开发行业即将迎来“第二春”?
随着鸿蒙生态的不断壮大,越来越多的企业开始加入其中,对鸿蒙OS开发工程师的需求也越来越迫切。 年初时还只有200个APP宣布加入鸿蒙生态,而最近华为也已经官宣,已经有4000多个应用加入鸿蒙,短短三个月就增加了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的查询,因为能获取到查询结果的rownum,就想着直接在查询条件后面做翻页,而且首页确实是正常查询到了。后面才发现翻页是空的。。。 这是因为rownum排序是在查询结果才分配的。所以应该把查询结果作为子查询,在外查询应用排序…...
学习笔记——动态路由协议——OSPF(OSPF基本术语)
OSPF基本术语 1、链路状态(LS)与链路状态通告(LSA) 链路(LINK):路由器上的一个接口。 状态(State):描述接口以及其与邻居路由器之间的关系。 (1)链路状态(LS) OSPF是一种链路状态协议,所谓的链路状态,其实就是路由器的接口状态…...
子集和问题(回溯法)
目录 前言 一、算法思路 二、分析过程 三、代码实现 伪代码: C: 总结 前言 【问题描述】考虑定义如下的PARTITION问题中的一个变型。给定一个n个整数的集合X{x1,x2,…,xn}和整数y,找出和等于y的X的子集Y。 一、算法思路 基本思想&am…...
【NumPy】全面解析arange函数:高效创建数值范围数组
🧑 博主简介:阿里巴巴嵌入式技术专家,深耕嵌入式人工智能领域,具备多年的嵌入式硬件产品研发管理经验。 📒 博客介绍:分享嵌入式开发领域的相关知识、经验、思考和感悟,欢迎关注。提供嵌入式方向…...
[ C++ ] 深入理解模板( 初 阶 )
函数模板 函数模板格式 template <typename T1, typename T2,......,typename Tn> 返回值类型 函数名(参数列表){} 注意: typename是用来定义模板参数关键字,也可以使用class(切记:不能使用struct代替class) 函数模板的实例化 模板参数…...
UI自动化测试最佳设计模式POM
当使用Selenium进行UI自动化测试时,Page Object Model(POM)是一种最佳实践的设计模式。POM的核心思想是通过将页面封装成对象,使得测试代码更加清晰、可维护和可重用。 POM的主要组成部分包括页面对象类、元素定位方式和操作方法…...
朋友圈定时发送设置
人日常中不可缺少的一件事,同时也是企业用来触达客户的重要渠道,下面一起来了解下微信朋友圈怎么定时发送呢?...
Spark SQL 中DataFrame DSL的使用
在上一篇文章中已经大致说明了DataFrame APi,下面我们具体介绍DataFrame DSL的使用。DataFrame DSL是一种命令式编写Spark SQL的方式,使用的是一种类sql的风格语法。 文章链接: 一、单词统计案例引入 import org.apache.spark.sql.{DataFrame, SaveMod…...
qt 布局学习笔记
目录 qt下载地址: widget 宽高 管理信息列表源码 c版: pro文件: qt 设置水平布局,里面有两个按钮,每个按钮就变的很宽,怎么设置按钮的精确位置 设置固定大小: 使用弹性空间(…...
设计模式复习
一、模式所采用的关系(e.g.继承…) UML图例 二、各模式的特点、优缺点 1.创建型(5种创建型口诀: 抽象工厂 按照 工厂方法,建造 单例 原型) 将对象的使用和创建分离,使用对象时无需知道对象的创建细节&a…...
前后端开发入门全攻略:零基础学起
新书上架~👇全国包邮奥~ python实用小工具开发教程http://pythontoolsteach.com/3 欢迎关注我👆,收藏下次不迷路┗|`O′|┛ 嗷~~ 目录 一、前后端开发概览 二、后端开发基础:Flask框架入门 代码案例:Hel…...
Android Studio无法改变Button背景颜色解决办法
大家好,我是咕噜铁蛋!今天我来和大家探讨一个在Android开发中常见但可能让初学者感到困惑的问题——如何在Android Studio中改变Button的背景颜色。这个问题看似简单,但实际操作中可能会遇到一些意想不到的挑战。接下来,我将从多个…...
元宇宙三维互动展厅让体验者进入一个充满奇幻与创意的数字世界
元宇宙数字产品展厅搭建编辑器凭借强大的三维可视化互动功能,为用户带来前所未有的沉浸式数字展览体验。 在元宇宙数字产品展厅搭建编辑器中,用户可以轻松打造逼真的三维展览环境,通过VR虚拟现实技术,仿佛置身于一个充满奇幻与创意…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动
一、前言说明 在2011版本的gb28181协议中,拉取视频流只要求udp方式,从2016开始要求新增支持tcp被动和tcp主动两种方式,udp理论上会丢包的,所以实际使用过程可能会出现画面花屏的情况,而tcp肯定不丢包,起码…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...
23-Oracle 23 ai 区块链表(Blockchain Table)
小伙伴有没有在金融强合规的领域中遇见,必须要保持数据不可变,管理员都无法修改和留痕的要求。比如医疗的电子病历中,影像检查检验结果不可篡改行的,药品追溯过程中数据只可插入无法删除的特性需求;登录日志、修改日志…...
基于服务器使用 apt 安装、配置 Nginx
🧾 一、查看可安装的 Nginx 版本 首先,你可以运行以下命令查看可用版本: apt-cache madison nginx-core输出示例: nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...
【磁盘】每天掌握一个Linux命令 - iostat
目录 【磁盘】每天掌握一个Linux命令 - iostat工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景 注意事项 【磁盘】每天掌握一个Linux命令 - iostat 工具概述 iostat(I/O Statistics)是Linux系统下用于监视系统输入输出设备和CPU使…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
