省份数量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 ,表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额,返回 -…...
WAN2.2文生视频效果实测对比:不同SDXL风格对动态连贯性的影响分析
WAN2.2文生视频效果实测对比:不同SDXL风格对动态连贯性的影响分析 最近在玩WAN2.2文生视频模型时,我发现一个挺有意思的现象:虽然模型本身很强大,但生成的视频效果好不好,很大程度上取决于你选的“风格”。WAN2.2集成…...
从‘双注意力网络’到MANet:手把手拆解CVPR经典模块在遥感分割中的魔改与应用
从双注意力机制到遥感图像分割:MANet的模块化设计与实战解析 遥感图像分割一直是计算机视觉领域的特殊挑战——当无人机以不同高度和角度拍摄地表时,同一张图像中可能同时存在微小的车辆和庞大的工业园区,这种极端的尺度变化让传统分割网络束…...
4个关键步骤:用vscode-ai-toolkit实现智能应用开发全流程
4个关键步骤:用vscode-ai-toolkit实现智能应用开发全流程 【免费下载链接】vscode-ai-toolkit 项目地址: https://gitcode.com/GitHub_Trending/vs/vscode-ai-toolkit AI Toolkit for Visual Studio Code是一款专为简化生成式AI应用开发设计的强大VS Code扩…...
Winhance:重塑Windows体验的系统优化与个性化解决方案
Winhance:重塑Windows体验的系统优化与个性化解决方案 【免费下载链接】Winhance-zh_CN A Chinese version of Winhance. PowerShell GUI application designed to optimize and customize your Windows experience. 项目地址: https://gitcode.com/gh_mirrors/wi…...
别再手动推导了!用Sophus库5分钟搞定机器人SLAM中的位姿插值与扰动更新
别再手动推导了!用Sophus库5分钟搞定机器人SLAM中的位姿插值与扰动更新 在机器人SLAM开发中,你是否曾为手动推导旋转矩阵的插值公式而抓狂?是否在实现位姿扰动更新时被四元数微分弄得晕头转向?今天,我们将用Sophus库彻…...
保姆级教程:用C语言数组扫描法,搞定智能车摄像头识别赛道‘L型’拐点
智能车竞赛实战:C语言数组扫描法精准识别L型赛道拐点 在智能车竞赛的赛道上,L型拐点往往是让许多参赛队伍"翻车"的关键节点。传统横向巡线算法在这里容易丢失赛道边界,而基于纵向扫描的数组分析法却能像手术刀般精准定位特征点。本…...
Wave-U-Net:革新音频分离技术的端到端深度学习解决方案
Wave-U-Net:革新音频分离技术的端到端深度学习解决方案 【免费下载链接】Wave-U-Net Implementation of the Wave-U-Net for audio source separation 项目地址: https://gitcode.com/gh_mirrors/wa/Wave-U-Net 在数字音频处理领域,从混合音频中精…...
Splitting.js创意指南:让网页文字动起来的实用技巧
Splitting.js创意指南:让网页文字动起来的实用技巧 【免费下载链接】Splitting JavaScript microlibrary to split an element by words, characters, children and more, populated with CSS variables! 项目地址: https://gitcode.com/gh_mirrors/sp/Splitting …...
Python实战:用SymPy解常微分方程 vs 偏微分方程的5个关键差异
Python实战:用SymPy解常微分方程 vs 偏微分方程的5个关键差异 微分方程是数学建模的核心工具,而Python的SymPy库让符号计算变得触手可及。但当你真正在Jupyter Notebook中敲下dsolve()命令时,是否困惑过为什么有些方程秒出结果,有…...
别再为UVM环境发愁了!用路科V0虚拟机+《UVM实战》源码,10分钟搞定VCS/Verdi仿真
10分钟零配置玩转UVM验证:路科V0虚拟机《UVM实战》全攻略 当我在三年前第一次接触UVM验证时,花了整整三天时间在环境配置上——从EDA工具安装、环境变量配置到Makefile调试,每一步都踩过坑。直到发现路科V0预配置虚拟机这个"神器"&…...

