LeetCode300. 最长递增子序列(2024冬季每日一题 30)
给你一个整数数组 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 < = n u m s . l e n g t h < = 2500 1 <= nums.length <= 2500 1<=nums.length<=2500
− 1 0 4 < = n u m s [ i ] < = 1 0 4 -10^4 <= nums[i] <= 10^4 −104<=nums[i]<=104
进阶:
你能将算法的时间复杂度降低到 O( n l o g ( n ) n log(n) nlog(n)) 吗?
思路:动态规划
- 维护一个递增序列,遍历完所有元素后,递增序列的长度就是最长递增子序列的长度
- 遍历每个元素,找到维护的递增序列里面,比当前元素小的最右边一个元素,找到后,将当前元素插入到找到的元素的后面一个位置,确保序列是递增的,并且覆盖掉的元素大于等于当前元素/新增的位置
- 每次更新递增序列的最大长度
- 重复上面过程,返回递增序列的长度,即最长递增子序列的长度
class Solution {
public:int a[2510];int lengthOfLIS(vector<int>& nums) {a[0] = -2e9;int n = nums.size(), len = 0;for(int i = 0; i < n; i++){int l = 0, r = len;while(l < r){int mid = l + r + 1 >> 1;if(a[mid] >= nums[i]){r = mid - 1;}else{l = mid;}}a[l + 1] = nums[i];len = max(l + 1, len);}return len;}
};
相关文章:
LeetCode300. 最长递增子序列(2024冬季每日一题 30)
给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的 子序列。 示例 1&…...
vue H5如何实现copy功能
vue H5如何实现copy功能 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><link rel"stylesheet" href"https://unpkg.com/vant2.12/lib/index.css" /><title></title><st…...
Golang使用etcd构建分布式锁案例
在本教程中,我们将学习如何使用Go和etcd构建分布式锁系统。分布式锁系统对于管理对分布式系统中共享资源的并发访问至关重要。它有助于维护一致性,防止竞争条件,并确保在任何给定时间只有一个进程独占访问资源。 我们将使用Go作为编程语言&am…...
Windows 和 Ubuntu 双系统安装
复现论文的时候,个别包只有Linux版本,并且源码编译比较麻烦,所以干脆直接安装一个双系统(WinUbuntu),方便复现论文。 参考视频链接:Windows 和 Ubuntu 双系统的安装和卸载 0.所需工具 4G以上U…...
多媒体文件解复用(Demuxing)过程
多媒体文件的解复用(Demuxing)过程指的是从一个多媒体容器文件(如 MP4、MKV、AVI 等)中提取不同类型的多媒体数据流(例如视频流、音频流、字幕流等)的过程。 容器文件本身并不包含实际的视频或音频数据&…...
从 Zuul 迁移到 Spring Cloud Gateway:一步步实现服务网关的升级
从 Zuul 迁移到 Spring Cloud Gateway:一步步实现服务网关的升级 迁移前的准备工作迁移步骤详解第一步:查看源码第二步:启动类迁移第三步:引入 Gateway 依赖第四步 编写bootstrap.yaml第五步:替换路由配置第六步&#…...
qt之插件编译
QtXlsxWriter sudo apt install qtbase5-private-dev git clone https://github.com/dbzhang800/QtXlsxWriter.git cd QtXlsxWriter/ qmake make -j6 sudo make install #将生成的lib 及 include copy至项目路径的lib 及include里项目配置: QT xlsxbluetoo…...
pandas一行拆成多行
import pandas as pd df pd.DataFrame({Country:[China,US,Japan,EU,UK/Australia, UK/Netherland],Number:[100, 150, 120, 90, 30, 2],Value: [1, 2, 3, 4, 5, 6],label: list(abcdef)})# 法一 推荐 df2df.drop(Country, axis1).join(df[Country].str.split(/, expandTrue).…...
今天调了个转速的小BUG
同事说转速表有个bug,转速停止后,继电器没有恢复到初始状态。若停止之前是报警,继电器吸合,则停止后继电器还是吸合。我心想不会啊,这软件都弄了好几年了,一直也没出现过状况。 经过与调试同事的沟通&#…...
第三节、电机定速转动【51单片机-TB6600驱动器-步进电机教程】
摘要:本节介绍用定时器定时的方式,精准控制脉冲时间,从而控制步进电机速度 一、计算过程 1.1 电机每一步的角速度等于走这一步所花费的时间,走一步角度等于步距角,走一步的时间等于一个脉冲的时间 w s t e p t … ……...
从一个Bug谈前端响应拦截器的应用
一、问题场景 今天在开发商品管理系统时,遇到了一个有趣的问题:当添加重复的商品编号时,页面同时弹出了两条 "商品编号已存在" 错误提示: 这个问题暴露了前端错误处理机制的混乱,让我们从这个问题出发&…...
JS进阶DAY4|节点操作
嘿👋 今天我们要一起深入探索JavaScript中的DOM操作,这是前端开发中不可或缺的技能。🌟 准备好了吗?让我们一起跳进DOM的海洋,看看怎么用代码操控网页的结构吧! 目录 1. 增加节点 1.1 使用 appendChild 方…...
【Web】2023安洵杯第六届网络安全挑战赛 WP
目录 Whats my name easy_unserialize signal Swagger docs 赛题链接:GitHub - D0g3-Lab/i-SOON_CTF_2023: 2023 第六届安洵杯 题目环境/源码 Whats my name 第一段正则用于匹配以 include 结尾的字符串,并且在 include 之前,可以有任…...
go 语言中协程和GMP模型
为什么需要协程? 协程用来更加精细地利用线程,支撑超高的并发的。协程,从 runtime 的角度看,协程就是一个被调度的 g 结构体。 G 就是协程,M 是线程,P 是为了优化多线程并发时,会抢夺协程队列的…...
coco数据集转换SAM2格式
coco是一个大json汇总了所有train的标签 SAM2训练一张图对应一个json标签 import json import os from pycocotools import mask as mask_utils import numpy as np import cv2def poly2mask(points, width, height):points_array np.array(points, dtypenp.int32).reshape(-…...
【CMD、PowerShell和Bash设置代理】
【CMD、PowerShell和Bash设置代理】 1. CMD(命令提示符)临时设置代理(只对当前会话有效):查看当前代理设置:清除临时代理设置:永久设置代理(对所有新的 CMD 会话有效)&am…...
22智能 代码作业集合
3-2 #include <stdio.h>int main() {int a 21;int b 10;int c ;c a b;printf("Line 1 - c 的值是 %d\n", c );c a - b;printf("Line 2 - c 的值是 %d\n", c );c a * b;printf("Line 3 - c 的值是 %d\n", c );c a / b;printf("…...
实现一个简单的后台架子(侧边栏菜单渲染,折叠,黑白主题,组件主题色,全屏,路由快捷栏)
目录 侧边栏菜单渲染 侧边栏折叠 黑白主题 全屏切换 切换组件主题色 tab快捷栏 代码 侧边栏菜单渲染 结合ElementPlus组件库进行实现 新建的Vue3项目,引入了格式化样式normalize.css和ElementPlus,并进行了全局引入 并进行了全局引入 设置高度为100% 粘贴ElementPlus的…...
vue3-canvas实现在图片上框选标记(放大,缩小,移动,删除)
双图版本(模板对比) 业务描述:模板与图片对比,只操作模板框选的位置进行色差对比,传框选坐标位置给后端,返回对比结果显示 draw.js文件: 新增了 createUuid,和求取两个数组差集的方…...
unity3d—demo(2d人物左右移动发射子弹)
目录 人物代码示例: 子弹代码示例: 总结上面代码: 注意点: 人物代码示例: using System.Collections; using System.Collections.Generic; using UnityEngine;public class PlayerTiao : MonoBehaviour {public f…...
XML Group端口详解
在XML数据映射过程中,经常需要对数据进行分组聚合操作。例如,当处理包含多个物料明细的XML文件时,可能需要将相同物料号的明细归为一组,或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码,增加了开…...
基于FPGA的PID算法学习———实现PID比例控制算法
基于FPGA的PID算法学习 前言一、PID算法分析二、PID仿真分析1. PID代码2.PI代码3.P代码4.顶层5.测试文件6.仿真波形 总结 前言 学习内容:参考网站: PID算法控制 PID即:Proportional(比例)、Integral(积分&…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)
宇树机器人多姿态起立控制强化学习框架论文解析 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一) 论文解读:交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...
【Oracle】分区表
个人主页:Guiat 归属专栏:Oracle 文章目录 1. 分区表基础概述1.1 分区表的概念与优势1.2 分区类型概览1.3 分区表的工作原理 2. 范围分区 (RANGE Partitioning)2.1 基础范围分区2.1.1 按日期范围分区2.1.2 按数值范围分区 2.2 间隔分区 (INTERVAL Partit…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解
JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用,结合SQLite数据库实现联系人管理功能,并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能,同时可以最小化到系统…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
