想要精通算法和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);}
}

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

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

相关文章

R语言教程课后习题答案(持续更新中~~)

R语言教程网址如下 https://www.math.pku.edu.cn/teachers/lidf/docs/Rbook/html/_Rbook/index.html 目录 source()函数可以运行保存在一个文本文件中的源程序 R向量下标和子集 数值型向量及其运算 日期功能 R因子类型 source()函数可以运行保存在一个文本文件中的源程序…

【C语言】动态通讯录(超详细)

通讯录是一个可以很好锻炼我们对结构体的使用&#xff0c;加深对结构体的理解&#xff0c;在为以后学习数据结构打下结实的基础 这里我们想设计一个有添加联系人&#xff0c;删除联系人&#xff0c;查找联系人&#xff0c;修改联系人&#xff0c;展示联系人&#xff0c;排序这几…

快速了解Spring Cache

SpringCache是一个框架&#xff0c;实现了基于注解的缓存功能&#xff0c;只需要简单的加一个注解&#xff0c;就可以实现缓存功能。 SpringCache提供了一层抽象&#xff0c;底层可以切换不同的缓存实现。例如&#xff1a; EHChche Redis Caffeine 常用注解&#xff1a; Enabl…

Vue中如何进行分布式路由配置与管理

Vue中的分布式路由配置与管理 随着现代Web应用程序的复杂性不断增加&#xff0c;分布式路由配置和管理成为了一个重要的主题。Vue.js作为一种流行的前端框架&#xff0c;提供了多种方法来管理Vue应用程序的路由。本文将深入探讨在Vue中如何进行分布式路由配置与管理&#xff0…

全志ARM926 Melis2.0系统的开发指引⑧

全志ARM926 Melis2.0系统的开发指引⑧ 编写目的12.5. 应用程序编写12.5.1. 简单应用编写12.5.1.1. 注册应用12.5.1.2. 创建管理窗口12.5.1.3. 实现管理窗口消息处理回调函数12.5.1.4. 创建图层12.5.1.5. 创建 framewin12.5.1.6. 实现 framewin 消息处理回调函数 -. 全志相关工具…

【BBC新闻文章分类】使用 TF 2.0和 LSTM 的文本分类

一、说明 NLP上的许多创新是如何将上下文添加到词向量中。常见的方法之一是使用递归神经网络

SSM-XML整合

SSM-XML整合 核心配置文件 maven坐标 <dependencies><!--数据库驱动--><dependency><groupId>mysql</groupId><artifactId>mysql-connector-java</artifactId><version>8.0.27</version></dependency><!--数据…

解决dockerfile创建镜像时pip install报错的bug

项目场景&#xff1a; 使用docker-compose创建django容器 问题描述 > [5/5] RUN /bin/bash -c source ~/.bashrc && python3 -m pip install -r requirements.txt -i https://pypi.tuna.tsinghua.edu.cn/simple: 0.954 Looking in indexes: https://…

Next.js 入门笔记

前言 之前初步体验了 React 的魅力, 又看文档理解了一下 useState 和 useEffect, 目前初步理解的概念是: useState 用来声明在组件中使用并且需要修改的变量 useEffect 用来对 useState 声明的变量进行初始化赋值 可能理解的不太准确, 不过大概差不多是这么个意思. 但是再往后…

1.3.OpenCV技能树--第一单元--图像的基础操作(基础篇)

文章目录 1.文章内容来源2.图像的基本操作2.1.图像加载2.2.图像显示2.3.数据读取2.4.截取图像2.5.颜色通道提取2.5.1.保留红色处理2.5.2.保留绿色处理2.5.3.保留蓝色处理 3.易错点总结与反思 1.文章内容来源 1.题目来源: 2.资料来源:https://edu.csdn.net/skill/opencv/opencv…

软技能继续挑战网络安全领域

