算法刷题: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; ----------------------------------…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
XCTF-web-easyupload
试了试php,php7,pht,phtml等,都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接,得到flag...
Android Wi-Fi 连接失败日志分析
1. Android wifi 关键日志总结 (1) Wi-Fi 断开 (CTRL-EVENT-DISCONNECTED reason3) 日志相关部分: 06-05 10:48:40.987 943 943 I wpa_supplicant: wlan0: CTRL-EVENT-DISCONNECTED bssid44:9b:c1:57:a8:90 reason3 locally_generated1解析: CTR…...
【杂谈】-递归进化:人工智能的自我改进与监管挑战
递归进化:人工智能的自我改进与监管挑战 文章目录 递归进化:人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管?3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...
【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器
——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的一体化测试平台,覆盖应用全生命周期测试需求,主要提供五大核心能力: 测试类型检测目标关键指标功能体验基…...
如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...
Vue2 第一节_Vue2上手_插值表达式{{}}_访问数据和修改数据_Vue开发者工具
文章目录 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染2. 插值表达式{{}}3. 访问数据和修改数据4. vue响应式5. Vue开发者工具--方便调试 1.Vue2上手-如何创建一个Vue实例,进行初始化渲染 准备容器引包创建Vue实例 new Vue()指定配置项 ->渲染数据 准备一个容器,例如: …...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
企业如何增强终端安全?
在数字化转型加速的今天,企业的业务运行越来越依赖于终端设备。从员工的笔记本电脑、智能手机,到工厂里的物联网设备、智能传感器,这些终端构成了企业与外部世界连接的 “神经末梢”。然而,随着远程办公的常态化和设备接入的爆炸式…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
