【LeetCode75】第四十四题 省份数量
目录
题目:
示例:
分析:
代码:
题目:

示例:

分析:
给我们一个二维数组,表示城市之间的连通情况,连在一起的城市为一个省份,问我们一共有多少个省份。
这是一道很经典很纯粹的并查集题目。按照我自己的话来说,并查集就是给将相连的元素都设置一个共同的源头,在本题中,我们让相连的城市都有一个共同的源头,那么最后我们统计一下所有城市一共有多少个不同的源头即可确定是有多少个城市了。
这代码就是很标准的并查集模板,大家记住并且理解即可。
首先我们需要定义一个长度和城市数量一样的数组,用来存放每个城市的源头。
并且需要将每个城市的源头初始化成自己。
接着遍历城市之间的连通情况。如果城市之间是连通的,那么我们需要将他们联系在一起,即把他们的源头改成同一个。
首先是先找出他们各自的源头,再把其中一个的源头的源头改成对方的源头。其中找出各自源头这一步是不断寻找源头列表里对应位置,如果一个城市的源头不是自己,那么我们就接着找这个城市的源头的源头,直到找到源头是自己的城市,那么这座城市就是我们需要寻找的城市的最终源头。
这对应了代码中的find函数。
记录完所有城市的连通情况之后,我们再看看所有城市一共有几个最终源头,将最终源头的数量返回出去即可。
代码:
class Solution {
public:int find(int c,vector<int>& city){ //寻源if(c==city[c]) return c; //自己就是源头,直接返回city[c]=find(city[c],city); //接着往上寻找源头return city[c]; }void join(int i,int j,vector<int>& city){ //添加关系i=find(i,city);j=find(j,city);if(i==j) return; //如果源头一样returncity[i]=j; //源头不一样就添加为一样,这边改成city[j]=i也是可以的}int findCircleNum(vector<vector<int>>& isConnected) {vector<int>city(isConnected.size()); //用来记录每个城市的源头for(int i=0;i<isConnected.size();i++) city[i]=i; //初始化成每个城市都是自己的源头for(int i=0;i<isConnected.size();i++){for(int j=0;j<isConnected.size();j++){if(isConnected[i][j]==1) join(i,j,city); //如果城市间是相连的,则添加关系为源头一致}}//统计所有城市一共有多少个源头unordered_set<int>res;for(int& c:city){res.insert(find(c,city));}return res.size();}
};
相关文章:
【LeetCode75】第四十四题 省份数量
目录 题目: 示例: 分析: 代码: 题目: 示例: 分析: 给我们一个二维数组,表示城市之间的连通情况,连在一起的城市为一个省份,问我们一共有多少个省份。 这…...
把DTC从Excel导入cdd的方法
本文是基于CANdelaStudio12.0讲解 问题一:当导入DTC的xxx.cdi文件报如下红色错误 可能原因:在设置具有下拉框的属性的内容时,输入的内容不在下拉框列表中 解决办法:在.cddt文件中更新“”Error Code Table“”内容,把新的选项更新…...
养猪废水处理设备的处理方法
诸城市鑫淼环保小编带大家了解一下养猪废水处理设备的处理方法 1.高有机负荷:猪粪尿含有大量有机物质,比如蛋白质、脂肪和淀粉等,这些有机物在水体中分解会消耗氧气,导致水体缺氧。 2.高氨氮含量:猪粪尿中的蛋白质分解…...
【React】React学习:从初级到高级(三)
3 状态管理 随着应用不断变大,应该更有意识的去关注应用状态如何组织,以及数据如何在组件之间流动。冗余或重复的状态往往是缺陷的根源。 3.1 用State响应输入 3.1.1 声明式地考虑UI 总体步骤如下: 定位组件中不同的视图状态 确定是什么…...
Rest和Http什么关系?
分析&回答 REST 定义了一组体系架构原则,您可以根据这些,包括使用不同语言编写的客户端如何通过 HTTP 处理和传输资源状态。 REST只是一种风格,不是一种标准REST是以资源为中心的 用不同的 HTTP 请求方法来处理对资源的 CRUD࿰…...
leetcode原题: 生存人数
题目: 给定 N 个人的出生年份和死亡年份,第 i 个人的出生年份为 birth[i],死亡年份为 death[i],实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年(含 1900 和 2000 )…...
K8S的介绍和架构
仅供入门 K8S的介绍和架构 一. 什么是kubernetes二、Kubernetes架构和组件 2.1 核心组件 2.1.1 Kubernetes Master控制组件,调度管理整个系统(集群),包含如下组件: a、Kubernetes API Serverb、Kubernetes Schedulerc、Kubernet…...
linux信号量
通过学习linux的信号量,对linux的信号量进行了编程。...
Jupyter Notebook 好用在哪?
Jupyter Notebook 是一个 Web 应用程序,便于创建和共享文学化程序文档,支持实时代码、数学方程、可视化和 Markdown,其用途包括数据清理和转换、数值模拟、统计建模、机器学习等等。目前,数据挖掘领域中最热门的比赛 Kaggle 里的资…...
华为云云服务器评测|基于云服务器的minio部署手册
华为云云服务器评测|基于云服务器的minio部署手册 【软件安装版本】【集群安装(是)(否)】 版本 创建人 修改人 创建时间 备注 1.0 jz jz 2023.9.2 minio华为云耀服务器 一. 部署规划与架构 1. 规…...
【网络安全带你练爬虫-100练】第22练:数据包中参数提取与处理
目录 一、目标1:GET数据包的处理 1、GET数据包中参数的提取 2、GET请求中 统计参数个数 二、目标2:POST数据包的处理 1、post中参数个数的提取 2、POST请求中 统计参数个数 一、目标1:GET数据包的处理 1、GET数据包中参数的提取 impo…...
第64步 深度学习图像识别:多分类建模误判病例分析(Pytorch)
基于WIN10的64位系统演示 一、写在前面 上期我们基于TensorFlow环境介绍了多分类建模的误判病例分析。 本期以健康组、肺结核组、COVID-19组、细菌性(病毒性)肺炎组为数据集,基于Pytorch环境,构建SqueezeNet多分类模型…...
ES查询报错内容长度超过104857600
项目场景: 使用 ElasticsearchRestTemplate 或者使用 RestHighLevelClient 查询 ES 报错 内容长度超过 104857600 问题描述 ES 查询报错 entiity content is too long xxx for the configured buffer limit 104857600 Overridepublic void esQuery() {restHighL…...
2023欧亚合作发展大会暨国际公共采购大会在京举行
2023年9月2日至6日,以“合作、协同、共赢、共享”为主题的“2023欧亚合作发展大会暨国际公共采购大会等系列会议”在北京炎黄书院隆重举行,共有500多位中外贵宾参加了本次盛会。 本次大会指导单位是中国联合国采购促进会、北京市中医药局,由中…...
宝塔面板linux在终端使用命令开启服务保持服务不关闭
我们经常在宝塔面板终端开启服务(比如socket等服务时),如果关闭面板标签页或者关闭终端,服务也随之关闭了,要保持服务一直运行,就需要把终端进程放在linux后台执行,方法如下: 1、先…...
面试题--从键盘输入网站到网页显示,之间发生了什么
文章目录 首先进入HTTP阶段协议栈阶段TCP阶段IP阶段MAC网卡交换机路由器抵达 首先进入HTTP阶段 1.解析对应的URL,访问一个对应的服务器xxx.com的一个文件index.html; 2 使用DNS查询对应的ip地址,通过DNS服务器进行查找 3 组装http报文,生成h…...
字节9.3秋招研发笔试 【后端方向】第三题
题目 小红拿到了一个无向图,初始每人节点是白色,其中有若干个节点被染成了红色。小红想知道,若将 i 号节点染成红色,当前的红色连块的数量是多少? 你需要回答i∈[1,n] 的答案。 定义,若干节点组成一个红色连通块&am…...
Solidity 小白教程:8. 变量初始值
Solidity 小白教程:8. 变量初始值 变量初始值 在solidity中,声明但没赋值的变量都有它的初始值或默认值。这一讲,我们将介绍常用变量的初始值。 值类型初始值 boolean: falsestring: “”int: 0uint: 0enum: 枚举中的第一个元素address: …...
时序预测 | MATLAB实现EEMD-SSA-LSTM、EEMD-LSTM、SSA-LSTM、LSTM时间序列预测对比
时序预测 | MATLAB实现EEMD-SSA-LSTM、EEMD-LSTM、SSA-LSTM、LSTM时间序列预测对比 目录 时序预测 | MATLAB实现EEMD-SSA-LSTM、EEMD-LSTM、SSA-LSTM、LSTM时间序列预测对比预测效果基本介绍模型描述程序设计参考资料 预测效果 基本介绍 时序预测 | MATLAB实现EEMD-SSA-LSTM、E…...
京东搜索EE链路演进 | 京东云技术团队
导读 搜索系统中容易存在头部效应,中长尾的优质商品较难获得充分的展示机会,如何破除系统的马太效应,提升展示结果的丰富性与多样性,助力中长尾商品成长是电商平台搜索系统的一个重要课题。其中,搜索EE系统在保持排序…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
C# 类和继承(抽象类)
抽象类 抽象类是指设计为被继承的类。抽象类只能被用作其他类的基类。 不能创建抽象类的实例。抽象类使用abstract修饰符声明。 抽象类可以包含抽象成员或普通的非抽象成员。抽象类的成员可以是抽象成员和普通带 实现的成员的任意组合。抽象类自己可以派生自另一个抽象类。例…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
Mysql8 忘记密码重置,以及问题解决
1.使用免密登录 找到配置MySQL文件,我的文件路径是/etc/mysql/my.cnf,有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...
代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...
使用SSE解决获取状态不一致问题
使用SSE解决获取状态不一致问题 1. 问题描述2. SSE介绍2.1 SSE 的工作原理2.2 SSE 的事件格式规范2.3 SSE与其他技术对比2.4 SSE 的优缺点 3. 实战代码 1. 问题描述 目前做的一个功能是上传多个文件,这个上传文件是整体功能的一部分,文件在上传的过程中…...
sshd代码修改banner
sshd服务连接之后会收到字符串: SSH-2.0-OpenSSH_9.5 容易被hacker识别此服务为sshd服务。 是否可以通过修改此banner达到让人无法识别此服务的目的呢? 不能。因为这是写的SSH的协议中的。 也就是协议规定了banner必须这么写。 SSH- 开头,…...
