力扣第300题 最长递增子序列 c++ 动态规划题 附Java代码
题目
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
提示:
1 <= nums.length <= 2500-104 <= nums[i] <= 104
进阶:
- 你能将算法的时间复杂度降低到
O(n log(n))吗?
思路和解题方法
if(nums.size()<=1) return nums.size();:特判,如果数组nums长度为0或1,直接返回其长度。vector<int> dp(nums.size(), 1);:创建一个大小为nums长度的数组dp,用于存储以nums[i]结尾的最长上升子序列的长度。初始值全部赋为1,因为每个元素本身也可以构成一个长度为1的上升子序列。int ans = 0;:初始化最长上升子序列的长度为0。for(int i = 1; i < nums.size(); i++):从第二个元素开始遍历数组nums。for(int j = 0; j < i; j++):在i之前的元素中,找到比nums[i]小的元素。if(nums[i] > nums[j]):如果nums[i]大于nums[j],则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中。dp[i] = max(dp[i], dp[j] + 1);:更新以nums[i]结尾的最长上升子序列的长度。当前位置的值为前面比它小的元素中以每个元素结尾的最长上升子序列长度的最大值+1。if(ans < dp[i]) ans = dp[i];:更新最长上升子序列的长度。return ans;:返回最长上升子序列的长度。
复杂度
时间复杂度:
O(n*n)
时间复杂度分析: 代码中使用了两重循环,时间复杂度为O(n^2)。
其中,内层循环每次迭代都会执行常数个操作(比较和更新dp数组),因此时间复杂度为O(1)。
外层循环的迭代次数为n-1,因此时间复杂度为O(n)。
因此,算法的总时间复杂度为O(n^2)。
空间复杂度
O(n)
空间复杂度分析: 代码中使用了一个长度为n的dp数组,因此空间复杂度为O(n)。
c++ 代码
class Solution {
public:int lengthOfLIS(vector<int>& nums) {if(nums.size()<=1) return nums.size();vector<int> dp(nums.size(), 1); // 创建一个dp数组,用于存储以nums[i]结尾的最长上升子序列的长度,默认初始为1int ans = 0; // 初始化最长上升子序列的长度为0for(int i = 1; i < nums.size(); i++) // 遍历数组nums{for(int j = 0; j < i; j++) // 在i之前的元素中,找到比nums[i]小的元素{if(nums[i] > nums[j]) // 如果nums[i]大于nums[j],则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中dp[i] = max(dp[i], dp[j] + 1); // 更新以nums[i]结尾的最长上升子序列的长度}if(ans < dp[i]) // 更新最长上升子序列的长度ans = dp[i];}return ans; // 返回最长上升子序列的长度}
};
Java代码
class Solution {public int lengthOfLIS(int[] nums) {int[] dp = new int[nums.length]; // 创建一个大小为nums.length的数组dp,用于存储以nums[i]结尾的最长上升子序列的长度,默认初始为1int res = 0; // 初始化最长上升子序列的长度为0Arrays.fill(dp, 1); // 将dp数组中的元素全部赋值为1for (int i = 1; i < dp.length; i++) { // 遍历数组nums,从第二个元素开始for (int j = 0; j < i; j++) { // 在i之前的元素中,找到比nums[i]小的元素if (nums[i] > nums[j]) { // 如果nums[i]大于nums[j],则可以将nums[i]加入到以nums[j]结尾的最长上升子序列中dp[i] = Math.max(dp[i], dp[j] + 1); // 更新以nums[i]结尾的最长上升子序列的长度}res = Math.max(res, dp[i]); // 更新最长上升子序列的长度}}return res; // 返回最长上升子序列的长度}
}
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。
相关文章:
力扣第300题 最长递增子序列 c++ 动态规划题 附Java代码
题目 300. 最长递增子序列 中等 相关标签 数组 二分查找 动态规划 给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例…...
Si3262 集成低功耗SOC 三合一智能门锁应用芯片
Si3262 是一款G度集成的低功耗 SOC 芯片,其集成了基于 RISC-V 核的低功耗MCU 和工作在 13.56MHz 的非接触式读写器模块。 读写器模块支持 ISO/IEC 14443 A/B/MIFARE 协议,支持自动载波侦测功能(ACD)。无需外W其他电路,…...
linux rsyslog介绍
Rsyslog网址:https://www.rsyslog.com/ Rsyslog is the rocket-fast system for log processing. It offers high-performance, great security features and a modular design. While it started as a regular syslogd, rsyslog has evolved into a kind of swis…...
项目部署之安装和配置Canal
1.Canal介绍 Canal是阿里巴巴的一个开源项目,基于java实现,整体已经在很多大型的互联网项目生产环境中使用,包括阿里、美团等都有广泛的应用,是一个非常成熟的数据库同步方案,基础的使用只需要进行简单的配置即可。 …...
基于Skywalking的全链路跟踪实现
在前文“分布式应用全链路跟踪实现”中介绍了分布式应用全链路跟踪的几种实现方法,本文将重点介绍基于Skywalking的全链路实现,包括Skywalking的整体架构和基本概念原理、Skywalking环境部署、SpringBoot和Python集成Skywalking监控实现等。 1、Skywalki…...
Spark Core
Spark Core 本文来自 B站 黑马程序员 - Spark教程 :原地址 第一章 RDD详解 1.1 为什么需要RDD 分布式计算需要 分区控制shuffle控制数据存储、序列化、发送数据计算API等一系列功能 这些功能,不能简单的通过Python内置的本地集合对象(如…...
[算法日志]图论: 广度优先搜索(BFS)
[算法日志]图论: 广度优先搜索(BFS) 广度优先概论 广度优先遍历也是一种常用的遍历图的算法策略,其思想是将本节点相关联的节点都遍历一遍后才切换到相关联节点重复本操作。这种遍历方式类似于对二叉树节点的层序遍历,即先遍历完子节点后…...
Xilinx FPGA SPIx4 配置速度50M约束语句(Vivado开发环境)
qspi_50m.xdc文件: set_property BITSTREAM.GENERAL.COMPRESS TRUE [current_design] set_property BITSTREAM.CONFIG.SPI_BUSWIDTH 4 [current_design] set_property BITSTREAM.CONFIG.CONFIGRATE 50 [current_design] set_property CONFIG_VOLTAGE 3.3 [curren…...
Linux Shell和权限
目录 Shell命令及运行原理 权限 1.文件基本属性 2.文件权限值的表示方法 3.文件访问权限的相关设置方法 3.(1)chmod 组名修改 3.(2)chmod 二进制修改 3.(3)chown 3.(4)chgrp 3.(5)umask 4.目录权限 Shell命令及运行原理 Linux的操作系统,狭义上是…...
Git同时配置Gitee和GitHub
Git同时配置Gitee和GitHub 一、删除原先ssh密钥二、生成密钥 这里的同时配置是针对于之前配置过单个gitee或者github而言的,如果需要看git从安装开始的配置,则可以看这一篇文章 git安装配置教程 一、删除原先ssh密钥 在C盘下用户/用户名/.ssh文件下找到…...
IGP高级特性简要介绍(OSPF-上篇)
OSPF高级特性 一、OSPF_提升故障收敛及网络恢复速度 1.FRR与BFD快速恢复故障 1.1 FRR 在传统转发模式下,当到达同一个目的网络存在多条路由时,路由器总是选择最优路由使用,并且下发到FIB表指导数据转发。 当最优路由故障时,需…...
Oracle-Ogg集成模式降级为经典模式步骤
前言: Ogg集成模式降级为经典模式的场景比较少,因为降级为经典模式会导致无法支持压缩表同步,XA事务,多线程模式,PDB模式同步等功能,除非遇到集成模式暂时无法解决的bug或者环境不支持集成模式,比如DG备库环…...
链表面试OJ题(1)
今天讲解两道链表OJ题目。 1.链表的中间节点 给你单链表的头结点 head ,请你找出并返回链表的中间结点。 如果有两个中间结点,则返回第二个中间结点。 示例 输入:head [1,2,3,4,5] 输出:[3,4,5] 解释:链表只有一个…...
[极客大挑战 2019]Upload 1
题目环境: 根据题目和环境可知此题目是一道文件上传漏洞 编写一句话木马脚本<?php eval($_POST[shell]);?>将脚本文件更改为jpg图片文件我这里是flag.jpg上传文件并burpsuite抓包Repeater重放 报错一句话木马里面有<?字符 换一种一句话木马继续编写木马…...
OpenFeign讲解+面试题
一:OpenFeign是什么? 是一个声明式的web客户端,只需要创建一个接口,添加注解即可完成微服务之间的调用 二:调用微服务的方式? ribbon restTemplate方式调用openFeign通过接口注解的方式调用 三:如何使用OpenFeign&…...
嬴图 | LLM+Graph:大语言模型与图数据库技术的协同
前言 2022年11月以来,大语言模型席卷全球,在自然语言任务中表现卓越。尽管存在一系列伦理、安全等方面的担心,但各界对该技术的热情和关注并未减弱。 本文不谈智能伦理方面的问题,仅集中于Ulitpa嬴图在应用中的一些探索与实践&a…...
微信小程序下载文件和转发文件给好友总结
这段时间公司让我负责小程序的一些功能开发,回想上次开发小程序还是在上一次,这次开发小程序主要实现的功能就是转发文件给好友和下载文件,总结一下这次遇到的各种问题和解决方法。 下载文件 首先正常下载 wx.downloadFile({url: https://img.haihaina.cn/月度支出表.xls,…...
一文掌握 Apache SkyWalking
Apache SkyWalking SkyWalking是一个开源可观测平台,用于收集、分析、聚合和可视化来自服务和云原生基础设施的数据。SkyWalking 提供了一种简单的方法来保持分布式系统的清晰视图,甚至跨云。它是一种现代APM,专为云原生、基于容器的分布式系…...
外贸网站优化常用流程和一些常识
外贸网站google排名,总以为是单个网页标签的优化过程。 显然,这些观点都是错误的,九凌网络是做谷歌优化服务,九凌网络跟大家分享外贸网站Google优化常用流程和一些常识需要做以下几个步骤: 第一步:网站诊断࿰…...
Hive的时间操作函数
目录 前言函数使用介绍实际使用判断该天是星期几判断该天对应的周(包含一周开始和结束) 前言 hive 里面的时间函数有很多,今天单讲dayofweek函数,背景:有时候不仅要出日报,还要出周报,需要很多…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
Mac软件卸载指南,简单易懂!
刚和Adobe分手,它却总在Library里给你写"回忆录"?卸载的Final Cut Pro像电子幽灵般阴魂不散?总是会有残留文件,别慌!这份Mac软件卸载指南,将用最硬核的方式教你"数字分手术"࿰…...
Psychopy音频的使用
Psychopy音频的使用 本文主要解决以下问题: 指定音频引擎与设备;播放音频文件 本文所使用的环境: Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
ardupilot 开发环境eclipse 中import 缺少C++
目录 文章目录 目录摘要1.修复过程摘要 本节主要解决ardupilot 开发环境eclipse 中import 缺少C++,无法导入ardupilot代码,会引起查看不方便的问题。如下图所示 1.修复过程 0.安装ubuntu 软件中自带的eclipse 1.打开eclipse—Help—install new software 2.在 Work with中…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)
上一章用到了V2 的概念,其实 Fiori当中还有 V4,咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务),代理中间件(ui5-middleware-simpleproxy)-CSDN博客…...
基于IDIG-GAN的小样本电机轴承故障诊断
目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) 梯度归一化(Gradient Normalization) (2) 判别器梯度间隙正则化(Discriminator Gradient Gap Regularization) (3) 自注意力机制(Self-Attention) 3. 完整损失函数 二…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