根据 ISACA 的一份新报告&#xff0c;新的网络安全调查结果指出了网络安全专家缺乏的领域&#xff0c;其中人际技能、云计算和安全措施是网络安全专家最突出的技能缺陷。 59% 的网络安全领导者表示他们的团队人手不足。50% 的受访者表示有非入门级职位的职位空缺&#xff0c;而…

八大排序源码(含优化)

文章目录 1、直接插入排序2、希尔排序3、选择排序4、冒泡排序5、堆排序6、快速排序快速排序递归实现霍尔法挖坑法前后指针法快速排序小区间优化 快速排序非递归实现 7、归并排序归并排序递归实现归并排序非递归 8、计数排序 大家好&#xff0c;我是纪宁&#xff0c;这篇文章是关…

GPT系列论文解读:GPT-2

GPT系列 GPT&#xff08;Generative Pre-trained Transformer&#xff09;是一系列基于Transformer架构的预训练语言模型&#xff0c;由OpenAI开发。以下是GPT系列的主要模型&#xff1a; GPT&#xff1a;GPT-1是于2018年发布的第一个版本&#xff0c;它使用了12个Transformer…

VUE3照本宣科——认识VUE3

VUE3照本宣科——认识VUE3 前言一、命令创建项目1.中文官网2.菜鸟教程 二、VUE3项目目录结构1.public2.src&#xff08;1&#xff09;assets&#xff08;2&#xff09;components 3. .eslintrc.cjs4. .gitignore5. .prettierrc.json6.index.html7.package.json8.README.md9.vit…

进程调度算法之时间片轮转调度(RR),优先级调度以及多级反馈队列调度

1.时间片轮转调度算法(RR) round Robin 1.算法思想 公平地、轮流地为各个进程服务&#xff0c;让每个进程在一定时间间隔内都可以得到响应。 2.算法规则 按照各进程到达就绪队列的顺序&#xff0c;轮流让各个进程执行一个时间片&#xff08;如100ms&#xff09;。 若进程未…

Linux 文件上传、下载

1、通过FinalShell工具虚拟机进行数据交换 在FinalShell软件的下方窗体中&#xff0c;提供了Linux的文件系统视图&#xff0c;可以方便的&#xff1a; 浏览文件系统&#xff0c;找到合适的文件&#xff0c;右键点击下载&#xff0c;即可传输到本地电脑 浏览文件系统&#xff0…

数值分析学习笔记——绪论【华科B站教程版本】

绪论 数值分析概念 用计算机求解数学问题的数值方法和理论 三大科学研究方法 实验理论分析科学计算&#xff08;用计算机去辅助研究&#xff09;&#xff1a;数值方法计算机 解析解和近似解 解析解&#xff1a;使用数学方法求出或推导出的结果&#xff0c;往往可以求解出…

【STL】list常见用法及模拟实现(附完整源码)

目录 前言1. list介绍及使用1.1 list介绍1.2 list使用 2. list模拟实现2.1 迭代器功能分类2.2 list迭代器模拟实现2.2.1 普通迭代器2.2.2 const迭代器 3. list和vector区别4. 源码 前言 这篇文章我们继续STL中容器的学习&#xff0c;这篇文章要讲解的是list。 1. list介绍及使用…

软件工程与计算总结(三)示例项目描述

本节介绍一个标准的项目描述&#xff0c;大家可以作为蓝本学习~ 目录 一.背景 二.目标 三.系统用户 四.用户访谈要点 1.收银员 2.客户经理 3.总经理 4.系统管理员 五.项目实践过程 一.背景 A是一家刚刚发展起来的小型连锁商店&#xff0c;其前身是一家独立的小百货门面…

SDL2绘制ffmpeg解析的mp4文件

文章目录 1.FFMPEG利用命令行将mp4转yuv4202.ffmpeg将mp4解析为yuv数据2.1 核心api: 3.SDL2进行yuv绘制到屏幕3.1 核心api 4.完整代码5.效果展示6.SDL2事件响应补充6.1 处理方式-016.2 处理方式-02 本项目采用生产者消费者模型&#xff0c;生产者线程&#xff1a;使用ffmpeg将m…