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

Java-数据结构-并查集<二>

一.并查集的简单介绍

二. 并查集的主要构成和实现方式

三.HashMap模板和数组模板

由于在下文的模板基本一致,不再每次都罗列,大体的模板如下,若有错误可以在leetcode找到对应的题目解答,已经附上连接。

HashMap


class UnionFind {private Map<Integer,Integer> father;public UnionFind() {father = new HashMap<Integer,Integer>();}public void add(int x) {if (!father.containsKey(x)) {father.put(x, null);}}public void merge(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY){father.put(rootX,rootY);}}public int find(int x) {int root = x;while(father.get(root) != null){root = father.get(root);}while(x != root){int original_father = father.get(x);father.put(x,root);x = original_father;}return root;}public boolean isConnected(int x, int y) {return find(x) == find(y);}
}

数组

class UnionFind{public int[] parent;public int count;//初始化public UnionFind(int n){parent = new int[n];count = n;for(int i = 0; i< n; i++){parent[i] = i;}}//查找public int find(int x){while(x != parent[x]){parent[x] = parent[parent[x]];x = parent[x];}return x;}//合并节点public void union(int x, int y){if(find(x) == find(y)) return;parent[find(x)] = find(y);count--;}//是否为同一父节点,也就是是否联通public boolean isConnected(int x, int y){return find(x) == find(y);}//返回数量public int getCount(){return count;}
}

三. leetcode实战

1. leetcode547 省份数量

2. leetcode684 冗余连接

以上未出现部分圈全在在前篇文章,不再赘述

Java-数据结构-并查集<一>

3. leetcode1905 统计子岛屿

给你两个 m x n 的二进制矩阵 grid1 和 grid2 ,它们只包含 0 (表示水域)和 1 (表示陆地)。一个 岛屿 是由 四个方向 (水平或者竖直)上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。

如果 grid2 的一个岛屿,被 grid1 的一个岛屿 完全 包含,也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含,那么我们称 grid2 中的这个岛屿为 子岛屿 。

请你返回 grid2 中 子岛屿 的 数目 。

输入:grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
输出:3
解释:如上图所示,左边为 grid1 ,右边为 grid2 。
grid2 中标红的 1 区域是子岛屿,总共有 3 个子岛屿。

 

整体思路:

1.遍历grid2数组,利用并查集把区域都连通起来
2.将grid的根节点都添加到HashSet中
3.到grid1中找HashSet中对应的节点是不是1

以示例一为例

那么,在使用并查集后,我们的un2里面陆地联通的区域就是:
0,11,15,17,21
那么对应的HashSet里面也会是{0,11,15,17,21}
然后遍历grid1,找到HashSet对应的位置,是1的话,就可以符合题目要求。
HashSet中的11是不符合要求的,因为对应的grid1里面是0,同样
HashSet中的17也是同样的道理。 

主题函数部分(模板在上方)

class Solution {public int countSubIslands(int[][] grid1, int[][] grid2) {int row1 = grid1.length;int col1 = grid1[0].length;int row2 = grid2.length;int col2 = grid2[0].length;UnionFind un2 = new UnionFind(row2*col2);//遍历grid2for(int i = 0; i < row2; i++){for(int j = 0; j < col2; j++){if(grid2[i][j] == 0) continue;if(i+1 < row2 && grid2[i+1][j] == 1) un2.union(i*col2+j, i*col2+j+col2);if(j+1 < col2 && grid2[i][j+1] == 1) un2.union(i*col2+j, i*col2+j+1);}}//把grid2联通区域的根节点放进set中HashSet<Integer> set = new HashSet<>();for(int i = 0; i < row2; i++){for(int j = 0; j < col2; j++){if(grid2[i][j] == 1){set.add(un2.find(i*col2+j));}     }}//去grid1查找对应的点是不是1for(int i = 0; i < row1; i++){for(int j = 0; j < col1; j++){if(grid1[i][j] == 0){set.remove(un2.find(i*col2+j));}    }}return set.size();}
}

 原题解连接(若模板有出入可参考):

Java 并查集 超简单易懂附模板

 

4. leetcode1254 统计封闭岛屿的数目

二维矩阵 grid 由 0 (土地)和 1 (水)组成。岛是由最大的4个方向连通的 0 组成的群,封闭岛是一个 完全 由1包围(左、上、右、下)的岛。

请返回 封闭岛屿 的数目。

示例 1:
输入:grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出:2
解释:
灰色区域的岛屿是封闭岛屿,因为这座岛屿完全被水域包围(即被 1 区域包围)。

 

