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

并查集---力扣547省份的数量

假设:有一群小混混打架,小弟们可能互相不认识,如果要确定他们是一伙的,就需要确定他们的组长是不是一个,但是每个组长的领导可能又不一样,所以要找到最大的那个领导,才能确定是一伙的。

我们先初始化一个数组,用来存储每个成员的领导,初始化每个成员的领导就是他自己。

   void init(int[] pre) {for (int i = 0; i < pre.length; i++) {pre[i]=i;}}

通过find方法来寻找每位成员的直属领导

  //查找元素的最高上级int find(int x,int [] pre){//因为初始化的时候,我们将所有元素的最高级设为自己//所以最高级是自己的元素即为最高级元素while (pre[x]!=x){//如果当前元素不是最高级,继续去找它上级的上级x=pre[x];}return x;}

但是可能存在着这样的关系,A的领导是B,B的领导是C,C的领导是D。甲的领导是乙,乙的领导是丙,丙的领导是丁。这样就意味着存在两个组织。但是丙又成为了B的领导,所以这两个资质就需要进行合并成为一个组织。

对应以下代码

 //合并void merge(int x,int y,int pre[]){int a=find(x,pre);int b=find(y,pre);pre[a]=b;}

力扣链接:547. 省份数量 - 力扣(LeetCode)

class Solution {//查找元素的最高上级int find(int x,int [] pre){//因为初始化的时候,我们将所有元素的最高级设为自己//所以最高级是自己的元素即为最高级元素while (pre[x]!=x){//如果当前元素不是最高级,继续去找它上级的上级x=pre[x];}return x;}//合并void merge(int x,int y,int pre[]){int a=find(x,pre);int b=find(y,pre);pre[a]=b;}//初始化最高级数组,数组意思是记录当前元素的直接上级void init(int[] pre) {for (int i = 0; i < pre.length; i++) {pre[i]=i;}}public int findCircleNum(int[][] isConnected) {int pre[] = new int[isConnected.length];//元素的数量init(pre);for (int i = 0; i < isConnected.length; i++) {for (int j = 0; j < isConnected[i].length; j++) {if(i!=j){if(isConnected[i][j]==1){merge(i,j,pre);}}}}int count=0;for (int i = 0; i < pre.length; i++) {if(pre[i]==i){count++;}}return count;}
}

相关文章:

并查集---力扣547省份的数量

假设&#xff1a;有一群小混混打架&#xff0c;小弟们可能互相不认识&#xff0c;如果要确定他们是一伙的&#xff0c;就需要确定他们的组长是不是一个&#xff0c;但是每个组长的领导可能又不一样&#xff0c;所以要找到最大的那个领导&#xff0c;才能确定是一伙的。 我们先…...

stm32启动文件里面的__main和主函数main()

一、__main和main()之间的关系 先来对stm32启动过程简单学习 启动文件里面的Reset_Handler&#xff1a; 调用过程&#xff1a; stm32在启动后先进入重启中断函数Reset_Handler&#xff0c;其中会先后调用SystemInit和__main函数&#xff0c; __main函数属于c库函数&…...

曲线生成 | 图解Reeds-Shepp曲线生成原理(附ROS C++/Python/Matlab仿真)

目录 0 专栏介绍1 什么是Reeds-Shepp曲线&#xff1f;2 Reeds-Shepp曲线的运动模式3 Reeds-Shepp曲线算法原理3.1 坐标变换3.2 时间翻转(time-flip)3.3 反射变换(reflect)3.4 后向变换(backwards) 4 仿真实现4.1 ROS C实现4.2 Python实现4.3 Matlab实现 0 专栏介绍 &#x1f5…...

深入探讨iOS开发:从创建第一个iOS程序到纯代码实现全面解析

iOS开发作为移动应用开发的重要领域之一&#xff0c;对于开发人员具有重要意义。本文将深入探讨iOS开发的各个方面&#xff0c;从创建第一个iOS程序到纯代码实现iOS开发&#xff0c;带领读者全面了解iOS应用程序的开发流程和技术要点。 &#x1f4f1; 第一个iOS程序 在创建第…...

Python学习之-正则表达式

