想要精通算法和SQL的成长之路 - 最长连续序列
想要精通算法和SQL的成长之路 - 最长连续序列
- 前言
- 一. 最长连续序列
- 1.1 并查集数据结构创建
- 1.2 find 查找
- 1.3 union 合并操作
- 1.4 最终代码
前言
想要精通算法和SQL的成长之路 - 系列导航
并查集的运用
一. 最长连续序列
原题链接

这个题目,如何使用并查集是一个小难点,我们可以这么想:
- 对于数组中的每一个元素,在初始化的时候,根节点是它本身。以它为根节点的最长连续序列是1。
- 在经历过一系列的合并操作之后,以示例1来说,元素4的根节点就是元素1。
- 那么我们合并操作,合并的对象是谁?注意题目要求的是连续序列。那么针对每个元素num,我进行
union(num,num+1)即可。 - 由于题目要求的是最长的连续序列,因此我们可以在并查集中维护一个
max最大值。在合并操作的时候更新它。 - 由于数组内元素的跳跃性,我们可以用一个
HashMap替代并查集的int[]数组。
1.1 并查集数据结构创建
class UnionFind {private Map<Integer, Integer> parent;private Map<Integer, Integer> rank;private int max;public UnionFind(int[] nums) {max = 1;HashMap<Integer, Integer> tmpParent = new HashMap<>();HashMap<Integer, Integer> tmpRank = new HashMap<>();// 初始化操作:每个元素的根节点是它本身。并且以该元素作为根节点时的最长连续序列长度是1for (int num : nums) {tmpParent.put(num, num);tmpRank.put(num, 1);}parent = tmpParent;rank = tmpRank;}
}
1.2 find 查找
因为我们在合并过程中,进行union(num,num+1)操作,以nums = [100,4,200,1,3,2]为例,那么100+1 = 101,101这个元素是否在集合当中呢?
我们看下常规的函数:
public int find(int x) {while (x != parent[x]) {x = parent[x];}return x;
}
而我们在本题当中,使用HashMap作为替换存储,同时我们还需要考虑到对象不存在的情况,代码如下
public int find(int x) {// 因为我们是以每个元素 + 1 来合并的,因此+1后的元素不一定存在于集合当中。// 这里就要特判,否则就会导致NPE,null和int进行 == 比较,会NPEif (!parent.containsKey(x)) {return x;}if (parent.get(x) == x) {return x;}parent.put(x, find(parent.get(x)));return parent.get(x);
}
1.3 union 合并操作
public void union(int x, int y) {// 如果不存在,也要直接返回if (!parent.containsKey(y)) {return;}int rootX = find(x);int rootY = find(y);// 是同一个根节点,直接返回if (rootX == rootY) {return;}// 区间合并,算出合并后的连续序列长度int tmpSum = rank.get(rootY) + rank.get(rootX);if (rank.get(rootX) > rank.get(rootY)) {rank.put(rootX, tmpSum);// 更新rootY的根节点为rootXparent.put(rootY, rootX);} else {rank.put(rootY, tmpSum);parent.put(rootX, rootY);}// 合并的同时还要维护max值(最长连续序列长)max = Math.max(max, tmpSum);
}
1.4 最终代码
public int longestConsecutive(int[] nums) {if (nums.length == 0) {return 0;}UnionFind unionFind = new UnionFind(nums);for (int num : nums) {// 将当前元素和 +1后的值进行合并unionFind.union(num, num + 1);}return unionFind.max;
}class UnionFind {private Map<Integer, Integer> parent;private Map<Integer, Integer> rank;private int max;public UnionFind(int[] nums) {max = 1;HashMap<Integer, Integer> tmpParent = new HashMap<>();HashMap<Integer, Integer> tmpRank = new HashMap<>();// 初始化操作:每个元素的根节点是它本身。并且以该元素作为根节点时的最长连续序列长度是1for (int num : nums) {tmpParent.put(num, num);tmpRank.put(num, 1);}parent = tmpParent;rank = tmpRank;}public int find(int x) {// 因为我们是以每个元素 + 1 来合并的,因此+1后的元素不一定存在于集合当中。// 这里就要特判if (!parent.containsKey(x)) {return x;}if (parent.get(x) == x) {return x;}parent.put(x, find(parent.get(x)));return parent.get(x);}public void union(int x, int y) {if (!parent.containsKey(y)) {return;}int rootX = find(x);int rootY = find(y);// 是同一个根节点if (rootX == rootY) {return;}int tmpSum = rank.get(rootY) + rank.get(rootX);if (rank.get(rootX) > rank.get(rootY)) {rank.put(rootX, tmpSum);parent.put(rootY, rootX);} else {rank.put(rootY, tmpSum);parent.put(rootX, rootY);}max = Math.max(max, tmpSum);}
}
相关文章:
想要精通算法和SQL的成长之路 - 最长连续序列
想要精通算法和SQL的成长之路 - 最长连续序列 前言一. 最长连续序列1.1 并查集数据结构创建1.2 find 查找1.3 union 合并操作1.4 最终代码 前言 想要精通算法和SQL的成长之路 - 系列导航 并查集的运用 一. 最长连续序列 原题链接 这个题目,如何使用并查集是一个小难…...
UG NX二次开发(C#)- 制图(Draft)-工程图框选制图曲线并输出制图曲线的信息
提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、在UG NX中打开一个装配体模型3、进入工程制图模块,创建工程制图4、在VS中创建一个工程项目5、在Main()中添加选择的代码(UFun)6、在Main()中添加选择的代码(NXOpen)7、框选解决方案…...
1.7.C++项目:仿muduo库实现并发服务器之Poller模块的设计
项目完整在: 文章目录 一、Poller模块:描述符IO事件监控模块二、提供的功能三、实现思想(一)功能(二)意义(三)功能设计 四、封装思想五、代码(一)框架&#…...
Flutter笔记:build方法、构建上下文BuildContext解析
Flutter笔记 build 方法解析 作者:李俊才 (jcLee95):https://blog.csdn.net/qq_28550263 邮箱 :291148484163.com 本文地址:https://blog.csdn.net/qq_28550263/article/details/133556333 本文主要介绍Flu…...
composer 安装和基本使用
php的包管理软件 如果没有安装php,参考这篇:添加链接描述 1.composer安装 composer官网 需要先安装好php,同时php -v输出有信息 cd /usr/localphp -r "copy(https://install.phpcomposer.com/installer, composer-setup.php);"…...
Ubuntu配置深度学习环境(TensorFlow和PyTorch)
文章目录 一、CUDA安装1.1 安装显卡驱动1.2 CUDA安装1.3 安装cuDNN 二、Anaconda安装三、安装TensorFlow和pyTorch3.1 安装pyTorch3.2 安装TensorFlow2 四、安装pyCharm4.1 pyCharm的安装4.2 关联anaconda的Python解释器 五、VScode配置anaconda的Python虚拟环境 前言ÿ…...
【产品经理】国内企业服务SAAS平台的生存与发展
SaaS在国外发展的比较成熟,甚至已经成为了主流,但在国内这几年才掀起热潮;企业服务SaaS平台在少部分行业发展较快,大部分行业在国内还处于起步、探索阶段;SaaS将如何再国内生存和发展? 在企业服务行业做了五…...
【vue 首屏加载优化】
Vue 首屏加载优化指的是通过一系列的技术手段,尽可能地缩短首屏(即页面中可见的部分)的加载时间,提高用户体验。 以下是一些常见的 Vue 首屏加载优化技巧: 使用 Vue SSR(服务端渲染)࿱…...
docker--redis容器部署及与SpringBoot整合-I
文章目录 1. 容器化部署docker2. 如何与SpringBoot集成2.1. 引入依赖2.2. 添加配置信息2.3. 测试类2.4. 内置的Spring Beansredis 主流客户端比较redissonlettucejedis参考1. 容器化部署docker 拉取镜像创建数据目录data 及 配置目录conf创建配置文件redis.conf启动redis容器进…...
力扣 -- 518. 零钱兑换 II(完全背包问题)
解题步骤: 参考代码: 未优化代码: class Solution { public:int change(int amount, vector<int>& coins) {int ncoins.size();//多开一行,多开一列vector<vector<int>> dp(n1,vector<int>(amount1…...
一文搞懂UART通信协议
目录 1、UART简介 2、UART特性 3、UART协议帧 3.1、起始位 3.2、数据位 3.3、奇偶校验位 3.4、停止位 4、UART通信步骤 1、UART简介 UART(Universal Asynchronous Receiver/Transmitter,通用异步收发器)是一种双向、串行、异步的通信…...
【算法|动态规划No.7】leetcode300. 最长递增子序列
个人主页:兜里有颗棉花糖 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 🍔本专栏旨在提高自己算法能力的同时,记录一下自己的学习过程,希望…...
LeetCode 54 螺旋矩阵
先贴代码 class Solution {public int[][] generateMatrix(int n) {int left 0;int right n-1;int up 0;int down n-1;int[][] result new int[n][n];int number 0;while(left < right && up < down) {for(int ileft;i<right;i) {number;result[up]…...
OpenCV 概念、整体架构、各模块主要功能
文章目录 1. OpenCV 概念2 OpenCV主要模块3 各模块 详细介绍3.1 calib3d 标定3.2 core 核心功能模块3.4 features2d 二维特征3.5 flann 快速近似近邻算法库3.7 highgui 高级图形用户界面3.9 imgproc 图像处理模块3.10 ml 机器学习模块3.11 objdetect 目标检测模块3.12 photo 数…...
组合数与莫队——组合数前缀和
用莫队求组合数是一种常见套路 莫队求 S ( n , m ) ∑ i 0 m ( n i ) S(n,m)\sum_{i0}^m\binom n i S(n,m)∑i0m(in) S ( n , m 1 ) S(n,m1) S(n,m1) 直接做个差,然后就相当于加上 ( n i 1 ) \binom n {i1} (i1n) 求 S ( n 1 , m ) S(n1,m) S(n1,m)…...
stm32之雨滴传感器使用记录
一、简介 雨滴传感器、烟雾传感器(MQ2)、轨迹传感器、干黄管等的原理都类似,都是将检测到的信号通过LM393进行处理之后再输出,可以输出数字信号DO(0和1)和模拟信号A0。 雨滴传感器在正常情况下是AO输出的是…...
华硕平板k013me176cx线刷方法
1.下载adb刷机工具, 或者刷机精灵 2.下载刷机rom包 华硕asus k013 me176cx rom固件刷机包-CSDN博客 3.平板进入刷机界面 进入方法参考: ASUS (k013) ME176CX不进入系统恢复出厂设置的方法-CSDN博客 4.解压ME176C-CN-3_2_23_182.zip,把UL-K013-CN-3.2.…...
C#停车场管理系统
目录 一、绪论1.1内容简介及意义1.2开发工具及技术介绍 二、总体设计2.1系统总体架构2.2登录模块总体设计2.3主界面模块总体设计2.4停车证管理模块总体设计2.5停车位管理模块总体设计2.6员工管理模块总体设计2.7其他模块总体设计 三、详细设计3.1登录模块设计3.2主界面模块设计…...
C++:stl:stack、queue、priority_queue介绍及模拟实现和容量适配器deque介绍
本文主要介绍c中stl的栈、队列和优先级队列并对其模拟实现,对deque进行一定介绍并在栈和队列的模拟实现中使用。 目录 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的…...
【Java】面向对象程序设计 课程笔记 面向对象基础
🚀Write In Front🚀 📝个人主页:令夏二十三 🎁欢迎各位→点赞👍 收藏⭐️ 留言📝 📣系列专栏:Java 💬总结:希望你看完之后,能对你有…...
eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15
缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下: struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Keil 中设置 STM32 Flash 和 RAM 地址详解
文章目录 Keil 中设置 STM32 Flash 和 RAM 地址详解一、Flash 和 RAM 配置界面(Target 选项卡)1. IROM1(用于配置 Flash)2. IRAM1(用于配置 RAM)二、链接器设置界面(Linker 选项卡)1. 勾选“Use Memory Layout from Target Dialog”2. 查看链接器参数(如果没有勾选上面…...
【单片机期末】单片机系统设计
主要内容:系统状态机,系统时基,系统需求分析,系统构建,系统状态流图 一、题目要求 二、绘制系统状态流图 题目:根据上述描述绘制系统状态流图,注明状态转移条件及方向。 三、利用定时器产生时…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
论文笔记——相干体技术在裂缝预测中的应用研究
目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术:基于互相关的相干体技术(Correlation)第二代相干体技术:基于相似的相干体技术(Semblance)基于多道相似的相干体…...
