LeetCode Medium|【300. 最长递增子序列】
力扣题目链接
本题有一个简单的解法是动态规划,时间复杂度O(n^2),笔者在之前曾做过相关记录:300.最长递增子序列
现在我们来讨论 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))的解法
局部最优:如果我们希望上升子序列尽可能的长,则我们需要让序列上升得尽可能慢;
全局最优:最终遍历完整个数组,那么此时的序列长度为最长递增子序列。
所以有一个很直观的思路就出来了:
- 我们维护一个递增数组
d[i],其中i表示最长上升子序列的末尾元素的最小值; - 我们开始遍历整个数组,在遍历到 nums[i] 时:
- 如果
nums[i] > d[len],直接加入到 d 数组末尾,并且更新 len = len + 1; - 否则,在 d 数组中二分查找,找到一个比
nums[i]小的数d[k],并更新d[k +1] = nums[i]
- 如果
这里举一个例子:
对于序列[0, 8, 4, 12, 2],
-
第一步插入 0,d=[0];
-
第二步插入 8,d=[0,8];
-
第三步插入 4,d=[0,4];
-
第四步插入 12,d=[0,4,12];
-
第五步插入 2,d=[0,2,12]。
如果你能了解二分查找找到插入位置的话,此题非常简单
class Solution {
public:int lengthOfLIS(vector<int>& nums) {int n = nums.size();if (n == 0) {return 0; // 如果数组为空,返回 0}vector<int> d(n + 1, 0); // 用于存储最长递增子序列的数组int len = 1; // 当前 LIS 的长度d[len] = nums[0]; // 初始化第一个元素for (int i = 1; i < n; ++i) {if (nums[i] > d[len]) {// 如果 nums[i] 大于当前 LIS 的最后一个元素d[++len] = nums[i];} else {// 否则,在 d 数组中找到第一个大于或等于 nums[i] 的位置,并替换它int l = 1, r = len, pos = 0;while (l <= r) {int mid = (l + r) / 2;if (d[mid] < nums[i]) {pos = mid; // 找到小于 nums[i] 的最大位置l = mid + 1;} else {r = mid - 1;}}d[pos + 1] = nums[i]; // 替换位置 pos+1 处的值}}return len; // 返回最长递增子序列的长度}
};
相关文章:
LeetCode Medium|【300. 最长递增子序列】
力扣题目链接 本题有一个简单的解法是动态规划,时间复杂度 O(n^2),笔者在之前曾做过相关记录:300.最长递增子序列 现在我们来讨论 O ( n l o g ( n ) ) O(nlog(n)) O(nlog(n))的解法 局部最优:如果我们希望上升子序列尽可能的长&a…...
jenkins自动化构建docker镜像并上传至harbor仓库
1、插件下载 首先进入jenkins之后需要现在“Maven”、“GitLab”、“Jdk”、“SSH”、“Git”的相关插件,这里不再赘述,需要什么插件直接安装即可 搜索对应插件后选择直接安装即可 2、系统全局配置 2.1 Maven配置 配置maven安装的相应的setting文件 …...
Java高级Day23-HashMap
74.HashMap Map接口常用实现类:HashMap、Hashtable和Properties HashMap是Map接口使用频率最高的实现类 HashMap是以key-value对的方式来存储数据 key不能重复,但是值可以重复,允许使用null健和null值 如果添加相同的key,会覆…...
【学术会议征稿】第四届电气工程与计算机技术国际学术会议(ICEECT2024)
第四届电气工程与计算机技术国际学术会议(ICEECT2024) 2024 4th International Conference on Electrical Engineering and Computer Technology 第四届电气工程与计算机技术国际学术会议(ICEECT2024)将于9月27日-29日在哈尔滨举…...
Spring boot tomcat使用自定义线程池监控线程数量告警
Spring boot tocmat 使用自定义线程池 线程池 接近最大线程数量 警戒值告警 修改tomcat线程池中线程名字 配置文件上代码 server:port: 9898servlet:context-path: /testtomcat:connection-timeout: 5000max-connections: 5accept-count: 5 tomcat_thread_max_number_warn:…...
K8S子节点加入主节点访问MaterAPI报错:Unauthorized 401
问题场景: 本地测试由于之前安装过K8S今天重启无法使用了,于是重新安装了一下,子节点加入主节点报错: I0808 23:13:04.299356 19180 round_trippers.go:466] curl -v -XGET -H "Accept: application/json, */*" -H …...
C++ Poco服务端框架中JSON的使用
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言一、JSON是什么?二、使用步骤总结 前言 上面一篇文章教你学会了Poco开发服务端应用,这个教程教会你使用JSON。一般传JSON的时候都是POS…...
leetcode787. K 站中转内最便宜的航班——优先队列优化的Dijkstra算法+剪枝
题目 leetcode787. K 站中转内最便宜的航班 题目分析 给定一个城市图,每个城市通过航班与其他城市相连。每个航班都有一个起点、终点和价格。你需要找到从起点城市 src 到终点城市 dst 的最便宜路径,但这条路径最多只能经过 k 个中转站。你需要返回这…...
赛盈分销亮相AI科技大会暨亚马逊新增长大会,与企业共话跨境品牌发展新机遇!
八月开端,由知无不言与xmars和钱老师课堂联合主办的2024年AI科技大会暨亚马逊新增长大会在深圳宝安顺利开展,为期2天的跨境峰会吸引了上千位优秀的卖家朋友前来感受一场盛夏大狂欢。在本次跨境峰会里,邀请了多位不同领域的先锋人物࿰…...
Nacos-配置中心
1.为什么要使用配置中心? 2.常用的配置中心组件? 3.如何使用? 在配置中心创建配置文件 启动一个单列的nacos服务 点击发布 在微服务中使用 添加依赖 <!--nacso配置中心的依赖--><dependency><groupId>com.alibaba.cloud&l…...
ava中的文件操作、IO流、递归和字符集
目录 File类的使用 创建File对象 创建和删除文件 遍历文件夹 IO流 字节流 读取文件 字符流 读取文本文件 写入文本文件 递归 计算阶乘 文件搜索 字符集 编码与解码 File类的使用 在Java中,File类用于表示文件和目录的路径。它提供了一些方法来创建、删…...
生成式人工智能安全评估体系构建
文章目录 前言一、人工智能安全治理的现状1.1 国际安全治理现状1.2 国内安全治理现状二、构建人工智能安全评估体系1.1 需要对生成式人工智能技术的安全性、可靠性、可控性、公平性等维度进行全面的考量。1.2 应对生成式人工智能全维度风险。1.3 在体系化应对框架中,应明确法律…...
NRBO-XGBoost分类 基于牛顿-拉夫逊优化算法[24年最新算法]-XGBoost多特征分类预测+交叉验证
NRBO-XGBoost分类 基于牛顿-拉夫逊优化算法[24年最新算法]-XGBoost多特征分类预测交叉验证 多输入单输出) matlab代码 程序已调试好,无需更改代码替换数据直接使用!!!数据格式为excel格式!需要定制可私&a…...
synchronized实现原理及优化
一、概述 线程安全在并发编程中是重要关注点,造成线程安全问题的主要诱因有两个:一是存在共享数据(也称临界资源),二是存在多个线程共同操作共享数据。synchronized关键字能够保证在同一时刻只有一个线程可以执行某个…...
NLP 之词的表示与语言模型
表示的基本原理: 机器无法理解文字,却能进行复杂的数学运算——神经网络只要够深、够复杂,就能拟合足够复杂的数学模式。把文字嵌入(embed)到一个向量空间中去。 词表示(Word Representation)…...
每天一个数据分析题(四百七十一)- 假设检验
下列对假设检验的描述合理的是? A. 备择假设是研究者想收集证据予以支持的假设 B. 原假设是研究者想收集证据予以推翻的假设 C. 原假设是研究者想收集证据予以支持的假设 D. 备择假设是研究者想收集证据予以推翻的假设 数据分析认证考试介绍:点击进入 题目来…...
《系统架构设计师教程(第2版)》第13章-层次式架构设计理论与实践-04-数据访问层设计
文章目录 1. 五种数据访问模式1.1 在线访问1.2 DAO1.3 DTO1.4 离线数据模式1.5 对象/关系映射 (O/R Mapping) 2. 工厂方法模式在数据访问层应用3 ORM、Hibernate与CMP2.0设计思想3.1 ORM3.2 Hibernate1)概述2) Hibernate的架构(2023年的考题&…...
【视觉SLAM】 十四讲ch7习题
简介 本文主要内容是《视觉SLAM十四讲》(第二版)第7章的习题解答,并介绍了在解答习题中的一下思考和总结的经验。本文代码部分参考了:HW-of-SLAMBOOK2 1、除了本书介绍的ORB特征点,你还能找到哪些特征点?…...
K-近邻算法(二)
三、 kd 树 问题导⼊: 实现k 近邻算法时, 主要考虑的问题是如何对训练数据进⾏快速 k 近邻搜索。这在特征空间的维数⼤及训练数据容量⼤时尤其必要。 k 近邻法最简单的实现是线性扫描(穷举搜索),即要计算输⼊实例与…...
WPF学习(2)-UniformGrid控件(均分布局)+StackPanel控件(栈式布局)
UniformGrid控件(均分布局) UniformGrid和Grid有些相似,只不过UniformGrid的每个单元格面积都是相等的,不管是横向的单元格,或是纵向的单元格,它们会平分整个UniformGrid。 UniformGrid控件提供了3个属性…...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:
在 HarmonyOS 应用开发中,手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力,既支持点击、长按、拖拽等基础单一手势的精细控制,也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档,…...
【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)
服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)
UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中,UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化…...
OPENCV形态学基础之二腐蚀
一.腐蚀的原理 (图1) 数学表达式:dst(x,y) erode(src(x,y)) min(x,y)src(xx,yy) 腐蚀也是图像形态学的基本功能之一,腐蚀跟膨胀属于反向操作,膨胀是把图像图像变大,而腐蚀就是把图像变小。腐蚀后的图像变小变暗淡。 腐蚀…...
腾讯云V3签名
想要接入腾讯云的Api,必然先按其文档计算出所要求的签名。 之前也调用过腾讯云的接口,但总是卡在签名这一步,最后放弃选择SDK,这次终于自己代码实现。 可能腾讯云翻新了接口文档,现在阅读起来,清晰了很多&…...
HybridVLA——让单一LLM同时具备扩散和自回归动作预测能力:训练时既扩散也回归,但推理时则扩散
前言 如上一篇文章《dexcap升级版之DexWild》中的前言部分所说,在叠衣服的过程中,我会带着团队对比各种模型、方法、策略,毕竟针对各个场景始终寻找更优的解决方案,是我个人和我司「七月在线」的职责之一 且个人认为,…...
stm32wle5 lpuart DMA数据不接收
配置波特率9600时,需要使用外部低速晶振...
Python网页自动化Selenium中文文档
1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API,让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API,你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...
