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…...
地震勘探——干扰波识别、井中地震时距曲线特点
目录 干扰波识别反射波地震勘探的干扰波 井中地震时距曲线特点 干扰波识别 有效波:可以用来解决所提出的地质任务的波;干扰波:所有妨碍辨认、追踪有效波的其他波。 地震勘探中,有效波和干扰波是相对的。例如,在反射波…...
FastAPI 教程:从入门到实践
FastAPI 是一个现代、快速(高性能)的 Web 框架,用于构建 API,支持 Python 3.6。它基于标准 Python 类型提示,易于学习且功能强大。以下是一个完整的 FastAPI 入门教程,涵盖从环境搭建到创建并运行一个简单的…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务
通过akshare库,获取股票数据,并生成TabPFN这个模型 可以识别、处理的格式,写一个完整的预处理示例,并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务,进行预测并输…...
1.3 VSCode安装与环境配置
进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件,然后打开终端,进入下载文件夹,键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...
