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

【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】第四十四题 省份数量

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 给我们一个二维数组&#xff0c;表示城市之间的连通情况&#xff0c;连在一起的城市为一个省份&#xff0c;问我们一共有多少个省份。 这…...

把DTC从Excel导入cdd的方法

本文是基于CANdelaStudio12.0讲解 问题一&#xff1a;当导入DTC的xxx.cdi文件报如下红色错误 可能原因&#xff1a;在设置具有下拉框的属性的内容时&#xff0c;输入的内容不在下拉框列表中 解决办法:在.cddt文件中更新“”Error Code Table“”内容&#xff0c;把新的选项更新…...

养猪废水处理设备的处理方法

诸城市鑫淼环保小编带大家了解一下养猪废水处理设备的处理方法 1.高有机负荷&#xff1a;猪粪尿含有大量有机物质&#xff0c;比如蛋白质、脂肪和淀粉等&#xff0c;这些有机物在水体中分解会消耗氧气&#xff0c;导致水体缺氧。 2.高氨氮含量&#xff1a;猪粪尿中的蛋白质分解…...

【React】React学习:从初级到高级(三)

3 状态管理 随着应用不断变大&#xff0c;应该更有意识的去关注应用状态如何组织&#xff0c;以及数据如何在组件之间流动。冗余或重复的状态往往是缺陷的根源。 3.1 用State响应输入 3.1.1 声明式地考虑UI 总体步骤如下&#xff1a; 定位组件中不同的视图状态 确定是什么…...

Rest和Http什么关系?

分析&回答 REST 定义了一组体系架构原则&#xff0c;您可以根据这些&#xff0c;包括使用不同语言编写的客户端如何通过 HTTP 处理和传输资源状态。 REST只是一种风格&#xff0c;不是一种标准REST是以资源为中心的 用不同的 HTTP 请求方法来处理对资源的 CRUD&#xff0…...

leetcode原题: 生存人数

题目&#xff1a; 给定 N 个人的出生年份和死亡年份&#xff0c;第 i 个人的出生年份为 birth[i]&#xff0c;死亡年份为 death[i]&#xff0c;实现一个方法以计算生存人数最多的年份。 你可以假设所有人都出生于 1900 年至 2000 年&#xff08;含 1900 和 2000 &#xff09;…...

K8S的介绍和架构

仅供入门 K8S的介绍和架构 一. 什么是kubernetes二、Kubernetes架构和组件 2.1 核心组件 2.1.1 Kubernetes Master控制组件&#xff0c;调度管理整个系统&#xff08;集群&#xff09;&#xff0c;包含如下组件: a、Kubernetes API Serverb、Kubernetes Schedulerc、Kubernet…...

linux信号量

通过学习linux的信号量&#xff0c;对linux的信号量进行了编程。...

Jupyter Notebook 好用在哪?

Jupyter Notebook 是一个 Web 应用程序&#xff0c;便于创建和共享文学化程序文档&#xff0c;支持实时代码、数学方程、可视化和 Markdown&#xff0c;其用途包括数据清理和转换、数值模拟、统计建模、机器学习等等。目前&#xff0c;数据挖掘领域中最热门的比赛 Kaggle 里的资…...

华为云云服务器评测|基于云服务器的minio部署手册

华为云云服务器评测|基于云服务器的minio部署手册 【软件安装版本】【集群安装&#xff08;是&#xff09;&#xff08;否&#xff09;】 版本 创建人 修改人 创建时间 备注 1.0 jz jz 2023.9.2 minio华为云耀服务器 一. 部署规划与架构 1. 规…...

【网络安全带你练爬虫-100练】第22练:数据包中参数提取与处理

目录 一、目标1&#xff1a;GET数据包的处理 1、GET数据包中参数的提取 2、GET请求中 统计参数个数 二、目标2&#xff1a;POST数据包的处理 1、post中参数个数的提取 2、POST请求中 统计参数个数 一、目标1&#xff1a;GET数据包的处理 1、GET数据包中参数的提取 impo…...

第64步 深度学习图像识别:多分类建模误判病例分析(Pytorch)

基于WIN10的64位系统演示 一、写在前面 上期我们基于TensorFlow环境介绍了多分类建模的误判病例分析。 本期以健康组、肺结核组、COVID-19组、细菌性&#xff08;病毒性&#xff09;肺炎组为数据集&#xff0c;基于Pytorch环境&#xff0c;构建SqueezeNet多分类模型&#xf…...

ES查询报错内容长度超过104857600