 整体思路

1. 用并查集走一遍grid,把岛屿都联通起来
2. 用HashSet添加岛屿的根节点
3. 把处于边上,也就是下图中红色部分排除掉(注意,此时排除的是对应是陆地的那个节点的根节点)

 也就是

if(grid[i][j] == 0){if(i == 0 || j == 0 || i == row-1 || j == col -1) set.remove(un.find(i*col+j));    
}

主函数中

if(i == 0 || j == 0 || i == row-1 || j == col -1)

可以排除掉图中红色的部分。

主函数部分

class Solution {public int closedIsland(int[][] grid) {int row = grid.length;int col = grid[0].length;UnionFind un = new UnionFind(row*col);for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(grid[i][j] == 1) continue;if(i+1 < row && grid[i+1][j] == 0) un.union(i*col+j, i*col+j+col);if(j+1 < col && grid[i][j+1] == 0) un.union(i*col+j, i*col+j+1);}}HashSet<Integer> set = new HashSet<>();for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(grid[i][j] == 0) set.add(un.find(i*col+j));    }}for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(grid[i][j] == 0){if(i == 0 || j == 0 || i == row-1 || j == col -1) set.remove(un.find(i*col+j));    }}}return set.size();}
}

原题解连接(若模板有出入可参考):
Java 并查集 思路简单附模板

 

5. leetcode130 被围绕的区域

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

示例 1:
输入:board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出:[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
解释:被围绕的区间不会存在于边界上,换句话说,任何边界上的 'O' 都不会被填充为 'X'。 
任何不在边界上,或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。
如果两个元素在水平或垂直方向相邻,则称它们是“相连”的。

整体思路:

1.这题和1254. 统计封闭岛屿的数目思路一样
2.只不过要的是外面的岛屿,而1254里要的是里卖的。

思路

1. 并查集走一遍,得到所有的父节点
2. 把所有的父节点添加到set中
3. 把边上的所有的岛排除掉(即排除边上的是'O'的父节点)(即下图红色的部分从set中排除)
4. 把剩在set中的父节点中的是'O'的都变成'X'

主函数

class Solution {public void solve(char[][] board) {int row = board.length;int col = board[0].length;UnionFind un = new UnionFind(row*col);for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'X') continue;if(i+1 < row && board[i+1][j] == 'O') un.union(i*col+j, i*col+j+col);if(j+1 < col && board[i][j+1] == 'O') un.union(i*col+j, i*col+j+1);}}HashSet<Integer> set = new HashSet<>();for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'O'){set.add(un.find(i*col +j));}}}for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'O'){if(i == 0 || j == 0 || i == row-1 || j == col-1){set.remove(un.find(i*col +j));}}}}for(int i = 0; i < row; i++){for(int j = 0; j < col; j++){if(board[i][j] == 'O'){if(set.contains(un.find(i*col +j))){board[i][j] = 'X';}}}}}
}

原题解连接(若模板有出入可参考):

Java 并查集 思路简单附模板

6. leetcode1319 连通网络的操作次数

用以太网线缆将 n 台计算机连接成一个网络,计算机的编号从 0 到 n-1。线缆用 connections 表示,其中 connections[i] = [a, b] 连接了计算机 a 和 b。

网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。

给你这个计算机网络的初始布线 connections,你可以拔开任意两台直连计算机之间的线缆,并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能,则返回 -1 。

输入:n = 4, connections = [[0,1],[0,2],[1,2]]
输出:1
解释:拔下计算机 1 和 2 之间的线缆,并将它插到计算机 1 和 3 上。

 思路:

1. 我们总共有的线的数量就是connections数组的数量
2. 连接n个电脑我们最少需要n-1条线
3. 并查集过后我们把已经连接的电脑看作一个整体m,如果线够用的情况下我们只需要m-1条线,不必在意具体要怎么连接

以示例2为例

示例 2:
输入:n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出:2

那么在并查集过后,并查集的数量是3,减一就可以得到我们需要的答案。

主函数

class Solution {public int makeConnected(int n, int[][] connections) {int len = connections.length;if(len < n-1) return -1;UnionFind un = new UnionFind(n);for(int i = 0; i < len; i++){un.union(connections[i][0],connections[i][1]);}return un.getcount()-1;}
}

原题解连接(若模板有出入可参考):

Java 并查集 简单易懂附模板

相关文章:

Java-数据结构-并查集<二>

一.并查集的简单介绍 二. 并查集的主要构成和实现方式 三.HashMap模板和数组模板 由于在下文的模板基本一致&#xff0c;不再每次都罗列&#xff0c;大体的模板如下&#xff0c;若有错误可以在leetcode找到对应的题目解答&#xff0c;已经附上连接。 HashMap class UnionFi…...

