力扣第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函数,背景:有时候不仅要出日报,还要出周报,需要很多…...
Java 语言特性(面试系列1)
一、面向对象编程 1. 封装(Encapsulation) 定义:将数据(属性)和操作数据的方法绑定在一起,通过访问控制符(private、protected、public)隐藏内部实现细节。示例: public …...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八
现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet,点击确认后如下提示 最终上报fail 解决方法 内核升级导致,需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
【Go】3、Go语言进阶与依赖管理
前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课,做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程,它的核心机制是 Goroutine 协程、Channel 通道,并基于CSP(Communicating Sequential Processes࿰…...
Python爬虫(一):爬虫伪装
一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...
Linux-07 ubuntu 的 chrome 启动不了
文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了,报错如下四、启动不了,解决如下 总结 问题原因 在应用中可以看到chrome,但是打不开(说明:原来的ubuntu系统出问题了,这个是备用的硬盘&a…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
