算法刷题:300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
300. 最长递增子序列
1.dp定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
2.递推公式:if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值。
3.初始化:每一个i,对应的dp[i](即最长递增子序列)起始大小至少都是1.
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if (nums.size() <= 1) return nums.size();vector<int> dp(nums.size(), 1);int result = 0;for (int i = 1; i < nums.size(); i++) {for (int j = 0; j < i; j++) {if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);}if (dp[i] > result) result = dp[i]; // 取长的子序列}return result;}
};
674. 最长连续递增序列
1.dp定义:dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。
2.递推公式:如果 nums[i] > nums[i - 1],那么以 i 为结尾的连续递增的子序列长度 一定等于 以i - 1为结尾的连续递增的子序列长度 + 1 。
即:dp[i] = dp[i - 1] + 1;
因为本题要求连续递增子序列,所以就只要比较nums[i]与nums[i - 1],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)。
3.dp[i]应该初始1;
class Solution {
public:int findLengthOfLCIS(vector<int>& nums) {if (nums.size() == 0) return 0;int result = 1;vector<int> dp(nums.size() ,1);for (int i = 1; i < nums.size(); i++) {if (nums[i] > nums[i - 1]) { // 连续记录dp[i] = dp[i - 1] + 1;}if (dp[i] > result) result = dp[i];}return result;}
};
718. 最长重复子数组
1.dp定义:以下标i - 1为结尾的A,和以下标j - 1为结尾的B,最长重复子数组长度为dp[i][j]。
2.递推公式:当A[i - 1] 和B[j - 1]相等的时候,dp[i][j] = dp[i - 1][j - 1] + 1;
根据递推公式可以看出,遍历i 和 j 要从1开始!
3.初始化:根据dp[i][j]的定义,dp[i][0] 和dp[0][j]其实都是没有意义的!
但dp[i][0] 和dp[0][j]要初始值,因为 为了方便递归公式dp[i][j] = dp[i - 1][j - 1] + 1;
所以dp[i][0] 和dp[0][j]初始化为0。
举个例子A[0]如果和B[0]相同的话,dp[1][1] = dp[0][0] + 1,只有dp[0][0]初始为0,正好符合递推公式逐步累加起来。
注:如果dp数组以i,j为结尾,那么初始化时,应该为dp[i] = dp[j]时初始化为1

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2) {vector<vector<int>> dp (nums1.size() + 1, vector<int>(nums2.size() + 1, 0));int result = 0;for (int i = 1; i <= nums1.size(); i++) {for (int j = 1; j <= nums2.size(); j++) {if (nums1[i - 1] == nums2[j - 1]) {dp[i][j] = dp[i - 1][j - 1] + 1;}if (dp[i][j] > result) result = dp[i][j];}}return result;}
};
相关文章:
算法刷题:300. 最长递增子序列、674. 最长连续递增序列、718. 最长重复子数组
300. 最长递增子序列 1.dp定义:dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度 2.递推公式:if (nums[i] > nums[j]) dp[i] max(dp[i], dp[j] 1); 注意这里不是要dp[i] 与 dp[j] 1进行比较,而是我们要取dp[j] 1的最大值…...
【linux】一种基于虚拟串口的方式使两个应用通讯
在Linux系统中,两个应用之间通过串口(Serial Port)进行通信是一种常见的通信方式,特别是在嵌入式系统、工业自动化等领域。串口通信通常涉及到对串口设备的配置和读写操作。以下是一个基本的步骤指南,说明如何在Linux中…...
并行程序设计基础——并行I/O(3)
目录 一、多视口的并行文件并行读写 1、文件视口与指针 1.1 MPI_FILE_SET_VIEW 1.2 MPI_FILE_GET_VIEW 1.3 MPI_FILE_SEEK 1.4 MPI_FILE_GET_POSTION 1.5 MPI_FILE_GET_BYTE_OFFSET 2、阻塞方式的视口读写 2.1 MPI_FILE_READ 2.2 MPI_FILE_WRITE 2.3 MPI_FILE_READ_…...
性能测试-jmeter脚本录制(十五)
一、jmeter脚本录制(不推荐)简介: 二、jmeter脚本录制步骤 1、添加代理服务器和线程组 2、配置http代理服务器的端口和目标线程组 3修改本机浏览器代理 4、点击启动 5、每次操作页面前,修改提示文字...
关系型数据库 - MySQL I
MySQL 数据库 MySQL 是一种关系型数据库。开源免费,并且方便扩展。在 Java 开发中常用于保存和管理数据。默认端口号 3306。 MySQL 数据库主要分为 Server 和存储引擎两部分,现在最常用的存储引擎是 InnoDB。 指令执行过程 MySQL 数据库接收到用户指令…...
解锁AI写作新境界:5款工具让你的论文创作事半功倍
在这个数字化飞速发展的时代,人工智能(AI)已经不再是科幻小说中的幻想,而是实实在在地融入了我们的日常生活。特别是在学术领域,AI技术的介入正在改变传统的论文写作方式。你是否还在为撰写论文而熬夜苦战?…...
一文读懂多组学联合分析产品在医学领域的应用
疾病的发生和发展通常涉及多个层面的生物学过程,包括基因表达、蛋白质功能、代谢物变化等。传统的单一组学研究只能提供某一层面的信息,而多组学关联分析能够综合多个层面的数据,提供更全面、更深入的疾病理解。例如,通过分析患者…...
js react 笔记 2
起因, 目的: 记录一些 js, react, css 1. 生成一个随机的 uuid // 需要先安装 crypto 模块 const { randomUUID } require(crypto);const uuid randomUUID(); console.log(uuid); // 输出类似 9b1deb4d-3b7d-4bad-9bdd-2b0d7b3dcb6d 2. 使用 props, 传递参数…...
快速使用react 全局状态管理工具--redux
redux Redux 是 JavaScript 应用中管理应用状态的工具,特别适用于复杂的、需要共享状态的中大型应用。Redux 的核心思想是将应用的所有状态存储在一个单一的、不可变的状态树(state tree)中,状态只能通过触发特定的 action 来更新…...
活动系统开发之采用设计模式与非设计模式的区别-非设计模式
1、父类Base.php <?php /*** 初始化控制器* User: Administrator* Date: 2022/9/26* Time: 18:00*/ declare (strict_types 1); namespace app\controller; use app\model\common\Token; use app\BaseController; use app\BaseError; use OpenSSL\Encrypt; use app\model…...
JVM面试(六)垃圾收集器
目录 概述STW收集器的并发和并行 Serial收集器ParNew收集器Parallel Scavenge收集器Serial Old收集器Parallel Old收集器CMS收集器Garbage First(G1)收集器 概述 上一章我们分析了垃圾收集算法,那这一章我们来认识一下这些垃圾收集器是如何运…...
固态硬盘装系统有必要分区吗?
前言 现在的新电脑有哪一台是不使用固态硬盘的呢?这个好像很少很少了…… 有个朋友买了一台新的笔记本电脑,开机之后,电脑只有一个分区(系统C盘500GB)。这时候她想要给笔记本分区…… 这个真的有必要分区吗…...
网络安全架构师
网络安全架构师负责构建全面的安全框架,以保护组织的数字资产免受侵害,确保组织在数字化转型的同时维持强大的安全防护。 摩根大通的网络安全运营副总裁兼安全架构总监Lester Nichols强调,成为网络安全架构师对现代企业至关重要,…...
如何本地部署Ganache并使用内网穿透配置公网地址远程连接测试网络
目录 前言 1. 安装Ganache 2. 安装cpolar 3. 创建公网地址 4. 公网访问连接 5. 固定公网地址 作者简介: 懒大王敲代码,计算机专业应届生 今天给大家聊聊如何本地部署Ganache并使用内网穿透配置公网地址远程连接测试网络,欢迎大家点赞 &a…...
算法岗/开发岗 实况
深信服算法岗一面 第一题 树的直径有哪些解法 两次dfs和树形dp,讲了一下树形dp的思路 因为我的简历写的比较少,所以面试官问我一些个人信息和擅长哪方面。 我说:ACM大一下打到大三,然后去考研。dp写的多一点,还有思维…...
Nginx跨域运行案例:云台控制http请求,通过 http server 代理转发功能,实现跨域运行。(基于大华摄像头WEB无插件开发包)
文章目录 引言I 跨域运行案例开发资源测试/生产环境,Nginx代理转发,实现跨域运行本机开发运行II nginx的location指令Nginx配置中, 获取自定义请求header头Nginx 配置中,获取URL参数引言 背景:全景监控 需求:感知站点由于云台相关操作为 http 请求,http 请求受浏览器…...
【数据分析预备】Pandas
Pandas 构建在NumPy之上,继承了NumPy高性能的数组计算功能,同时提供更多复杂精细的数据处理功能 安装 pip install pandas导入 import pandas as pdSeries 键值对列表 # 创建Series s1 pd.Series([5, 17, 3, 26, 31]) s10 5 1 17 2 3 3 26 4 31 dt…...
MATLAB-基于高斯过程回归GPR的数据回归预测
目录 目录 1 介绍 1. 1 高斯过程的基本概念 1.2 核函数(协方差函数) 1.3 GPR 的优点 1.4. GPR 的局限 2 运行结果 3 核心代码 1 介绍 高斯过程回归(Gaussian Process Regression, GPR)是一种强大的非参数贝叶斯方法&…...
欧洲国际眼科盛会,中国眼科专家周进斩获六项屈光大奖
2024年第42届欧洲白内障和屈光外科医生协会(ESCRS)大会由世界青光眼协会(WGA)、欧洲白内障和屈光外科医生协会(ESCRS)主办,于2024年9月6日至10日在西班牙巴塞罗那举行。 这场眼科盛会,汇聚了来自全球130多个国家的上万名眼科医学领域的顶尖专家、学者和临…...
MySQL——数据库的高级操作(二)用户管理(2)创建普通用户
在创建新用户之前,可以通过 SELECT 语句查看 mysql.user 表中有哪些用户,查询结果如下: mysql> USE mysql; Database changed mysql> SELECT Host, User, authentication_string FROM mysql.user; ----------------------------------…...
基于算法竞赛的c++编程(28)结构体的进阶应用
结构体的嵌套与复杂数据组织 在C中,结构体可以嵌套使用,形成更复杂的数据结构。例如,可以通过嵌套结构体描述多层级数据关系: struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
java 实现excel文件转pdf | 无水印 | 无限制
文章目录 目录 文章目录 前言 1.项目远程仓库配置 2.pom文件引入相关依赖 3.代码破解 二、Excel转PDF 1.代码实现 2.Aspose.License.xml 授权文件 总结 前言 java处理excel转pdf一直没找到什么好用的免费jar包工具,自己手写的难度,恐怕高级程序员花费一年的事件,也…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
零基础设计模式——行为型模式 - 责任链模式
第四部分:行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习!行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想:使多个对象都有机会处…...
分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