JSP网上教学资源共享系统(源代码+论文)

通过网上教学资源共享系统的建设&#xff0c;完成了对于操作系统课程的远程化授课。可以使学生不受时间空间的限制&#xff0c;通过网络对于这门课程进行学习。建立起了基于B/C的网络化教学系统。本网站采用当前最流行的JSP网络编程技术&#xff0c;可以实现数据的高效、动态、…...

QT C++入门学习(1) QT Creator安装和使用

Qt官方下载 Qt 官网有一个专门的资源下载网站&#xff0c;所有的开发环境和相关工具都可以从这里下载&#xff0c;具体地址是&#xff1a;http://download.qt.io/ 进入链接后&#xff0c;是一个文件目录&#xff0c;依次进入这个路径&#xff1a;archive/qt/5.12/5.12.9/qt-o…...

UE动画状态机的事件触发顺序测试

正常A状态过渡到B状态的事件顺序&#xff1a; 整个流程为&#xff1a; 调用B状态的On Become Relevant事件调用B状态的On Update事件调用A状态的Left State Event事件调用B状态的Entered State Event事件调用B状态的Start Transition Event事件调用B状态的End Transition Even…...

数学建模的搜索技巧

你真的会使用“度娘”吗&#xff1f;是不是在查找所需要的东西的时候&#xff0c;搜出来的信息价值并不是很大&#xff0c;跟着北海老师学习&#xff0c;如何更高效的使用百度去查询自己想要的&#xff0c;有用的资料&#xff01; 搜索技巧 完全匹配搜索 : 查询词的外边加上双…...

学成在线笔记+踩坑(10)——课程搜索、课程发布时同步索引库。

导航&#xff1a; 【黑马Java笔记踩坑汇总】JavaSEJavaWebSSMSpringBoot瑞吉外卖SpringCloud黑马旅游谷粒商城学成在线牛客面试题_java黑马笔记 目录 1 【检索模块】需求分析 1.1 全文检索介绍 1.2 业务流程 1.2.1、课程发布时索引库里新增一条记录 1.2.2、课程搜索 2 准…...

某应用虚拟化系统远程代码执行

漏洞简介 微步在线漏洞团队通过“X漏洞奖励计划”获取到瑞友天翼应用虚拟化系统远程代码执行漏洞情报(0day)&#xff0c;攻击者可以通过该漏洞执行任意代码&#xff0c;导致系统被攻击与控制。瑞友天翼应用虚拟化系统是基于服务器计算架构的应用虚拟化平台&#xff0c;它将用户…...

solaris-Oracle11g于linux-mysql相连

Oracle11g(solaris64sparc)mysql(linux)实验 此实验目的,实现公司ebs R12 连mysql上的短信平台.预警和提示ebs中信息, 一,环境 主机名 ip 平台 数据库 dbname ebs234 192.168.1.234 …...

大厂齐出海:字节忙种草,网易爱社交

配图来自Canva可画 随着国内移动互联网红利逐渐触顶&#xff0c;互联网市场日趋饱和&#xff0c;国内各互联网企业之间的竞争便愈发激烈起来。在此背景下&#xff0c;广阔的海外市场就成为了腾讯、阿里、字节、京东、拼多多、百度、网易、快手、B站等互联网公司关注和争夺的重…...

几个实用的正则表达式

1到100之间的正整数正则 表达式&#xff1a;^[1-9]\d?$|^100$ 解释&#xff1a; ^表示匹配字符串开始位置 [1-9]表示数字1-9中的任意一个 \d表示任意一个数字 ?表示前面一个字符或子表达式出现0或1次 $表示匹配字符串结束位置 |表示或 最终的解释为&#xff1a;匹配满…...

python实战应用讲解-【numpy数组篇】常用函数(八)(附python示例代码)

目录 Python Numpy MaskedArray.cumprod()函数 Python Numpy MaskedArray.cumsum()函数 Python Numpy MaskedArray.default_fill_value()函数 Python Numpy MaskedArray.flatten()函数 Python Numpy MaskedArray.masked_equal()函数 Python Numpy MaskedArray.cumprod()函…...

Speech and Language Processing-之N-gram语言模型

正如一句老话所说&#xff0c;预测是困难的&#xff0c;尤其是预测未来。但是&#xff0c;如何预测一些看起来容易得多的事情&#xff0c;比如某人接下来要说的几句话后面可能跟着哪个单词。 希望你们大多数人都能总结出一个很可能的词是in&#xff0c;或者可能是over&#x…...

【AI】Python 安装时启用长路径支持

