当前位置: 首页 > news >正文

想要精通算法和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的成长之路 - 系列导航 并查集的运用 一. 最长连续序列 原题链接 这个题目&#xff0c;如何使用并查集是一个小难…...

UG NX二次开发(C#)- 制图(Draft)-工程图框选制图曲线并输出制图曲线的信息

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 1、前言2、在UG NX中打开一个装配体模型3、进入工程制图模块,创建工程制图4、在VS中创建一个工程项目5、在Main()中添加选择的代码(UFun)6、在Main()中添加选择的代码(NXOpen)7、框选解决方案…...

1.7.C++项目:仿muduo库实现并发服务器之Poller模块的设计

项目完整在&#xff1a; 文章目录 一、Poller模块&#xff1a;描述符IO事件监控模块二、提供的功能三、实现思想&#xff08;一&#xff09;功能&#xff08;二&#xff09;意义&#xff08;三&#xff09;功能设计 四、封装思想五、代码&#xff08;一&#xff09;框架&#…...

Flutter笔记:build方法、构建上下文BuildContext解析

Flutter笔记 build 方法解析 作者&#xff1a;李俊才 &#xff08;jcLee95&#xff09;&#xff1a;https://blog.csdn.net/qq_28550263 邮箱 &#xff1a;291148484163.com 本文地址&#xff1a;https://blog.csdn.net/qq_28550263/article/details/133556333 本文主要介绍Flu…...

composer 安装和基本使用

php的包管理软件 如果没有安装php&#xff0c;参考这篇&#xff1a;添加链接描述 1.composer安装 composer官网 需要先安装好php&#xff0c;同时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虚拟环境 前言&#xff…...

【产品经理】国内企业服务SAAS平台的生存与发展

SaaS在国外发展的比较成熟&#xff0c;甚至已经成为了主流&#xff0c;但在国内这几年才掀起热潮&#xff1b;企业服务SaaS平台在少部分行业发展较快&#xff0c;大部分行业在国内还处于起步、探索阶段&#xff1b;SaaS将如何再国内生存和发展&#xff1f; 在企业服务行业做了五…...

【vue 首屏加载优化】

Vue 首屏加载优化指的是通过一系列的技术手段&#xff0c;尽可能地缩短首屏&#xff08;即页面中可见的部分&#xff09;的加载时间&#xff0c;提高用户体验。 以下是一些常见的 Vue 首屏加载优化技巧&#xff1a; 使用 Vue SSR&#xff08;服务端渲染&#xff09;&#xff1…...

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(完全背包问题)

解题步骤&#xff1a; 参考代码&#xff1a; 未优化代码&#xff1a; class Solution { public:int change(int amount, vector<int>& coins) {int ncoins.size();//多开一行&#xff0c;多开一列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&#xff08;Universal Asynchronous Receiver/Transmitter&#xff0c;通用异步收发器&#xff09;是一种双向、串行、异步的通信…...

【算法|动态规划No.7】leetcode300. 最长递增子序列

个人主页&#xff1a;兜里有颗棉花糖 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 兜里有颗棉花糖 原创 收录于专栏【手撕算法系列专栏】【LeetCode】 &#x1f354;本专栏旨在提高自己算法能力的同时&#xff0c;记录一下自己的学习过程&#xff0c;希望…...

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) 直接做个差&#xff0c;然后就相当于加上 ( n i 1 ) \binom n {i1} (i1n​) 求 S ( n 1 , m ) S(n1,m) S(n1,m)…...

stm32之雨滴传感器使用记录

一、简介 雨滴传感器、烟雾传感器&#xff08;MQ2&#xff09;、轨迹传感器、干黄管等的原理都类似&#xff0c;都是将检测到的信号通过LM393进行处理之后再输出&#xff0c;可以输出数字信号DO&#xff08;0和1&#xff09;和模拟信号A0。 雨滴传感器在正常情况下是AO输出的是…...

华硕平板k013me176cx线刷方法

1.下载adb刷机工具, 或者刷机精灵 2.下载刷机rom包 华硕asus k013 me176cx rom固件刷机包-CSDN博客 3.平板进入刷机界面 进入方法参考&#xff1a; ASUS (k013) ME176CX不进入系统恢复出厂设置的方法-CSDN博客 4.解压ME176C-CN-3_2_23_182.zip&#xff0c;把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的栈、队列和优先级队列并对其模拟实现&#xff0c;对deque进行一定介绍并在栈和队列的模拟实现中使用。 目录 一、stack的介绍和使用 1.stack的介绍 2.stack的使用 3.stack的模拟实现 二、queue的介绍和使用 1.queue的介绍 2.queue的使用 3.queue的…...

​【Java】面向对象程序设计 课程笔记 面向对象基础

&#x1f680;Write In Front&#x1f680; &#x1f4dd;个人主页&#xff1a;令夏二十三 &#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐️ 留言&#x1f4dd; &#x1f4e3;系列专栏&#xff1a;Java &#x1f4ac;总结&#xff1a;希望你看完之后&#xff0c;能对你有…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

Admin.Net中的消息通信SignalR解释

定义集线器接口 IOnlineUserHub public interface IOnlineUserHub {/// 在线用户列表Task OnlineUserList(OnlineUserList context);/// 强制下线Task ForceOffline(object context);/// 发布站内消息Task PublicNotice(SysNotice context);/// 接收消息Task ReceiveMessage(…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

Java求职者面试指南:Spring、Spring Boot、Spring MVC与MyBatis技术解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、Spring MVC与MyBatis技术解析 一、第一轮基础概念问题 1. Spring框架的核心容器是什么&#xff1f;它的作用是什么&#xff1f; Spring框架的核心容器是IoC&#xff08;控制反转&#xff09;容器。它的主要作用是管理对…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

CMS内容管理系统的设计与实现:多站点模式的实现

在一套内容管理系统中&#xff0c;其实有很多站点&#xff0c;比如企业门户网站&#xff0c;产品手册&#xff0c;知识帮助手册等&#xff0c;因此会需要多个站点&#xff0c;甚至PC、mobile、ipad各有一个站点。 每个站点关联的有站点所在目录及所属的域名。 一、站点表设计…...