目录 前言&#xff1a;1.re.serach1.1例子&#xff1a; 2.re.match2.1示例1&#xff1a;2.2 示例2&#xff1a; 3.re.findall3.1 示例 4.re.fullmatch4.1 示例1&#xff1a;4.2 示例2: 5.re.split5.1 示例1:5.2 示例2&#xff1a;5.3 示例3&#xff1a; 6.re.sub6.1 示例&#…...

Godot.NET C# 工程化开发(1):通用Nuget 导入+ 模板文件导出,包含随机数生成,日志管理,数据库连接等功能

文章目录 前言Github项目地址&#xff0c;包含模板文件后期思考补充项目设置编写失误环境visual studio 配置详细的配置看我这篇文章 Nuget 推荐NewtonSoft 成功Bogus 成功Github文档地址随机生成构造器生成构造器接口(推荐) 文件夹设置Nlog 成功&#xff01;Nlog.configNlogHe…...

数据仓库——雪花模式以及层次递归

层次结构 钻取 向下钻取&#xff1a;对某些代表事实的报表中添加维度细节 向上钻取&#xff1a;从某些代表事实的报表中去除维度细节 属性层次 提供了一种自然方法&#xff0c;用于顺序地在不断深入的层次上组织事实。许多维度可以被理解为包含连续主从关系的属性层次。此类…...

Transformer的前世今生 day09(Transformer的框架概述)

前情提要 编码器-解码器结构 如果将一个模型分为两块&#xff1a;编码器和解码器那么编码器-解码器结构为&#xff1a;编码器负责处理输入&#xff0c;解码器负责生成输出流程&#xff1a;我们先将输入送入编码器层&#xff0c;得到一个中间状态state&#xff0c;并送入解码器…...

Qt 压缩/解压文件

前面讲了很多Qt的文件操作&#xff0c;文件操作自然就包括压缩与解压缩文件了&#xff0c;正好最近项目里要用到压缩以及解压缩文件&#xff0c;所以就研究了一下Qt如何压缩与解压缩文件。 QZipReader/QZipWriter QZipReader 和 QZipWriter 类提供了用于读取和写入 ZIP 格式文…...

【leetcode刷题之路】面试经典150题(8)——位运算+数学+一维动态规划+多维动态规划

文章目录 20 位运算20.1 【位运算】二进制求和20.2 【位运算】颠倒二进制位20.3 【位运算】位1的个数20.4 【位运算】只出现一次的数字20.5 【哈希表】【位运算】只出现一次的数字 II20.6 【位运算】数字范围按位与 21 数学21.1 【双指针】回文数21.2 【数学】加一21.3 【数学】…...

JetBrains全家桶激活,分享 WebStorm 2024 激活的方案

大家好&#xff0c;欢迎来到金榜探云手&#xff01; WebStorm公司简介 JetBrains 是一家专注于开发工具的软件公司&#xff0c;总部位于捷克。他们以提供强大的集成开发环境&#xff08;IDE&#xff09;而闻名&#xff0c;如 IntelliJ IDEA、PyCharm、和 WebStorm等。这些工具…...

Sublime 彻底解决中文乱码

1. 按ctrl&#xff0c;打开Console&#xff0c;输入如下代码&#xff1a; import urllib.request,os; pf Package Control.sublime-package; ipp sublime.installed_packages_path(); urllib.request.install_opener( urllib.request.build_opener( urllib.request.ProxyHand…...

复旦大学EMBA校友出席两会建言献策助力中国发展

阳春三月&#xff0c;备受瞩目的全国两会如期召开。期间&#xff0c;复旦大学EMBA多位校友作为第十四届全国人民代表大会代表、第十四届全国政协委员与全国各地代表共商国是。      无论是作为大型央企负责人&#xff0c;还是作为科创企业的中坚力量&#xff0c;复旦大学EM…...

virtualbox导入vdi

新建虚拟机 点击新建 输入新建属性 配置cpu和内存 虚拟硬盘 这里选择已有的vdi文件 摘要 这里点击完成 虚拟机添加成功 点击启动&#xff0c;启动虚拟机 注意 这个时候的ip&#xff0c;还是以前镜像的ip&#xff0c;如果两个镜像一起启动&#xff0c;则需要修 改ip地…...

【信号处理】基于DGGAN的单通道脑电信号增强和情绪检测(tensorflow)

