从零学算法128

news/2024/4/19 14:13:22/文章来源:https://blog.csdn.net/m0_53256503/article/details/136471955

128.给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9

  • 这里就直接调 api 排序了,排序后最长连续序列在数组中就一定为连续的整数了。设 dp[i] 为以 nums[i] 结尾的子数组的最长序列,dp[i] 有两种情况,当 nums[i]=nums[i-1]+1 表示它能和前一个数组成连续的序列,就为 dp[i-1]+1,否则就没法连续, dp[i]=1。初始情况也很好理解,dp[0]=1 表示长度为 1 的数组无论如何存在连续序列长度为 1。
  • 时间复杂度: O ( n ) O(n) O(n)
  • 空间复杂度: O ( n ) O(n) O(n)
  •   public int longestConsecutive(int[] nums) {int n = nums.length;if(n == 0)return 0;Arrays.sort(nums);// 由于 dp 更新时只和前一个结果有关,所以不需要数组int dp = 1;int ans = dp;List<Integer> list = new ArrayList<>();// 去重,你也可以用一个变量记录前一个数// 这样也就不需要 list 了,空间复杂度将为 O(1)for(int i=0;i<n;i++){while(i<n-1 && nums[i]==nums[i+1])i++;list.add(nums[i]);}for(int i=1;i<list.size();i++){if(list.get(i)==list.get(i-1)+1)dp++;else dp=1;ans=Math.max(ans,dp);}return ans;}
    
  • 去重优化
  •   public int longestConsecutive(int[] nums) {int n = nums.length;if(n == 0)return 0;Arrays.sort(nums);int dp = 0;int ans = 0;int pre=nums[n-1]+1;for(int i=0;i<n;i++){while(i<n-1 && nums[i]==nums[i+1])i++;if(nums[i]==pre+1)dp++;else dp=1;pre=nums[i];ans=Math.max(ans,dp);}return ans;}
    
  • 还有用 set + 递归暴力解的:限定某个起点,从 set 中找连续的序列长度很容易,这里的计算用递归表示了。
  •   Set<Integer> set = new HashSet();public int longestConsecutive(int[] nums) {int n = nums.length;int ans = 0;if(n == 0)return ans;// set 去重Arrays.stream(nums).forEach(v->{set.add(v);});for(int x:set){// 如果有 x-1 那从 x-1 开始的长度肯定更长,所以跳过 xif(set.contains(x-1))continue;// 这就等于比较每个连续序列的长度ans = Math.max(ans,dfs(x,0));}return ans;}// 计算从 x 开始的最长序列长度int dfs(int x,int res){if(set.contains(x))return dfs(x+1,res+1);else return res;}
    

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_996094.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

阿里云配置服务器详细指南

阿里云服务器配置怎么选择&#xff1f;CPU内存、公网带宽和系统盘怎么选择&#xff1f;个人开发者或中小企业选择轻量应用服务器、ECS经济型e实例&#xff0c;企业用户选择ECS通用算力型u1云服务器、ECS计算型c7、通用型g7云服务器&#xff0c;阿里云服务器网aliyunfuwuqi.com整…

Ubuntu 22.04修改静态ip

1. 备份原网络配置文件 # 配置文件名称因机器设置有异 cd /etc/netplan cp 01-network-config.yaml 01-network-config.yaml.bak# 文件内容如下 network:version: 2renderer: NetworkManager2. 修改配置文件 使用 ipconfig 命令查看网络信息&#xff0c;ip addr 命令也可 我这…

【QT】控件的用法介绍

QLabel&#xff08;很重要&#xff09; QPixmap在Qt中代表的就是一张图片 QPicture不是图片 如果图片不能完整显示&#xff0c;那就是没有布局 //添加静态图片如果构造的时候没有指定&#xff0c;可以在外面用load()指定图片路径ui->label->setPixmap(QPixmap(":…

量化人这样用Jupyter(2) - JupySQL, D-tale

当我们使用 Jupyter 时,很显然我们的主要目的是探索数据。这篇文章将介绍如何利用 JupySQL 来进行数据查询–甚至代替你正在使用的 Navicat, dbeaver 或者 pgAdmin。此外,我们还将介绍如何更敏捷地探索数据,相信这些工具,可以帮你省下 90%的 coding 时间。 原文发表在这里…

《探索虚拟与现实的边界:VR与AR谁更能引领未来?》

引言 在当今数字时代&#xff0c;虚拟现实&#xff08;VR&#xff09;和增强现实&#xff08;AR&#xff09;技术正以惊人的速度发展&#xff0c;并逐渐渗透到我们的日常生活中。它们正在重新定义人与技术、人与环境之间的关系&#xff0c;同时也为各行各业带来了全新的可能性。…

第五节 JDBC驱动程序类型

JDBC驱动程序是什么&#xff1f; JDBC驱动程序在JDBC API中实现定义的接口&#xff0c;用于与数据库服务器进行交互。 例如&#xff0c;使用JDBC驱动程序&#xff0c;可以通过发送SQL或数据库命令&#xff0c;然后使用Java接收结果来打开数据库连接并与数据库进行交互。 JDK…

MATLAB BP神经网络工具箱

1. 原理 BP神经网络结构&#xff1a; Matlab神经网络工具箱&#xff1a; BP神经网络定义&#xff1a; netnewff(PR,[S1 S2...SNl],{TF1 TF2...TFNl},BTF,BLF,PF) 其中&#xff1a; PR --输入元素的最小值和最大值的Rx2矩阵R SI -- 第 i 层的大小&#xff0c;对于Nl层&…

YOLOV8介绍

原文链接&#xff1a; 1、 详解YOLOv8网络结构/环境搭建/数据集获取/训练/推理/验证/导出 2、Yolov8的详解与实战 3、YOLOV8模型训练部署&#xff08;实战&#xff09;&#xff08;&#xff09;有具体部署和训练实现代码YOLOV8模型训练部署&#xff08;实战&#xff09;&…

FPGA——三速自适应以太网设计(1)基本模块

FPGA——以太网设计&#xff08;1&#xff09;基本模块 1. 协议解析&#xff08;1&#xff09;MAC层&#xff08;2&#xff09;IP层 和 ARP层&#xff08;3&#xff09;UDP层 和 ICMP层 2.1 MAC接收模块2.2 MAC发送模块3.1 IP接收模块3.2 IP发送模块4.1 UDP接收模块4.2 UDP发送…

以创新筑牢安全盾牌,广师大隐盾科技照亮软件知识产权保护之路

“很感谢隐盾科技团队的各位成员对我司计算机软件代码保护的鼎力相助……”广州市硬科技百强企业在给予隐盾科技团队的感谢信中写道。据了解&#xff0c;该公司在使用了隐盾科技团队研发的隐盾代码虚拟化系统后&#xff0c;企业开发盗版率从45%降至0%、保护该企业年侵权成本超过…

计算机设计大赛 深度学习的智能中文对话问答机器人

文章目录 0 简介1 项目架构2 项目的主要过程2.1 数据清洗、预处理2.2 分桶2.3 训练 3 项目的整体结构4 重要的API4.1 LSTM cells部分&#xff1a;4.2 损失函数&#xff1a;4.3 搭建seq2seq框架&#xff1a;4.4 测试部分&#xff1a;4.5 评价NLP测试效果&#xff1a;4.6 梯度截断…

Linux conntrack和iptables技术解析

Linux虚拟文件系统管理技术 1. netfilter解析1.1 netfilter的基础原理1.2 netfilter的相关hook 2. conntrack解析2.1 conntrack的基础原理2.2 conntrack的表记录解析 3. iptables解析3.1 iptables基础原理3.2 融合conntrack表的iptables规则 4. 疑问和思考4.1 conntrack和iptab…

Tensorflow2.0笔记 - 常见激活函数sigmoid,tanh和relu

本笔记主要记录常见的三个激活函数sigmoid&#xff0c;tanh和relu&#xff0c;关于激活函数详细的描述&#xff0c;可以参考这里&#xff1a; 详解激活函数&#xff08;Sigmoid/Tanh/ReLU/Leaky ReLu等&#xff09; - 知乎 import tensorflow as tf import numpy as nptf.__ve…

20240306-1-大数据的几个面试题目

面试题目 1. 相同URL 题目: 给定a、b两个文件&#xff0c;各存放50亿个url&#xff0c;每个url各占64字节&#xff0c;内存限制是4G&#xff0c;让你找出a、b文件共同的url&#xff1f; 方案1&#xff1a;估计每个文件的大小为50G64320G&#xff0c;远远大于内存限制的4G。所以…

【golang】26、retry-go 使用示例和源码解析

文章目录 一、使用方法1.1 http 示例1.1.1 retry.Do1.1.2 retry.DoWithData1.1.3 OnRetry1.1.4 根据 error 的类型&#xff0c;决定 delay 的时长1.1.5 自定义 retry function 二、API2.1 Do 执行2.1.1 Do2.1.2 DoWithData 2.2 Delay 策略2.3 错误处理2.3.1 Unwrap2.3.2 Unwrap…

口碑营销:品牌如何维护良好口碑?

企业的品牌传播最有效的方式莫过用户的口碑&#xff0c;互联网的发展为企业的品牌传播引入了驱动力&#xff0c;愈来愈多的企业花费更多的资源开展网络口碑的建设和维护&#xff0c;那么企业如何维护好网络口碑&#xff1f; 1、持续传递优质的品牌内容 内容是营销推广的支撑点&…

学习Java的第一天

一、Java简介 Java 是由 Sun Microsystems 公司于 1995 年 5 月推出的 Java 面向对象程序设计语言和 Java 平台的总称。由 James Gosling和同事们共同研发&#xff0c;并在 1995 年正式推出。 后来 Sun 公司被 Oracle &#xff08;甲骨文&#xff09;公司收购&#xff0c;Jav…

如何做代币分析:以 LDO 币为例

作者&#xff1a;lesleyfootprint.network 编译&#xff1a;mingfootprint.network 数据源&#xff1a;LDO 代币仪表板 &#xff08;仅包括以太坊数据&#xff09; 在加密货币和数字资产领域&#xff0c;代币分析起着至关重要的作用。代币分析指的是深入研究与代币相关的数据…

【EI会议征稿通知】第四届人工智能,大数据与算法国际学术会议 (CAIBDA 2024)

第四届人工智能&#xff0c;大数据与算法国际学术会议 (CAIBDA 2024) 2024 4th International Conference on Artificial Intelligence, Big Data and Algorithms 由河南省科学院、河南大学主办&#xff0c;河南省科学院智慧创制研究所、河南大学学术发展部、河南大学人工智能…

Java 数据结构之链表

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA null || headB null) return null;ListNode pA headA, pB headB;while (pA ! pB) {pA pA null ? headB : pA.next;pB pB null ? headA : pB.next;}return pA;} public ListNode rev…