【LeetCode最详尽解答】128_最长连续序列 Longest-Consecutive-Sequence
欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家!
链接:
- 128_最长连续序列
直觉
- 输入:
nums = [100, 4, 200, 1, 3, 2] - 输出:
4 - 解释: 最长的连续元素序列是
[1, 2, 3, 4]。因此它的长度是4。
首先,我们需要找到每个递增序列的起始位置,并且舍弃重复的值。所以先使用 set(nums) 将 nums 转换为一个集合。集合中的每个值可能是起始位置,也可能只是序列的一部分。我们只需要找到起始值。
考虑列表 [1, 2, 3, 4, 5, 6]。如果不只找起始点,它会计算从 1-6,2-6,3-6 等开始的序列,导致 ( O ( n 2 ) (O(n^2) (O(n2) 的复杂度。为了确保线性时间复杂度,我们需要仅识别每个间隔的起始点。
当遇到一个值时,如果 n-1 在集合中,跳过它,因为它不是起始位置。如果 n-1 不在集合中,说明 n 是一个起始值,我们将长度初始化为 1。当 n + length 在集合中时,长度加 1。然后,将结果更新为 length 和当前结果中的最大值。
方法
我们将找到每个起始位置,并使用哈希集合存储 nums 的所有值。当我们找到一个起始位置时,我们将从这个位置计算序列的长度。然后,更新最终结果并返回它。
找到起始位置:
- 如果
n-1不在numset中,那么n是一个起始位置。 - 将长度初始化为
1。 - 当
n + length在numset中时,我们增加长度。 - 最后,用找到的最长长度更新结果。
复杂度
-
时间复杂度:
O ( n ) O(n) O(n)- 创建集合: O ( n ) O(n) O(n)
- 遍历列表: O ( n ) O(n) O(n)
- 检查序列的起始点并计算长度: O ( n ) O(n) O(n)
-
空间复杂度:
O ( n ) O(n) O(n)- 集合的空间: O ( n ) O(n) O(n)
- 其他变量的空间: O ( 1 ) O(1) O(1)
代码
class Solution(object):def longestConsecutive(self, nums):""":type nums: List[int]:rtype: int"""numset = set(nums)longest = 0for n in nums:# calculate just from the starting positionif n-1 not in numset:length = 1while n + length in numset:length+=1longest = max(longest, length)return longest
相关文章:
【LeetCode最详尽解答】128_最长连续序列 Longest-Consecutive-Sequence
欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家! 链接: 128_最长连续序列 直觉 输入: nums [100, 4, 200, 1, 3, 2]输出: 4解释: 最长的连续元素序列是…...
盒马鲜生礼品卡如何使用?
盒马鲜生的礼品卡除了在门店用以外,还有什么用处啊 毕竟家附近的盒马距离都太远了,好多卡最后都闲置下来了,而且以前都不知道盒马卡还会过期,浪费了好多 还好最近发现了 盒马鲜生礼品卡现在也能在收卡云上兑现了,而且…...
有哪些常用ORM框架
ORM(Object-Relational Mapping,对象关系映射)是一种编程技术,它允许开发者使用面向对象的编程语言来操作关系型数据库。ORM的主要目的是将数据库中的数据表映射到编程语言中的对象,从而使得开发者可以使用对象的方式来…...
nodejs 中 axios 设置 burp 抓取 http 与 https
在使用 axios 库的时候,希望用 burp 抓包查看发包内容。但关于 axios 设置代理问题,网上提到的一些方法不是好用,摸索了一段时间后总结出设置 burp 代理抓包的方法。 nodejs 中 axios 设置 burp 抓包 根据请求的站点,分为 http …...
数据通信与网络(二)
如何构建网络协议 这些协议采用分层的结构,每层协议实现特定功能,同时也需要依靠低层协议所提供的服务。 网络协议可以理解为三部分组成: 1、语法:通信时双方交换数据和控制信息的格式,是对通信时采用的数据结构形式…...
DTU为何应用如此广泛?
1.DTU是什么 DTU(数据传输单元)是一种无线终端设备,它的核心功能是将串口数据转换为IP数据或将IP数据转换为串口数据,并通过无线通信网络进行传送。DTU通常内置GPRS模块,能够实现远程数据的实时传输,广泛应用于工业自动化、远程监…...
基于软件在环的飞控机建模仿真
安全关键系统(Safety-Critical System,SCS)是指由于某些行为或组合行为能够引发整体系统失效,继而导致财物损失、人员受伤等严重影响的系统,诸多安全关键领域如航空航天、核电系统、医疗设备、交通运输等领域的系统都属…...
github ssh key的SHA256是什么
github ssh key的SHA256是什么 怎么知道github上自己的公钥指纹和本地的公钥是否一致? 计算方法如下: cat .ssh/id_rsa.pub |awk { print $2 } | # Only the actual key data without prefix or commentsbase64 -d | # decode as base64s…...
HyperBDR新版本上线,自动化容灾兼容再升级!
本次HyperBDR v5.5.0版本新增完成HCS(Huawei Cloud Stack)8.3.x和HCSO(Huawei Cloud Stack Online)自动化对接,另外还突破性完成了Oracle云(块存储模式)的自动化对接。 HyperBDR,云原生业务级别容灾工具。支…...
python学习—合并多个Excel工作簿表格文件
系列文章目录 python学习—合并TXT文本文件 python学习—统计嵌套文件夹内的文件数量并建立索引表格 python学习—查找指定目录下的指定类型文件 python学习—年会不能停,游戏抽签抽奖 python学习—循环语句-控制流 文章目录 系列文章目录功能说明1 准备工作&#…...
如何把路由器设备的LAN口地址为三大私网地址
要将路由器的LAN口地址配置为三大私有IP地址范围之一(10.0.0.0/8、172.16.0.0/12 或 192.168.0.0/16),我们需要访问路由器的管理界面并进行相应的设置。 下面是步骤: 连接到路由器: 连接到路由器的管理界面…...
Java多线程-StampedLock(原子读写锁)
StampedLock 是读写锁的实现,对比 ReentrantReadWriteLock 主要不同是该锁不允许重入,多了乐观读的功能,使用上会更加复杂一些,但是具有更好的性能表现。StampedLock 的状态由版本和读写锁持有计数组成。 获取锁方法返回一个邮戳&…...
(源码)一套医学影像PACS系统源码 医院系统源码 提供数据接收、图像处理、测量、保存、管理、远程医疗和系统参数设置等功能
PACS系统还提供了数据接收、图像处理、测量、保存、管理、远程医疗和系统参数设置等功能。 PACS系统提高了医学影像的利用率和诊疗效率,为医生提供了更加准确和及时的诊断依据。它是医院信息化的必备系统之一,已经成为医学影像管理和传输的重要工具。 P…...
【Qt 学习笔记】Qt窗口 | 对话框 | 创建自定义对话框
博客主页:Duck Bro 博客主页系列专栏:Qt 专栏关注博主,后期持续更新系列文章如果有错误感谢请大家批评指出,及时修改感谢大家点赞👍收藏⭐评论✍ Qt窗口 | 对话框 | 创建自定义对话框 文章编号:Qt 学习笔记…...
# RocketMQ 实战:模拟电商网站场景综合案例(五)
RocketMQ 实战:模拟电商网站场景综合案例(五) 一、mybatis 逆向工程使用 4、逆向工程 生成 的 .xml 配置文件。 4.1、生成的 TradeCouponMapper.xml 文件。 <?xml version"1.0" encoding"UTF-8" ?> <!DOC…...
Cesium4Unreal - # 009 直接加载显示shapefile
文章目录 直接加载显示shapefile1 思路2 步骤2.1 下载shapelib2.2 添加依赖模块2.3 创建Actor2.3.1 MyShapeLoaderActor.h2.3.2 MyShapeLoaderActor.cpp2.3 蓝图代码直接加载显示shapefile 1 思路 在Unreal Engine中加载显示shapefile无非就是从shapefile中读取几何数据,并且…...
Release和Debug的区别?Release有什么好处?【面试】
Release和Debug的区别: 优化:Debug版本通常不进行优化,以便更容易调试;Release版本则经过高度优化,以提高性能。调试信息:Debug版本包含详尽的调试信息,如符号信息和源代码映射;Rel…...
DevExpress 控件和库
UI控件和组件 DevExpress WinForms包括以下Windows窗体库和控件: Grids and Editors Data Grid Tree List Vertical Grid Property Grid Gantt Control Data Editors and Simple Controls Office-inspired Ribbon, Bars and Menu Rich Text Editor Scheduler S…...
车载以太网测试
一、车载以太网的发展 IEEE: 电气与电子工程师协会,其中IEEE802.3工作小组致力于推进以太网相关标准的制定与完善,其发展主要经过一下三个阶段: 1.诊断/程序更新 2.智驾座舱 3.主干网 二、车载以太网协议(OSI七层模型&#x…...
181.二叉树:验证二叉树(力扣)
代码解决 /*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* Tre…...
docker详细操作--未完待续
docker介绍 docker官网: Docker:加速容器应用程序开发 harbor官网:Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台,用于将应用程序及其依赖项(如库、运行时环…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
postgresql|数据库|只读用户的创建和删除(备忘)
CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...
论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)
笔记整理:刘治强,浙江大学硕士生,研究方向为知识图谱表示学习,大语言模型 论文链接:http://arxiv.org/abs/2407.16127 发表会议:ISWC 2024 1. 动机 传统的知识图谱补全(KGC)模型通过…...
OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()
操作系统:ubuntu22.04 OpenCV版本:OpenCV4.9 IDE:Visual Studio Code 编程语言:C11 算法描述 在 GPU 上对图像执行 均值漂移滤波(Mean Shift Filtering),用于图像分割或平滑处理。 该函数将输入图像中的…...
DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”
目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
初探Service服务发现机制
1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能:服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
【LeetCode】算法详解#6 ---除自身以外数组的乘积
1.题目介绍 给定一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O…...