关于 情绪检测&#xff0c;是脑科学研究中的一个常见和热门的方向。在进行情绪检测的分类中&#xff0c;真实数据不足&#xff0c;经常导致情绪检测模型的性能不佳。因此&#xff0c;对数据进行增强&#xff0c;成为了一个提升下游任务的重要的手段。本项目通过DCGAN模型实现脑…...

使用 Docker Compose 部署 Spring Boot 应用

使用 Docker Compose 部署 Spring Boot 应用 第一步&#xff1a;创建 Spring Boot 应用的 Dockerfile 在您的 Spring Boot 项目根目录中创建一个 Dockerfile。 编辑 Dockerfile&#xff0c;添加以下内容&#xff1a; # 基础镜像使用 OpenJDK FROM openjdk:11-jdk-slim# 维护者…...

nginx 正向代理 https

问题背景 因为网络环境受限&#xff0c;应用服务器无法直接访问外网&#xff0c;需要前置机上中转一下&#xff0c;这种情况可在应用服务器修改/etc/hosts文件指向前置机&#xff0c;在前置机上的nginx设置四层代理&#xff0c;从而出站。 方案 根据How to Use NGINX as an …...

vue3从其他页面跳转页面头部组件菜单el-menu菜单高亮

主要代码 import { ref, onMounted, watch } from vue; const activeIndex ref("/"); const route useRoute();onMounted(() > {updateActiveMenu(); });watch(() > route.path, updateActiveMenu);function updateActiveMenu() {// 根据路由更新activeMenu…...

python 条件循环语句

python 条件循环语句 一、条件控制语句1. Python3 条件控制2. if 语句3. if 嵌套4. match...case5. 注意&#xff1a; 二、循环控制语句1. Python3 循环语句2. while 循环3. 无限循环4. while 循环使用 else 语句5. 简单语句组6. for 语句7. for...else8. break 和 continue 语…...

CIM搭建实现发送消息的效果

目录 背景过程1、下载代码2、进行配置3、直接启动项目4、打开管理界面5、启动web客户端实例项目6、发送消息 项目使用总结 背景 公司项目有许多需要发送即时消息的场景&#xff0c;之前一直采用的是传统的websocket连接&#xff0c;它会存在掉线严重&#xff0c;不可重连&…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

阿里云ACP云计算备考笔记 (5)——弹性伸缩

目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Robots.txt 文件

什么是robots.txt&#xff1f; robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...

12.找到字符串中所有字母异位词

&#x1f9e0; 题目解析 题目描述&#xff1a; 给定两个字符串 s 和 p&#xff0c;找出 s 中所有 p 的字母异位词的起始索引。 返回的答案以数组形式表示。 字母异位词定义&#xff1a; 若两个字符串包含的字符种类和出现次数完全相同&#xff0c;顺序无所谓&#xff0c;则互为…...

【碎碎念】宝可梦 Mesh GO : 基于MESH网络的口袋妖怪 宝可梦GO游戏自组网系统

目录 游戏说明《宝可梦 Mesh GO》 —— 局域宝可梦探索Pokmon GO 类游戏核心理念应用场景Mesh 特性 宝可梦玩法融合设计游戏构想要素1. 地图探索&#xff08;基于物理空间 广播范围&#xff09;2. 野生宝可梦生成与广播3. 对战系统4. 道具与通信5. 延伸玩法 安全性设计 技术选…...

OPenCV CUDA模块图像处理-----对图像执行 均值漂移滤波(Mean Shift Filtering)函数meanShiftFiltering()

操作系统&#xff1a;ubuntu22.04 OpenCV版本&#xff1a;OpenCV4.9 IDE:Visual Studio Code 编程语言&#xff1a;C11 算法描述 在 GPU 上对图像执行 均值漂移滤波&#xff08;Mean Shift Filtering&#xff09;&#xff0c;用于图像分割或平滑处理。 该函数将输入图像中的…...

如何更改默认 Crontab 编辑器 ?

在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...

GitHub 趋势日报 (2025年06月06日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...

MySQL 部分重点知识篇

一、数据库对象 1. 主键 定义 &#xff1a;主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 &#xff1a;确保数据的完整性&#xff0c;便于数据的查询和管理。 示例 &#xff1a;在学生信息表中&#xff0c;学号可以作为主键&#xff…...