省份数量00
题目链接
省份数量
题目描述
注意点
- 1 <= n <= 200
- isConnected[i][j] 为 1 或 0
- isConnected[i][i] == 1
- isConnected[i][j] == isConnected[j][i]
解答思路
- 最初想到的是广度优先遍历,当某个城市不属于省份,需要从该城市开始,根据isConnected找到所有与其相连的城市,即可得到省份中有哪些城市,保存城市所属省份的信息,遍历完全部城市以后,即可得到连通分量的总数,即省份的总数
- 另一个方法就是深度优先遍历找到相连的城市,找到一个属于新的省份的城市后,找到与之相连的城市,再根据相连的城市找到与相连城市相连的城市…找到省份中所有的城市。遍历完全部城市,找到所有省份
代码
方法一:
class Solution {public int findCircleNum(int[][] isConnected) {int res = 0;int n = isConnected.length;int[] province = new int[n];Deque<Integer> deque = new ArrayDeque<>();for (int i = 0; i < n; i++) {// 该城市已经属于某个省份if (province[i] != 0) {continue;}res++;deque.offerLast(i);// 找到与i相连的所有城市while (!deque.isEmpty()) {int row = deque.pollFirst();for (int j = 0; j < n; j++) {if (isConnected[row][j] == 1 && province[j] == 0) {province[j] = res;deque.offerLast(j);}}}}return res;}
}
方法二:
class Solution {public int findCircleNum(int[][] isConnected) {int res = 0;int n = isConnected.length;int[] province = new int[n];for (int i = 0; i < n; i++) {// 该城市已属于某个省份if (province[i] != 0) {continue;}res++;// 深度优先遍历找到属于该省份的城市dfs(isConnected, province, i);}return res;}public void dfs(int[][] isConnected, int[] province, int i) {if (province[i] != 0) {return;}province[i] = 1;for (int j = 0; j < province.length; j++) {if (isConnected[i][j] == 1) {dfs(isConnected, province, j);}}}
}
关键点
- 深度优先遍历的思想
- 广度优先遍历的思想
- 需要保存城市属于某个省份的信息
相关文章:
省份数量00
题目链接 省份数量 题目描述 注意点 1 < n < 200isConnected[i][j] 为 1 或 0isConnected[i][i] 1isConnected[i][j] isConnected[j][i] 解答思路 最初想到的是广度优先遍历,当某个城市不属于省份,需要从该城市开始,根据isConne…...
Android Native内存泄漏检测方案详解
文章目录 1. AddressSanitizer (ASan)2. LeakSanitizer (LSan)3. Valgrind4. 手动检测5. 实践建议6. 总结 在Android Native层开发过程中,内存泄漏是一个常见的问题。内存泄漏不仅会导致应用程序占用越来越多的内存,还可能引发性能问题和崩溃。因此&…...
有限单元法-编程与软件应用(崔济东、沈雪龙)【PDF下载】
专栏导读 作者简介:工学博士,高级工程师,专注于工业软件算法研究本文已收录于专栏:《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现,并提供所有案例完整源码;2.单元…...
蓝桥杯练习系统(算法训练)ALGO-950 逆序数奇偶
资源限制 内存限制:256.0MB C/C时间限制:1.0s Java时间限制:3.0s Python时间限制:5.0s 问题描述 老虎moreD是一个勤于思考的青年,线性代数行列式时,其定义中提到了逆序数这一概念。不过众所周知我们…...
uniapp踩坑 uni.showToast 和 uni.showLoading
uniapp踩坑 uni.showToast 和 uni.showLoading 一、问题描述 uni.showLoading 和 uni.showToast 混合使用时,showLoading和showToast会相互覆盖对方,调用hideLoading时也会将toast内容进行隐藏。 二、触发条件 1.uniapp中使用自己封装的axois&#x…...
BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU、TCN-BIGRU-ATTENTION合集
(BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU、TCN-BIGRU-ATTENTION)时,我们可以从它们的基本结构、工作原理、应用场景以及优缺点等方面进行详细介绍和分析。 BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU等(matlab…...
通过 Java 操作 redis -- 基本通用命令
目录 使用 String 类型的 get 和 set 方法 使用通用命令 exists ,del 使用通用命令 keys 使用通用命令 expire,ttl 使用通用命令 type 要想通过 Java 操作 redis,首先要连接上 redis 服务器,推荐看通过 Java 操作 redis -- 连接 redis 关…...
Jenkins集成Kubernetes 部署springboot项目
文章目录 准备部署的yml文件Harbor私服配置测试使用效果Jenkins远程调用参考文章 准备部署的yml文件 apiVersion: apps/v1 kind: Deployment metadata:namespace: testname: pipelinelabels:app: pipeline spec:replicas: 2selector:matchLabels:app: pipelinetemplate:metada…...
个股期权是什么期权?个股期权什么时候推出?
今天期权懂带你了解个股期权是什么期权?个股期权什么时候推出?期权也称选择权,是指期权的买方有权在约定的期限内,按照事先确定的价格,买入或卖出一定数量某种特定商品或金融指标的权利。 个股期权是什么期权ÿ…...
TCP UDP
传输层 端口号 tcp udp 网络层 IP地址 IP TCP,UDP 1,TCP是面向链接的协议,而UDP是无连接的协议; 2,TCP协议的传输是可靠的,而UDP协议的传输“尽力而为” 3,TCP可以实现流控,但UDP不行;…...
PCIE协议-1
1. PCIe结构拓扑 一个结构由点对点的链路组成,这些链路将一组组件互相连接 - 图1-2展示了一个结构拓扑示例。该图展示了一个称为层级结构的单一结构实例,由一个根复合体(Root Complex, RC)、多个端点(I/O设备…...
[C++][PCL]pcl安装包预编译包国内源下载地址
版本名称下载地址PCL-1.14.1-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.14.0-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.13.1-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.13.0-AllInOne-msvc2022-win64含pdb.zip点我下载PCL-1.12.1-AllInOne-msvc2019-win64含…...
海洋行业工业气体检测传感器的重要性
海洋行业是一个广阔而复杂的领域,涉及多个分支和应用,包括浮式生产、储存和卸载(FPSO)装置、渡轮和潜艇等。这些船舶和设施在执行任务时,都可能遇到各种潜在的气体危害。因此,对于海洋行业来说,…...
免费在线录屏、无需注册、免费可用、无限制
免费在线工具 https://orcc.online/ 在线录屏 https://orcc.online/recorder pdf在线免费转word文档 https://orcc.online/pdf 时间戳转换 https://orcc.online/timestamp Base64 编码解码 https://orcc.online/base64 URL 编码解码 https://orcc.online/url Hash(MD5/SHA…...
5V升9V2A升压恒压WT3231
5V升9V2A升压恒压WT3231 WT3231,一款性能卓越的DC-DC转换器,采用了集成10A、26mΩ功率的MOSFET电源开关转换器。它能够输出高达12V的电压,稳定可靠。这款产品以固定的600KHz运行,因此可以使用小型的外部感应器和电容器࿰…...
Java中枚举类的使用详解
Java中枚举类的使用详解 在Java编程中,枚举(Enum)是一种特殊的类,用于表示固定数量的常量。与常量相比,枚举类型具有类型安全、可读性强和易于管理的优点。下面我们将详细讲解Java中枚举类的使用,并通过示…...
C++11 设计模式6. 建造者模式,也叫做生成器模式
一 什么是建造者模式? // 小木公司对于SQL有配置,因此要输入sql url,然后输入 sql username,然后是 sql ps //因此小木就想到了使用 SystemConfig这个类来完成上述的三个初始化 //5.1号小木公司加入了redis的缓存机制࿰…...
GPS与精致农业 无人机应用 农业遥感 农业类
全球定位系统是美国国防部主要为满足军事部门对海上、陆地和空中设施进行高精度导航和定位的要求而建立的。GPS系统最基本的特点是以“多星、高轨、高频、测量-测距”为体制,以高精度的原子钟为核心。GPS作为新一代卫星导航与定位系统,不仅具有全球性、全…...
Kotlin注解简介
Kotlin注解 注解(Annotations)在 Kotlin 中和在 Java 中有类似的地位,它们都是元数据的形式,为代码提供了额外的信息。注解不会直接影响代码的操作,但可以被编译器或者运行时环境用来生成额外的代码、进行类型检查、处…...
代码随想录训练营
Day45代码随想录 322.零钱兑换 1.题目描述 给你一个整数数组 coins ,表示不同面额的硬币;以及一个整数 amount ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -…...
接口测试中缓存处理策略
在接口测试中,缓存处理策略是一个关键环节,直接影响测试结果的准确性和可靠性。合理的缓存处理策略能够确保测试环境的一致性,避免因缓存数据导致的测试偏差。以下是接口测试中常见的缓存处理策略及其详细说明: 一、缓存处理的核…...
从深圳崛起的“机器之眼”:赴港乐动机器人的万亿赛道赶考路
进入2025年以来,尽管围绕人形机器人、具身智能等机器人赛道的质疑声不断,但全球市场热度依然高涨,入局者持续增加。 以国内市场为例,天眼查专业版数据显示,截至5月底,我国现存在业、存续状态的机器人相关企…...
Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...
ServerTrust 并非唯一
NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
华硕a豆14 Air香氛版,美学与科技的馨香融合
在快节奏的现代生活中,我们渴望一个能激发创想、愉悦感官的工作与生活伙伴,它不仅是冰冷的科技工具,更能触动我们内心深处的细腻情感。正是在这样的期许下,华硕a豆14 Air香氛版翩然而至,它以一种前所未有的方式&#x…...
用机器学习破解新能源领域的“弃风”难题
音乐发烧友深有体会,玩音乐的本质就是玩电网。火电声音偏暖,水电偏冷,风电偏空旷。至于太阳能发的电,则略显朦胧和单薄。 不知你是否有感觉,近两年家里的音响声音越来越冷,听起来越来越单薄? —…...
AGain DB和倍数增益的关系
我在设置一款索尼CMOS芯片时,Again增益0db变化为6DB,画面的变化只有2倍DN的增益,比如10变为20。 这与dB和线性增益的关系以及传感器处理流程有关。以下是具体原因分析: 1. dB与线性增益的换算关系 6dB对应的理论线性增益应为&…...
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.登…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...