项目场景&#xff1a; 使用 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日&#xff0c;以“合作、协同、共赢、共享”为主题的“2023欧亚合作发展大会暨国际公共采购大会等系列会议”在北京炎黄书院隆重举行&#xff0c;共有500多位中外贵宾参加了本次盛会。 本次大会指导单位是中国联合国采购促进会、北京市中医药局&#xff0c;由中…...

宝塔面板linux在终端使用命令开启服务保持服务不关闭

我们经常在宝塔面板终端开启服务&#xff08;比如socket等服务时&#xff09;&#xff0c;如果关闭面板标签页或者关闭终端&#xff0c;服务也随之关闭了&#xff0c;要保持服务一直运行&#xff0c;就需要把终端进程放在linux后台执行&#xff0c;方法如下&#xff1a; 1、先…...

面试题--从键盘输入网站到网页显示,之间发生了什么

文章目录 首先进入HTTP阶段协议栈阶段TCP阶段IP阶段MAC网卡交换机路由器抵达 首先进入HTTP阶段 1.解析对应的URL&#xff0c;访问一个对应的服务器xxx.com的一个文件index.html; 2 使用DNS查询对应的ip地址&#xff0c;通过DNS服务器进行查找 3 组装http报文&#xff0c;生成h…...

字节9.3秋招研发笔试 【后端方向】第三题

题目 小红拿到了一个无向图&#xff0c;初始每人节点是白色&#xff0c;其中有若干个节点被染成了红色。小红想知道&#xff0c;若将 i 号节点染成红色&#xff0c;当前的红色连块的数量是多少? 你需要回答i∈[1,n] 的答案。 定义&#xff0c;若干节点组成一个红色连通块&am…...

Solidity 小白教程:8. 变量初始值

Solidity 小白教程&#xff1a;8. 变量初始值 变量初始值 在solidity中&#xff0c;声明但没赋值的变量都有它的初始值或默认值。这一讲&#xff0c;我们将介绍常用变量的初始值。 值类型初始值 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链路演进 | 京东云技术团队

导读 搜索系统中容易存在头部效应&#xff0c;中长尾的优质商品较难获得充分的展示机会&#xff0c;如何破除系统的马太效应&#xff0c;提升展示结果的丰富性与多样性&#xff0c;助力中长尾商品成长是电商平台搜索系统的一个重要课题。其中&#xff0c;搜索EE系统在保持排序…...

python打卡day49

知识点回顾&#xff1a; 通道注意力模块复习空间注意力模块CBAM的定义 作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Qt Http Server模块功能及架构

Qt Http Server 是 Qt 6.0 中引入的一个新模块&#xff0c;它提供了一个轻量级的 HTTP 服务器实现&#xff0c;主要用于构建基于 HTTP 的应用程序和服务。 功能介绍&#xff1a; 主要功能 HTTP服务器功能&#xff1a; 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

LLM基础1_语言模型如何处理文本

基于GitHub项目&#xff1a;https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken&#xff1a;OpenAI开发的专业"分词器" torch&#xff1a;Facebook开发的强力计算引擎&#xff0c;相当于超级计算器 理解词嵌入&#xff1a;给词语画"…...

python执行测试用例,allure报乱码且未成功生成报告

allure执行测试用例时显示乱码&#xff1a;‘allure’ &#xfffd;&#xfffd;&#xfffd;&#xfffd;&#xfffd;ڲ&#xfffd;&#xfffd;&#xfffd;&#xfffd;ⲿ&#xfffd;&#xfffd;&#xfffd;Ҳ&#xfffd;&#xfffd;&#xfffd;ǿ&#xfffd;&am…...

论文笔记——相干体技术在裂缝预测中的应用研究

目录 相关地震知识补充地震数据的认识地震几何属性 相干体算法定义基本原理第一代相干体技术&#xff1a;基于互相关的相干体技术&#xff08;Correlation&#xff09;第二代相干体技术&#xff1a;基于相似的相干体技术&#xff08;Semblance&#xff09;基于多道相似的相干体…...

CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)

漏洞概览 漏洞名称&#xff1a;Apache Flink REST API 任意文件读取漏洞CVE编号&#xff1a;CVE-2020-17519CVSS评分&#xff1a;7.5影响版本&#xff1a;Apache Flink 1.11.0、1.11.1、1.11.2修复版本&#xff1a;≥ 1.11.3 或 ≥ 1.12.0漏洞类型&#xff1a;路径遍历&#x…...