当前位置: 首页 > 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;不可重连&…...

Windows资源管理器终极美化指南:一键添加惊艳毛玻璃效果

Windows资源管理器终极美化指南&#xff1a;一键添加惊艳毛玻璃效果 【免费下载链接】ExplorerBlurMica Add background Blur effect or Acrylic (Mica for win11) effect to explorer for win10 and win11 项目地址: https://gitcode.com/gh_mirrors/ex/ExplorerBlurMica …...

如何用ChatALL实现AI智能协同:一次提问,多模型对比的解决方案

如何用ChatALL实现AI智能协同&#xff1a;一次提问&#xff0c;多模型对比的解决方案 【免费下载链接】ChatALL Concurrently chat with ChatGPT, Bing Chat, Bard, Alpaca, Vicuna, Claude, ChatGLM, MOSS, 讯飞星火, 文心一言 and more, discover the best answers 项目地…...

FastJson内存泄漏实战:我是如何用MAT工具定位到IdentityHashMap这个坑的

FastJson内存泄漏深度剖析&#xff1a;从MAT工具实战到IdentityHashMap陷阱破解 凌晨三点&#xff0c;手机突然响起刺耳的告警声——生产环境某核心服务的堆内存使用率突破95%。作为值班工程师&#xff0c;我瞬间清醒过来。这不是普通的OOM&#xff0c;而是一场持续增长的内存…...

JAVA重点基础、进阶知识及易错点总结(1)---数据类型、运算符、流程控制

&#x1f680; Java 巩固进阶 第1天 主题&#xff1a;数据类型、运算符与流程控制 —— 避开那些“隐形”的坑&#x1f4c5; 进度概览&#xff1a;重启Java基础。 &#x1f4a1; 核心价值&#xff1a;很多生产环境的Bug&#xff08;如金额精度丢失、空指针崩溃、逻辑穿透&…...

语音转换完全上手:Retrieval-based Voice-Conversion-WebUI从入门到精通

语音转换完全上手&#xff1a;Retrieval-based Voice-Conversion-WebUI从入门到精通 【免费下载链接】Retrieval-based-Voice-Conversion-WebUI 语音数据小于等于10分钟也可以用来训练一个优秀的变声模型&#xff01; 项目地址: https://gitcode.com/GitHub_Trending/re/Retr…...

浏览器兼容性问题汇总

1.IE10版本以上浏览器input标签后面自带一个X问题IE10&#xff0c;IE11浏览器当点击input text文本框时&#xff0c;输入文本后出现一个删除功能的X按钮IE浏览器效果&#xff0c;而谷歌浏览器没有解决方案&#xff1a;给input添加如下CSS样式 input::-ms-clear{display:none;}2…...

三步打造沉浸式AI对话体验:SillyTavern终极指南

三步打造沉浸式AI对话体验&#xff1a;SillyTavern终极指南 【免费下载链接】SillyTavern LLM Frontend for Power Users. 项目地址: https://gitcode.com/GitHub_Trending/si/SillyTavern 你是否厌倦了单调的文字聊天&#xff1f;想让AI助手不仅能"说"&#…...

OpenClaw性能优化:GLM-4.7-Flash长任务链的Token节省技巧

OpenClaw性能优化&#xff1a;GLM-4.7-Flash长任务链的Token节省技巧 1. 问题背景&#xff1a;长任务链的Token消耗困境 上周我尝试用OpenClaw自动化处理一个典型的办公场景&#xff1a;从200页PDF中提取关键数据&#xff0c;整理成Excel表格后发送邮件。整个流程涉及PDF解析…...

B2B品牌战略方法拆解:客户层、业务层、价值层、证据层怎么串起来

一个有点反常识的判断是&#xff1a;真正拉开差距的&#xff0c;常常不是你有多少材料、多少动作、多少名字&#xff0c;而是你能不能先把最关键的判断结构做出来。B2B品牌战略一旦结构对了&#xff0c;后面的内容、渠道和场景才会越做越顺。B2B品牌战略是什么&#xff1a;围绕…...

GLM-OCR在ComfyUI工作流中的应用:构建可视化OCR处理节点

GLM-OCR在ComfyUI工作流中的应用&#xff1a;构建可视化OCR处理节点 如果你经常用ComfyUI做图片生成或者编辑&#xff0c;可能会遇到一个挺麻烦的事儿&#xff1a;怎么把图片里的文字快速提取出来&#xff0c;然后用到下一步工作流里&#xff1f;比如&#xff0c;你想把一张海…...