当前位置: 首页 > 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;所以使用起来…...

国防科技大学计算机基础课程笔记02信息编码

1.机内码和国标码 国标码就是我们非常熟悉的这个GB2312,但是因为都是16进制&#xff0c;因此这个了16进制的数据既可以翻译成为这个机器码&#xff0c;也可以翻译成为这个国标码&#xff0c;所以这个时候很容易会出现这个歧义的情况&#xff1b; 因此&#xff0c;我们的这个国…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

Nuxt.js 中的路由配置详解

Nuxt.js 通过其内置的路由系统简化了应用的路由配置&#xff0c;使得开发者可以轻松地管理页面导航和 URL 结构。路由配置主要涉及页面组件的组织、动态路由的设置以及路由元信息的配置。 自动路由生成 Nuxt.js 会根据 pages 目录下的文件结构自动生成路由配置。每个文件都会对…...

苍穹外卖--缓存菜品

1.问题说明 用户端小程序展示的菜品数据都是通过查询数据库获得&#xff0c;如果用户端访问量比较大&#xff0c;数据库访问压力随之增大 2.实现思路 通过Redis来缓存菜品数据&#xff0c;减少数据库查询操作。 缓存逻辑分析&#xff1a; ①每个分类下的菜品保持一份缓存数据…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...