day52【子序列】300.最长递归子序列 674.最长连续递增序列 718.最长重复子数组
文章目录
- 300.最长递增子序列
- 674.最长连续递增序列
- 718.最长重复子数组
300.最长递增子序列
-
题目链接:力扣链接
-
讲解链接:代码随想录链接
-
题意:给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1:输入:nums = [10,9,2,5,3,7,101,18]输出:4解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。示例 2:输入:nums = [0,1,0,3,2,3]输出:4示例 3:输入:nums = [7,7,7,7,7,7,7]输出:1 -
思路:
- 当前下标i的递增子序列长度,和i之前的下标j的子序列长度有关系。
-
动规五部曲
dp[i]:表示i之前的包括i的,以nums[i]为尾的最长递增子序列的长度
递归公式:下标i的最长升序子序列长度等于下标j从0到i-1各个位置的最长升序子序列+1的最大值,也就是下标i之前的,即到i-1的最长升序子序列长度+下标i本身(+1)的长度。前提条件是,nums[i]>nums[j], 才会触发递归公式,这样才符合升序。dp[i] = Math.max(dp[i], dp[j]+1);
初始化:每个以nums[i]为结尾的子序列的长度最短都是它自己本身,也就是1,所以要把dp数组都初始化为1.
遍历顺序:内外两层遍历都是正序遍历即可
最后返回的结果:不是dp[nums.length-1],应为最后一个元素不一定是在最长子序列里面的,所以最后返回的结果应该去遍历每一个dp[i]找到最大的dp[i]来返回。
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length];//最小的结果就是1int result = 1;//把dp数组都初始化为1;Arrays.fill(dp, 1);for(int i = 0; i < dp.length; i++) {for(int j = 0; j < i; j++) {if(nums[i] > nums[j]) {dp[i] = Math.max(dp[j]+1, dp[i]);}}//找到最长的dp[i]作为结果。result = Math.max(result, dp[i]);}return result;}
}
674.最长连续递增序列
-
题目链接:力扣链接
-
讲解链接:代码随想录讲解
-
题意:给定一个未经排序的整数数组,找到最长且 连续递增的子序列,并返回该序列的长度。
连续递增的子序列 可以由两个下标 l 和 r(l < r)确定,如果对于每个 l <= i < r,都有 nums[i] < nums[i + 1] ,那么子序列 [nums[l], nums[l + 1], …, nums[r - 1], nums[r]] 就是连续递增子序列。
示例 1:输入:nums = [1,3,5,4,7]输出:3解释:最长连续递增序列是 [1,3,5], 长度为3。尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的,因为 5 和 7 在原数组里被 4 隔开。 示例 2:输入:nums = [2,2,2,2,2]输出:1解释:最长连续递增序列是 [2], 长度为1。 -
思路:不同的是求连续递增的最长子序列的长度,这样的话i和i-1比较就行了,而不用引入j,让j在0到i-1中遍历得到最长的。
class Solution {public int findLengthOfLCIS(int[] nums) {//dp[i]代表以下标i为结尾的连续递增的子序列长度int[] dp = new int[nums.length];//初始化,dp[i]最少都应为1Arrays.fill(dp, 1);int res = 1;for(int i = 1; i < nums.length; i++) {//本题求连续增序列,所以就和i-1比较就行了,没必要和j比较,j是从0到i-1遍历。只要i比i-1大,那么最长的长度就得+1,如此一直遍历。 if(nums[i] > nums[i-1]) {dp[i] = Math.max(dp[i], dp[i-1]+1);}res = Math.max(res, dp[i]);}return res;}
}
718.最长重复子数组
-
题目链接:力扣链接
-
讲解链接:代码随想录讲解
-
题意:给两个整数数组 nums1 和 nums2 ,返回 两个数组中 公共的 、长度最长的子数组的长度 。
示例 1:输入:nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]输出:3解释:长度最长的公共子数组是 [3,2,1] 。示例 2:输入:nums1 = [0,0,0,0,0], nums2 = [0,0,0,0,0]输出:5 -
dp数组的含义
二维dp数组来表示两个数组的状态dp[i][j] 表示第一个数组到i-1为结尾,第二个数组到j-1为结尾的两个数组的最长重复子数组的长度。
为什么要以i-1和j-1为结尾,而不是以i和j为结尾呢?
因为如果是以i和j为结尾的话,在初始化时,就要对比nums1[0]和nums2的所有元素是否相等,以此来初始化nums[0][j]这一行,同理也要用相同的方法初始化nums[i][0]这一列。 -
递推公式
当nums1[i-1] == nums2[j-1]时(因为dp数组的定义是表示以i-1和j-1为结尾的,所以这里比较的是i-1和j-1的值相等,这是符合dp数组含义的),dp[i][j]需要加1,dp[i][j] = dp[i-1][j-1]+1,在[i-1][j-1]的基础上做加1,需要同时回退,然后在此基础上做+1的操作。 -
初始化
根据dp数组的定义,i和j为0时,dp数组表示以-1为结尾的,这是没有意义的,所以初始化为0,重复的长度如果有了就从0开始往上加,这样才正确。因为遍历时会把后面的初始值覆盖,所以其他初始值为多少都可以,但为方便统一设置为0.
dp[i][0] = 0
dp[0][j] = 0 -
遍历顺序
要遍历两个数组,两层for循环。遍历dp数组,找到最大值返回。
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length+1][nums2.length+1];int res = 0;for(int i = 1; i <= nums1.length; i++) {for(int j = 1; j<= nums2.length; j++) {if(nums1[i-1] == nums2[j-1]) {dp[i][j] = Math.max(dp[i][j], dp[i-1][j-1]+1);}res = Math.max(res, dp[i][j]);}}return res;}
}
相关文章:
day52【子序列】300.最长递归子序列 674.最长连续递增序列 718.最长重复子数组
文章目录 300.最长递增子序列674.最长连续递增序列718.最长重复子数组 300.最长递增子序列 题目链接:力扣链接 讲解链接:代码随想录链接 题意:给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而…...
计算机视觉 计算机视觉识别是什么?
计算机视觉识别(Computer Vision Recognition)是计算机科学和人工智能领域中的一个重要分支,它致力于使计算机系统能够模拟和理解人类视觉的过程,从而能够自动识别、分析和理解图像或视频中的内容。这一领域的发展旨在让计算机具备…...
Make.com实现多个APP应用的自动化的入门指南
Make.com是一款基于云的自动化平台,可帮助用户将多个应用程序连接在一起,并通过设置自动化流程来简化日常任务。Make.com提供丰富的API集成,支持连接各种流行的应用程序,包括社交媒体、电子商务、CRM等。 使用Make.com实现多个AP…...
LLMs之HFKR:HFKR(基于大语言模型实现异构知识融合的推荐算法)的简介、原理、性能、实现步骤、案例应用之详细攻略
LLMs之HFKR:HFKR(基于大语言模型实现异构知识融合的推荐算法)的简介、原理、性能、实现步骤、案例应用之详细攻略 目录 HFKR的简介 异构知识融合:一种基于LLM的个性化推荐新方法...
多模态 多引擎 超融合 新生态!2023亚信科技AntDB数据库8.0产品发布
9月20日,以“多模态 多引擎 超融合 新生态”为主题的亚信科技AntDB数据库8.0产品发布会成功举办,从技术和生态两个角度全方位展示了AntDB数据库第8次大型能力升级和生态建设成果。浙江移动、用友、麒麟软件、华录高诚、金云智联等行业伙伴及业界专家共同…...
elasticsearch无法访问9200端口
近期部署elasticsearch后,启动时发现一直报如下错误: curl: (7) Failed connect to localhost:9200; Connection refused 部署的版本为elasticsearch-7.13.2,排查原因是因为开启了ssl认证。 解决方法: 在/opt/software/elasticsearch-7.13.2/config下…...
【Linux】进程等待
文章目录 进程等待进程等待必要性实验(见见猪跑)进程等待的方法wait方法waitpid**方法**宏的使用方法获取子进程status 阻塞VS非阻塞概念对比非阻塞有什么好处 具体代码实现进程的阻塞等待方式:进程的非阻塞等待方式:让父进程做其他任务 进程等待 进程等待必要性 之前讲过&am…...
电视「沉浮录」:跌出家电“三大件”?
【潮汐商业评论/原创】 “这年头谁还看电视,家里电视近一年都没打开过了,我明天就打算把它二手卖掉。”想到已落灰许久的电视机,Andy打开了二手平台。 “要不是这几年孩子网课多,我是真没考虑换新电视,家里用了8年的…...
前端实现调用打印机和小票打印(TSPL )功能
Ⅰ- 壹 - 使用需求 前端 的方式 点击这个按钮,直接让打印机打印我想要的东西 Ⅱ - 贰 - 小票打印 目前比较好的方式就是直接用 TSPL 标签打印指令集, 基础环境就不多说了,这个功能的实现就是利用usb发送指令,现在缺少个来让我们能够和usb沟通的工具,下面这就是推…...
串口通信(6)应用定时器中断+串口中断实现接收一串数据
本文为博主 日月同辉,与我共生,csdn原创首发。希望看完后能对你有所帮助,不足之处请指正!一起交流学习,共同进步! > 发布人:日月同辉,与我共生_单片机-CSDN博客 > 欢迎你为独创博主日月同…...
【WinForm详细教程六】WinForm中的GroupBox和Panel 、TabControl 、SplitContainer控件
文章目录 1.GroupBox和Panel2.TabControl3.SplitContainer 1.GroupBox和Panel GroupBox:是一个分组容器,提供一个框架将相关的控件组织在一起,它有标题、边框,但没有滚动条。 Panel:也是一个容器控件,用来…...
gradle与maven
Gradle 和 Maven 都是流行的构建工具,通常用于构建和管理 Java 和 Android 项目。它们都可以自动下载依赖库、编译代码、运行测试、打包和发布等。 以下是对 Gradle 和 Maven 的介绍: Gradle: Gradle 是一个基于 Groovy 和 Kotlin 的构建自…...
2.Docker基本架构简介与安装实战
1.认识Docker的基本架构 下面这张图是docker官网上的,介绍了整个Docker的基础架构,我们根据这张图来学习一下docker的涉及到的一些相关概念。 1.1 Docker的架构组成 Docker架构是由Client(客户端)、Docker Host(服务端)、Registry(远程仓库)组成。 …...
拓世法宝 | 数字经济崛起,美业如何抓住流量风口?
爱美之心,人皆有之。无论男女,都会很自然地对美好事物燃起兴致,跟高颜值相关的事物总能聚集注意力。例如直播平台里的美女网红收割流量赚得盆满钵满,面庞俊俏的年轻偶像吸引万千粉丝,还有“央视最美记者”王冰冰、“最…...
Scala 泛型编程
1. 泛型 Scala 支持类型参数化,使得我们能够编写泛型程序。 1.1 泛型类 Java 中使用 <> 符号来包含定义的类型参数,Scala 则使用 []。 class Pair[T, S](val first: T, val second: S) {override def toString: String first ":" sec…...
索引失效的场景有哪些?
虽然你这列上建了索引,查询条件也是索引列,但最终执行计划没有走它的索引。下面是引起这种问题的几个关键点。 列与列对比 某个表中,有两列(id和c_id)都建了单独索引,下面这种查询条件不会走索引 select…...
Java进阶04 final关键字、abstract抽象、interface接口、JDK8与JDK9中接口的区别、内部类和匿名类
文章目录 一、final关键字二、abstract关键字三、接口interface四、JDK8和JDK9中接口的区别五、内部类 一、final关键字 final可以修饰类、方法、变量 用final修饰类 表示此类不能被继承 用final修饰方法 表示方法不可以被重写 用final修饰变量 既可以修饰成员变量也可以修饰…...
Python的web自动化学习(五)Selenium的隐式等待(元素定位)
引言: WebDriver隐式等待是一种全局性的等待方式,它会在查找元素时设置一个固定的等待时间。当使用隐式等待时,WebDriver会在查找元素时等待一段时间,如果在等待时间内找到了元素,则立即执行下一步操作;如果…...
20231102从头开始配置cv180zb的编译环境(欢迎入坑,肯定还有很多问题等着你)
20231102从头开始配置cv180zb的编译环境(欢迎入坑,肯定还有很多问题等着你) 2023/11/2 11:31 (欢迎入坑,本篇只是针对官方的文档整理的!只装这些东西你肯定编译不过的,还有很多问题等着你呢&…...
CentOS 安装HTTP代理服务器 Squid
参考:大部分摘自此文,做了少部分修改 Squid 是一个功能全面的缓存代理服务器,它支持著名的网络协议像 HTTP,HTTPS,FTP 等等。将 Squid 放在网页服务器的前端,通过缓存重复请求,过滤网络流量等&…...
盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来
一、破局:PCB行业的时代之问 在数字经济蓬勃发展的浪潮中,PCB(印制电路板)作为 “电子产品之母”,其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透,PCB行业面临着前所未有的挑战与机遇。产品迭代…...
基于服务器使用 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…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比
目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec? IPsec VPN 5.1 IPsec传输模式(Transport Mode) 5.2 IPsec隧道模式(Tunne…...
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南
精益数据分析(97/126):邮件营销与用户参与度的关键指标优化指南 在数字化营销时代,邮件列表效度、用户参与度和网站性能等指标往往决定着创业公司的增长成败。今天,我们将深入解析邮件打开率、网站可用性、页面参与时…...
GC1808高性能24位立体声音频ADC芯片解析
1. 芯片概述 GC1808是一款24位立体声音频模数转换器(ADC),支持8kHz~96kHz采样率,集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器,适用于高保真音频采集场景。 2. 核心特性 高精度:24位分辨率,…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
