当前位置: 首页 > news >正文

LeetCode【300】最长递增子序列

题目:
在这里插入图片描述

思路:

  • 通常来说,子序列不要求连续,而子数组或子字符串必须连续;
  • 对于子序列问题,第一种动态规划方法是,定义 dp 数组,其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后,统计一遍各个位置的结果即可得到题目要求的结果。
  • 在本题中, dp[i] 可以表示为以 i 结尾的、最长子序列长度。对于每个位置 i ,如果其之前的某个位置 j 所对应的数字小于位置 i 所对应的数字 ,则我们可以获得一个以 i 结尾、长度为 dp[j] + 1 的子序列。为了遍历所有情况,我们需要对 i 和 j 进行两层循环,其时间复杂度为 O(n2)。

参考:
https://blog.csdn.net/weixin_43894455/article/details/130477427
https://blog.csdn.net/qfc_128220/article/details/127931755

代码:

public int lengthOfLIS(int[] nums) {//动态规划表int[] dp = new int[nums.length];// dp[0] = 1; // 这里不行,考虑为什么?int max = 1;for (int i = 0; i < nums.length; i++) {//base case 每个位置本身长度dp[i] = 1;for (int j = 0; j < i; j++) {// i 位置依次向前比 ,比j 位置大,就是 1 + dp[i]// 根据不同j位置上的数,来更新最大值if (nums[i] > nums[j]) {      // 注意,这里比较的是 nums ,不是dp数组dp[i] = Math.max(dp[i], 1 + dp[j]);max = Math.max(max, dp[i]);}}}return max;}

相关文章:

LeetCode【300】最长递增子序列

题目&#xff1a; 思路&#xff1a; 通常来说&#xff0c;子序列不要求连续&#xff0c;而子数组或子字符串必须连续&#xff1b;对于子序列问题&#xff0c;第一种动态规划方法是&#xff0c;定义 dp 数组&#xff0c;其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个…...

JRebel在IDEA中实现热部署 (JRebel实用版)

JRebel简介&#xff1a; JRebel是与应用程序服务器集成的JVM Java代理&#xff0c;可使用现有的类加载器重新加载类。只有更改的类会重新编译并立即重新加载到正在运行的应用程序中&#xff0c;JRebel特别不依赖任何IDE或开发工具&#xff08;除编译器外&#xff09;。但是&…...

uniapp微信小程序之分包异步化之组件分包

一、组件分包异步化解决的问题 日渐增加的通用组件造成的主包空间不足; 提升小程序访问速度,降低白屏率; 二、开启组件分包异步化过程中遇到的问题 如何进行占位组件配置; 如何解决通过$refs访问异步组件报错; 如何判断所有异步组件都已加载完毕; 多分包组件之间互相调用…...

Nacos(替代Eureka)注册中心

Nacos初步学习 Nacos 是一个开源的服务注册和配置中心&#xff0c;它允许您注册、注销和发现服务实例&#xff0c;并提供了配置管理的功能。下面是Nacos的最基础用法&#xff1a; 1. 服务注册和发现&#xff1a; 首先&#xff0c;您需要将您的应用程序或服务注册到Nacos中。…...

FHRP首跳冗余的解析

首跳冗余的解析 个人简介 HSRP hot standby router protocol 热备份路由协议 思科设备上 HSRP VRRP 华为设备上 VRRP HSRP v1 version 1 HSRP v2 version 2 虚拟一个HSRP虚拟IP地址 192.168.1.1 开启HSRP的抢占功能 通过其他参数 人为调整谁是主 谁是从 &a…...

垂直分表为什么能够加快查询效率?

前言 垂直分表是分库分表中分表操作上一个重要的实现方式&#xff0c;利用垂直分表可以提高数据的处理效率和查询速度&#xff0c;本节主要围绕 垂直分表为什么能够加快查询速度 展开说明&#xff0c;以mysql查询的底层流程为例。 垂直分表是将一张表按列分为多张表&#xff0c…...

Linux网络基础知识全面总结

文章目录 linux网络基础知识1.1 IP地址和子网掩码1.2 网关和路由1.3 域名系统 (DNS)1.4 端口和协议 Linux网络配置2.1 ifconfig命令2.2 网络接口配置文件2.3 DHCP自动获取IP地址2.4 静态IP地址配置2.5 网络重启和应用配置3. 网络工具和命令3.1 ping命令3.2 traceroute和mtr命令…...

【arm实验2】按键中断事件控制实验

设置按键中断&#xff0c;按键1按下&#xff0c;LED亮&#xff0c;再次按下&#xff0c;灭 按键2按下&#xff0c;蜂鸣器叫&#xff0c;再次按下&#xff0c;停 按键3按下&#xff0c;风扇转&#xff0c;再次按下&#xff0c;停 主函数&#xff1a; linuxlinux:~/study/08-c$…...

【数据结构-栈 二】【单调栈】每日温度、接雨水

废话不多说&#xff0c;喊一句号子鼓励自己&#xff1a;程序员永不失业&#xff0c;程序员走向架构&#xff01;本篇Blog的主题是【单调栈的应用】&#xff0c;使用【栈】这个基本的数据结构来实现&#xff0c;这个高频题的站点是&#xff1a;CodeTop&#xff0c;筛选条件为&am…...

基于Keil a51汇编 —— 控制语句

ALIGN ALIGN expression ALIGN 语句将位置计数器设置为下一个地址模 2^表达式。 这可用于确保下一条语句在 2^n 边界上对齐。例如&#xff0c;对齐缓存行中的代码或数据。如有必要&#xff0c;汇编程序会创建一个间隙。间隔字节的内容因各个部分而异&#xff1a; 在data中未定…...

单目标优化算法:火鹰优化算法(Fire Hawk Optimizer,FHO)求解23个函数--提供MATLAB代码

一、火鹰优化算法FHO 火鹰优化算法&#xff08;Fire Hawk Optimizer&#xff0c;FHO&#xff09;由Mahdi Azizi等人于2022年提出&#xff0c;该算法性能高效&#xff0c;思路新颖。 单目标优化&#xff1a;火鹰优化算法&#xff08;Fire Hawk Optimizer&#xff0c;FHO&#…...

数据集笔记:分析OpenCellID 不同radio/ create_time update_time可视化

1 读取数据 &#xff08;以新加坡的cellID为例&#xff09; import geopandas as gpd import pandas as pdopencellidpd.read_csv(OpenCellID_SG.csv,headerNone,names[radio,mcc,net,area,cell,unit,lon,lat,range,samples,changeable1,created1,updated,AveSignal]) opence…...

【特纳斯电子】血氧饱和度监测仪设计-实物设计

视频及资料链接&#xff1a;血氧饱和度监测仪设计-实物设计 - 电子校园网 编号&#xff1a; T5662203M-SW 设计简介&#xff1a; 本设计是基于STM32的血氧饱和度监测仪系统&#xff0c;主要实现以下功能&#xff1a; 1. STM32单片机作为微处理器 2. MAX30102进行心率血氧检…...

雪花算法生成ID传到前端之后精度丢失问题

第一种&#xff1a;使用注解解决 使用方便简单&#xff0c;粒度高&#xff0c;适用于部分字段需要单独转换的场景&#xff0c;灵活度高 // 两种注解&#xff0c;选其一即可 // JsonFormat(shape JsonFormat.Shape.STRING) JsonSerialize(using ToStringSerializer.class) pri…...

Windows 10 - 适用于各种服务(Redis、MySQL)的文件迁移到其他目录后,导致的各种服务找不到的问题 - 注册服务 - 关闭服务 - 重启服务

目录 一、MySQL 服务找不到问题二、Redis 服务找不到问题Tips 三、PostgreSQL 服务找不到问题参考链接 必须要用管理员打开 doc 窗口&#xff0c;然后才进行以下操作。 通用命令 先关闭 xxx 服务 sc query xxx服务名&#xff0c;如 redis 服务 sc query redis sc query 删除…...

Java 串行接口调用优化

准备面试总结下 1.CompletableFuture static ThreadPoolExecutor poolExecutor new ThreadPoolExecutor(10, 20, 1000L, TimeUnit.MICROSECONDS, new ArrayBlockingQueue<>(100));public static void main(String[] args) throws ExecutionException, InterruptedExcep…...

【Java 进阶篇】JavaScript `typeof` 操作符详解

JavaScript是一种弱类型语言&#xff0c;这意味着变量的数据类型通常是灵活的。为了更好地理解和操作数据&#xff0c;JavaScript提供了typeof操作符&#xff0c;它可以用来确定一个值的数据类型。在本篇博客中&#xff0c;我们将详细讨论typeof操作符&#xff0c;包括它的用法…...

electron之进程间通信

Electron进程间通信 使用electron编写程序时经常遇到下面这种场景&#xff1a; 当用户点击一个按钮时&#xff0c;需要将页面输入的信息保存到本地电脑上&#xff1b; 或者是点击菜单时&#xff0c;需要页面窗口做出响应。 用户点击的按钮和窗口展示的内容是运行在渲染进程中&…...

Linux网络编程:UDP协议和TCP协议

目录 一. 对于端口号的理解 1.1 网络通信五元组 1.2 端口号的划分策略 二. 网络通信中常用的指令 2.1 netstat指令 2.2 pidof指令 三. udp协议 3.1 udp的概念及特点 3.2 udp协议端格式 3.3 对于面向数据报及应用层发送与读取数据的理解 四. tcp协议的概念及特点 五.…...

【SCS-CN】SCS-CN模型中CN值的确定

目录 一、说明二、SWAT三、HEC-HMS四、CN值转换公式五、确定CN25.1 ArcSWAT 2009用户指南5.2 SWAT plus Document5.3 National Engineering Handbook5.4 HEC-HMS水文建模系统原理方法应用5.5 Technical Release 55 (TR-55) 六、确定水文土壤单元&#xff08;HSG&#xff09;6.1…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

测试微信模版消息推送

进入“开发接口管理”--“公众平台测试账号”&#xff0c;无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息&#xff1a; 关注测试号&#xff1a;扫二维码关注测试号。 发送模版消息&#xff1a; import requests da…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄

文&#xff5c;魏琳华 编&#xff5c;王一粟 一场大会&#xff0c;聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中&#xff0c;汇集了学界、创业公司和大厂等三方的热门选手&#xff0c;关于多模态的集中讨论达到了前所未有的热度。其中&#xff0c;…...

label-studio的使用教程(导入本地路径)

文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

零基础设计模式——行为型模式 - 责任链模式

第四部分&#xff1a;行为型模式 - 责任链模式 (Chain of Responsibility Pattern) 欢迎来到行为型模式的学习&#xff01;行为型模式关注对象之间的职责分配、算法封装和对象间的交互。我们将学习的第一个行为型模式是责任链模式。 核心思想&#xff1a;使多个对象都有机会处…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...