day52|● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组
300.最长递增子序列
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.
这题看似简单,但感觉没想明白递增的判定(当前下标i的递增子序列长度,其实和i之前的下表j的子序列长度有关系)和递推的关系
“子序列是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序”。注意 这里是找递增子序列,他的递增可以是不连续的。
dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度
注意是以nums[i]结尾,和nums[j]比较(j在0到i之间),取最大的长度值
并非dp[i] 与 dp[j] + 1进行比较,而是我们要取dp[j] + 1的最大值。
需要把视角抽离出来,发现要求到当前i位置的最长递增子序列,其实依靠的是到他之前所有递增子序列长度的最大值,重点在[0 : i) 之前的所有dp

class Solution {public int lengthOfLIS(int[] nums) {// dp[i] the length of the longest increasing subsequence ending with nums[i]// dp[i]是以nums[i]为子序列尾元素的最长递增子序列的长度int[] dp = new int[nums.length];for (int i = 0; i < dp.length; i++) {dp[i] = 1;}int maxLength = 1;for (int i = 1; i < nums.length; i++) {for (int j = 0; j < i; j++) { // 着重注意理解这个forif (nums[i] > nums[j]){dp[i] = Math.max(dp[i], dp[j]+1);}}maxLength = dp[i] > maxLength ? dp[i]:maxLength;}return maxLength;}
}
时间复杂度: O(n^2)
空间复杂度: O(n)
674. 最长连续递增序列
dp[i]:以下标i为结尾的连续递增的子序列长度为dp[i]。
因为本题要求连续递增子序列,所以就只要比较nums[i]与nums[i - 1],而不用去比较nums[j]与nums[i] (j是在0到i之间遍历)。
既然不用j了,那么也不用两层for循环,本题一层for循环就行,比较nums[i] 和 nums[i - 1]。
class Solution {public int findLengthOfLCIS(int[] nums) {int[] dp = new int[nums.length];for (int i = 0; i < nums.length; i++) {dp[i] = 1;}int res = 1;for (int i = 1; i < nums.length; i++) {if (nums[i] > nums[i-1]) {dp[i] = dp[i-1]+1;}res = Math.max(res, dp[i]);}return res;}
}
时间复杂度:O(n)
空间复杂度:O(n)
718. 最长重复子数组
dp[i][j] :以下标i 为结尾的nums1,和以下标j 为结尾的nums2,最长重复子数组长度为dp[i][j]。
(特别注意: “以下标i 为结尾的A” 标明一定是 以A[i]为结尾的字符串 )
class Solution {public int findLength(int[] nums1, int[] nums2) {int[][] dp = new int[nums1.length][nums2.length];int maxLength = 0;for (int i = 0; i < nums1.length; i++) {for (int j = 0; j < nums2.length; j++) {if (nums1[i] == nums2[j]) {if (i==0 || j==0) {dp[i][j] = 1;} else {dp[i][j] = dp[i-1][j-1]+1;}}maxLength = Math.max(maxLength, dp[i][j]);}}return maxLength;}
}
相关文章:
day52|● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组
300.最长递增子序列 Input: nums [10,9,2,5,3,7,101,18] Output: 4 Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4. 这题看似简单,但感觉没想明白递增的判定(当前下标i的递增子序列长度,其实…...
uniapp,vue3路由传递接收参数
官网vue2升vue3的教程中,演示了如何使用onLoad,记得把官网所有内容都看一遍!!! 传递对象参数 uni.navigateTo({url: /pages/login/code/code?data JSON.stringify({limit: 6, iphone: loginForm.username, }), });…...
SkyEye与Jenkins的DevOps持续集成解决方案
在技术飞速发展的当下,随着各行各业的软件逻辑复杂程度提升带来的需求变更,传统测试已无法满足与之相对应的一系列测试任务,有必要引入一个自动化、可持续集成构建的DevOps平台来解决此类问题。本文将主要介绍SkyEye与Jenkins的持续集成解决方…...
HCIE Security——防火墙互联技术
目录 一、防火墙接口互联接口 1.防火墙支持的接口及板卡 2.物理链接线缆 3.支持接口种类 (1)物理接口 (2)逻辑接口 二、相关配置命令 1.配置三层接口IP地址 2.配置PPPOE拨号接口 3.配置VLANIF接口、子接口、回环接口 4…...
Rust- 闭包
A closure in Rust is an anonymous function you can save in a variable or pass as an argument to another function. You can create the closure using a lightweight syntax and access variables from the scope in which it’s defined. Here’s an example of a clo…...
【数据挖掘torch】 基于LSTM电力系统负荷预测分析(Python代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
「JVM」性能调优工具
「JVM」性能调优工具 一、jcmd1、jcmd 能干嘛?2、与JVM相关的命令3、示例 二、jmap1、jmap有什么用?2、jmap的命令大全3、示例 三、jps1、jps有什么用?2、jps命令以及示例 四、jstat1、jstat有什么用?2、jstat命令以及示例 五、js…...
IDEA Debug小技巧 添加减少所查看变量、查看不同线程
问题 IDEA的Debug肯定都用过。它下面显示的变量,有什么门道?可以增加变量、查看线程吗? 答案是:可以。 演示代码 代码如下: package cn.itcast.attempt.threadAttempt.attempt2;public class Test {public static …...
基于SpringBoot+Vue的车辆充电桩管理系统设计与实现(源码+LW+部署文档等)
博主介绍: 大家好,我是一名在Java圈混迹十余年的程序员,精通Java编程语言,同时也熟练掌握微信小程序、Python和Android等技术,能够为大家提供全方位的技术支持和交流。 我擅长在JavaWeb、SSH、SSM、SpringBoot等框架…...
Bean的加载方式
目录 1. 基于XML配置文件 2. 基于XML注解方式声明bean 自定义bean 第三方bean 3.注解方式声明配置类 扩展1,FactoryBean 扩展2,加载配置类并加载配置文件(系统迁移) 扩展3,proxyBeanMethodstrue的使用 4. 使用Import注解导入要注入的bean…...
《吐血整理》进阶系列教程-拿捏Fiddler抓包教程(13)-Fiddler请求和响应断点调试
1.简介 Fiddler有个强大的功能,可以修改发送到服务器的数据包,但是修改前需要拦截,即设置断点。设置断点后,开始拦截接下来所有网页,直到取消断点。这个功能可以在数据包发送之前,修改请求参数;…...
Android 13(T) - Media框架(1)- 总览
从事Android Media开发工作三年有余,刚从萌新变成菜鸟,一路上跌跌撞撞学习,看了很多零零碎碎的知识,为了加深对Android Media框架的理解,决定在这里记录下学习过程中想到的一些问题以及一些思考,也希望对初…...
简述vue3(ts)+antdesignvue项目框架搭建基本步骤
目录 项目简介 概念 过程简述 基本步骤 1.创建新项目 2.安装Ant Design Vue 3.配置Ant Design Vue 4.创建页面和组件 5.使用组件 6.运行项目 项目简介 概念 Vue 3(使用TypeScript)和Ant Design Vue项目框架搭建是指在Vue 3框架下,…...
webpack : 无法加载文件 C:\Program Files\nodejs\webpack.ps1
webpack : 无法加载文件 C:\Program Files\nodejs\webpack.ps1 1.问题2. 解决办法: 1.问题 使用webpack打包是报错如下: webpack : 无法加载文件 C:\Program Files\nodejs\webpack.ps1,因为在此系统上禁止运行脚本。有关详细信息,…...
GDAL OGR C++ API 学习之路 (5)OGRLayer篇 代码示例
GetStyleTable virtual OGRStyleTable *GetStyleTable () 返回图层样式表 返回: 指向不应由调用方修改或释放的样式表的指针 // 假设图层对象为 poLayer OGRStyleTable* poStyleTable poLayer->GetStyleTable(); if (poStyleTable ! nullptr) {// 处理样式表信息// ..…...
NIDEC COMPONENTS尼得科科宝滑动型DIP开关各系列介绍
今天AMEYA360对尼得科科宝电子滑动型DIP开关各系列参数进行详细介绍,方便大家选择适合自己的型号。 系列一、滑动型DIP开关 CVS 针脚数:1, 2, 3, 4, 8 安装类型:表面贴装,通孔 可水洗:无 端子类型:PC引脚(只…...
一起学算法(滑动窗口篇)
前言: 对于滑动窗口,有长度固定的窗口,也有长度可变的窗口,一般是基于数组进行求解,对于一个数组中两个相邻的窗口,势必会有一大部分重叠,这部分重叠的内容是不需要重复计算的,所以我…...
HTML <q> 标签
实例 标记短的引用: <q>Here is a short quotation here is a short quotation</q>浏览器支持 元素ChromeIEFirefoxSafariOpera<q>YesYesYesYesYes所有浏览器都支持 <q> 标签。 定义和用法 <q> 标签定义短的引用。 浏览器经常在引用的内容…...
机器学习02-再识K邻近算法(自定义数据集训练及测试)
定义: 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。简单的说就是根据你的“邻居”来推断出你的类别。 用个成语就是物以类聚 思想: 如果一个样本在特征空间中的K个最…...
github使用笔记及git协作常用命令
1.Github有一个主库,每个人自己也有一个库,称为分支。 2.Github的协作流程:先从主库fork出自己的分支, 然后进行代码的修改等操作, 操作完之后从本地库上推到自己的服务器分支,然后 服务器分支Pull Request到 主库。 3.本地仓库由git维护的三棵“树"组成:第1个…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
【决胜公务员考试】求职OMG——见面课测验1
2025最新版!!!6.8截至答题,大家注意呀! 博主码字不易点个关注吧,祝期末顺利~~ 1.单选题(2分) 下列说法错误的是:( B ) A.选调生属于公务员系统 B.公务员属于事业编 C.选调生有基层锻炼的要求 D…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
12.找到字符串中所有字母异位词
🧠 题目解析 题目描述: 给定两个字符串 s 和 p,找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义: 若两个字符串包含的字符种类和出现次数完全相同,顺序无所谓,则互为…...
HTML前端开发:JavaScript 常用事件详解
作为前端开发的核心,JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例: 1. onclick - 点击事件 当元素被单击时触发(左键点击) button.onclick function() {alert("按钮被点击了!&…...
Java多线程实现之Thread类深度解析
Java多线程实现之Thread类深度解析 一、多线程基础概念1.1 什么是线程1.2 多线程的优势1.3 Java多线程模型 二、Thread类的基本结构与构造函数2.1 Thread类的继承关系2.2 构造函数 三、创建和启动线程3.1 继承Thread类创建线程3.2 实现Runnable接口创建线程 四、Thread类的核心…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