文章目录 场景&#xff1a;解释&#xff1a;关于文件长路径&#xff1a;计算方法&#xff1a; 场景&#xff1a; Python 安装时&#xff0c;会出现 Disable path length limit 的提示。 解释&#xff1a; 在 Windows 操作系统中&#xff0c;文件路径的长度是有限制的。在早期…...

深入理解Go语言中的接口编程【17】

文章目录 接口接口接口类型为什么要使用接口接口的定义实现接口的条件接口类型变量值接收者和指针接收者实现接口的区别值接收者实现接口指针接收者实现接口下面的代码是一个比较好的面试题 类型与接口的关系一个类型实现多个接口多个类型实现同一接口接口嵌套 空接口空接口的定…...

“数字中国·福启海丝”多屏互动光影艺术秀27日在福州举办

作为深化“数字海丝”的核心区、海上丝绸之路的枢纽城市&#xff0c;为喜迎第六届数字中国建设峰会盛大召开之际&#xff0c;福州市人民政府特此举办“数字中国福启海丝”多屏互动光影秀活动。本次光影秀活动是由福建省文化和旅游厅指导&#xff0c;福州市人民政府主办&#xf…...

Docker安装mysql8.0文档

第一步需要安装Docker基础环境&#xff0c;具体可以看看这篇 docker基础篇 第二步&#xff0c;拉取mysql8.0的镜像 docker pull mysql:8.0 第三步&#xff0c;镜像启动和文件挂载 复制下面命令执行&#xff0c;33006是对外访问暴露的端口&#xff0c;当然你也可以设置为3306…...

在函数中使用变量

shell脚本编程系列 向函数传递参数 函数可以使用标准的位置变量来表示在命令行中传给函数的任何参数。其中函数名保存在$0变量中&#xff0c;函数参数则依次保存在$1、$2等变量当中&#xff0c;也可以使用特殊变量$#来确定参数的个数 在脚本中调用函数时&#xff0c;必须将参…...

python算法中的深度学习算法之自编码器(详解)

目录 学习目标: 学习内容: 自编码器 Ⅰ. 编码器(Encoder) Ⅱ. 解码器(Decoder)...

Python入门(一)Python概述与环境搭建

Python概述与环境搭建 1.概述1.1版本及下载1.2 Python 特点 2.环境搭建3.第一个程序“hello&#xff0c;world”4.可能会存在的问题 1.概述 Python 是一个高层次的结合了解释性、编译性、互动性和面向对象的脚本语言。 Python 的设计具有很强的可读性&#xff0c;相比其他语言…...

02_Lock锁

首先看一下JUC的重磅武器——锁&#xff08;Lock&#xff09; 相比同步锁&#xff0c;JUC包中的Lock锁的功能更加强大&#xff0c;它提供了各种各样的锁&#xff08;公平锁&#xff0c;非公平锁&#xff0c;共享锁&#xff0c;独占锁……&#xff09;&#xff0c;所以使用起来…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

论文浅尝 | 基于判别指令微调生成式大语言模型的知识图谱补全方法(ISWC2024)

笔记整理&#xff1a;刘治强&#xff0c;浙江大学硕士生&#xff0c;研究方向为知识图谱表示学习&#xff0c;大语言模型 论文链接&#xff1a;http://arxiv.org/abs/2407.16127 发表会议&#xff1a;ISWC 2024 1. 动机 传统的知识图谱补全&#xff08;KGC&#xff09;模型通过…...

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

iOS性能调优实战:借助克魔(KeyMob)与常用工具深度洞察App瓶颈

在日常iOS开发过程中&#xff0c;性能问题往往是最令人头疼的一类Bug。尤其是在App上线前的压测阶段或是处理用户反馈的高发期&#xff0c;开发者往往需要面对卡顿、崩溃、能耗异常、日志混乱等一系列问题。这些问题表面上看似偶发&#xff0c;但背后往往隐藏着系统资源调度不当…...

Qemu arm操作系统开发环境

使用qemu虚拟arm硬件比较合适。 步骤如下&#xff1a; 安装qemu apt install qemu-system安装aarch64-none-elf-gcc 需要手动下载&#xff0c;下载地址&#xff1a;https://developer.arm.com/-/media/Files/downloads/gnu/13.2.rel1/binrel/arm-gnu-toolchain-13.2.rel1-x…...

MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用

文章目录 一、背景知识&#xff1a;什么是 B-Tree 和 BTree&#xff1f; B-Tree&#xff08;平衡多路查找树&#xff09; BTree&#xff08;B-Tree 的变种&#xff09; 二、结构对比&#xff1a;一张图看懂 三、为什么 MySQL InnoDB 选择 BTree&#xff1f; 1. 范围查询更快 2…...