当前位置: 首页 > 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;能对你有…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

python/java环境配置

环境变量放一起 python&#xff1a; 1.首先下载Python Python下载地址&#xff1a;Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个&#xff0c;然后自定义&#xff0c;全选 可以把前4个选上 3.环境配置 1&#xff09;搜高级系统设置 2…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

Pinocchio 库详解及其在足式机器人上的应用

Pinocchio 库详解及其在足式机器人上的应用 Pinocchio (Pinocchio is not only a nose) 是一个开源的 C 库&#xff0c;专门用于快速计算机器人模型的正向运动学、逆向运动学、雅可比矩阵、动力学和动力学导数。它主要关注效率和准确性&#xff0c;并提供了一个通用的框架&…...

《C++ 模板》

目录 函数模板 类模板 非类型模板参数 模板特化 函数模板特化 类模板的特化 模板&#xff0c;就像一个模具&#xff0c;里面可以将不同类型的材料做成一个形状&#xff0c;其分为函数模板和类模板。 函数模板 函数模板可以简化函数重载的代码。格式&#xff1a;templa…...

Caliper 配置文件解析:fisco-bcos.json

config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...

MySQL的pymysql操作

本章是MySQL的最后一章&#xff0c;MySQL到此完结&#xff0c;下一站Hadoop&#xff01;&#xff01;&#xff01; 这章很简单&#xff0c;完整代码在最后&#xff0c;详细讲解之前python课程里面也有&#xff0c;感兴趣的可以往前找一下 一、查询操作 我们需要打开pycharm …...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...