当前位置:网站首页>五月刷题26——并查集
五月刷题26——并查集
2022-07-06 09:02:00 【追逐梦想的阿光】
今日刷题内容: 并查集
前言
- 一个算法废材的刷题之路开更了, 更新每天刷题的题解内容
- 注重个人理解,看难度更新题目数量
- 题目来源于力扣
- 新开专栏,争取每日都能做出至少一题=v=
- 语言java、python、c\c++
一、今日题目
今天只做完了一题,没剩下多少时间了,改日再补完剩下的吧
二、解题思路
1. 990. 等式方程的可满足性
- 使用并查集将所有
==
的字符归到一类- 查找
!=
的字符是否存在属于一类的情况- 如果存在属于一类,说明这两个字符已经属于等式,返回
false
,否则为true
class Solution {
int N = 256;
int[] fset;
// 初始化并查集,使用字符来存储
public void init(){
fset = new int[N];
for(int i=0; i < N; i++){
fset[i] = i;
}
}
// 查找隶属于哪个集合
public int find(int x){
if (x == fset[x]){
return x;
}else{
// 将沿途节点的父节点都设置为根节点
fset[x] = find(fset[x]);
return fset[x];
}
}
// 合并集合
public boolean merge(int x, int y){
int rx = find(x);
int ry = find(y);
if (rx != ry){
fset[rx] = ry;
return false;
}
return true;
}
public boolean equationsPossible(String[] equations) {
int n = equations.length;
init();
// 把两个字符相等的合并到一个集合内
for (String e: equations){
if (e.charAt(1) == '='){
merge(e.charAt(0), e.charAt(3));
}
}
// 如果这两个字符已经在相等的集合内,还在方程中出现了!,说明必定为假
for(String e: equations){
if (e.charAt(1) == '!'){
if ( find(e.charAt(0)) == find(e.charAt(3)) ){
return false;
}
}
}
return true;
}
}
/* * 使用并查集,只有当所有的方程都属于一个集合时可以满足题目条件 */
2. 1319. 连通网络的操作次数
采用朴素法和路径压缩的方式解决问题
路径压缩和并查集相关查看此文章并查集
- 这题,使用并查集的朴素法做完的
- 将所有的有连通的计算机合并在一起
- 在统计所有集合的数量,将所有的集合数量-1就是答案
朴素法代码如下:
class Solution {
int[] fset;
int N;
/* * 初始化并查集 */
public void init(int n){
fset = new int[n];
int i;
for(i = 0; i < n; i++){
fset[i] = i;
}
}
/* * 查找x隶属于哪个集合 */
public int find(int x){
return fset[x];
}
/* * 合并两个集合 */
public void merge(int x, int y){
int rx = find(x);
int ry = find(y);
// 找到各自隶属的集合,如果不同集合,则将两个合并
if (rx != ry){
for (int i = 0; i < N; i++){
if (fset[i] == ry){
fset[i] = rx;
}
}
}
}
public int makeConnected(int n, int[][] connections) {
int m = connections.length;
int i;
N = n;
if(m < n - 1){
return - 1; // n台计算机,至少需要n-1条电缆
}
init(n); // 初始化
int count = 0;
int[] hash = new int[n];
for(int[] nums: connections){
merge(nums[0], nums[1]); // 合并两个有连接的计算机
}
for(i = 0 ; i < n; i++){
int setId = find(i);
if (hash[setId] == 0){
hash[setId]++;
count++;
}
}
return count - 1;
// System.out.println(fset[3]);
}
}
/* n台计算机,至少需要n-1台线缆 计算所有同属于一个集合的计算机台数 找出不属于一个集合的独立计算机个数即是答案 */
路径压缩代码如下:
class Solution {
int[] fset;
int N;
/* * 初始化并查集 */
public void init(int n){
fset = new int[n];
int i;
for(i = 0; i < n; i++){
fset[i] = i;
}
}
/* * 查找x隶属于哪个集合,并将路径上的点的父节点都设置为rx */
public int find(int x){
if (x == fset[x]){
return x;
}else{
fset[x] = find(fset[x]);
return fset[x];
}
}
/* * 合并两个集合??? */
public boolean merge(int x, int y){
int rx = find(x);
int ry = find(y);
// 找到各自隶属的集合,如果不同集合,则将两个合并
if (rx != ry){
fset[rx] = ry;
return true;
}
return false;
}
public int makeConnected(int n, int[][] connections) {
int m = connections.length;
int i;
N = n;
if(m < n - 1){
return - 1; // n台计算机,至少需要n-1条电缆
}
init(n); // 初始化
int count = 0;
int[] hash = new int[n];
for(int[] nums: connections){
merge(nums[0], nums[1]); // 合并两个有连接的计算机
}
for(i = 0 ; i < n; i++){
int setId = find(i);
if (hash[setId] == 0){
hash[setId]++;
count++;
}
}
return count - 1;
// System.out.println(fset[3]);
}
}
/* n台计算机,至少需要n-1台线缆 计算所有同属于一个集合的计算机台数 找出不属于一个集合的独立计算机个数即是答案 */
3. 886. 可能的二分法
边栏推荐
- Global and Chinese markets for small seed seeders 2022-2028: Research Report on technology, participants, trends, market size and share
- AcWing 2456. 记事本
- Vs All comments and uncomments
- DCDC power ripple test
- MapReduce工作机制
- Servlet learning diary 7 -- servlet forwarding and redirection
- 发生OOM了,你知道是什么原因吗,又该怎么解决呢?
- 068.查找插入位置--二分查找
- Redis之五大基础数据结构深入、应用场景
- Global and Chinese market of cup masks 2022-2028: Research Report on technology, participants, trends, market size and share
猜你喜欢
为拿 Offer,“闭关修炼,相信努力必成大器
Redis geospatial
Mathematical modeling 2004b question (transmission problem)
DCDC power ripple test
Nacos installation and service registration
Lua script of redis
[three storage methods of graph] just use adjacency matrix to go out
Redis之Lua脚本
基于B/S的影视创作论坛的设计与实现(附:源码 论文 sql文件 项目部署教程)
Mapreduce实例(八):Map端join
随机推荐
基于B/S的影视创作论坛的设计与实现(附:源码 论文 sql文件 项目部署教程)
How to intercept the string correctly (for example, intercepting the stock in operation by applying the error information)
Redis之Lua脚本
Selenium+pytest automated test framework practice
为什么要数据分层
Research and implementation of hospital management inpatient system based on b/s (attached: source code paper SQL file)
运维,放过监控-也放过自己吧
Sqlmap installation tutorial and problem explanation under Windows Environment -- "sqlmap installation | CSDN creation punch in"
Chapter 1 :Application of Artificial intelligence in Drug Design:Opportunity and Challenges
Servlet learning diary 8 - servlet life cycle and thread safety
Design and implementation of online snack sales system based on b/s (attached: source code paper SQL file)
Leetcode:608 树节点
Global and Chinese market of bank smart cards 2022-2028: Research Report on technology, participants, trends, market size and share
【每日一题】搬运工 (DFS / DP)
Withdrawal of wechat applet (enterprise payment to change)
美团二面:为什么 Redis 会有哨兵?
Redis core configuration
工作流—activiti7环境搭建
Kratos ares microservice framework (II)
MapReduce工作机制