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

省份数量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] 解答思路 最初想到的是广度优先遍历&#xff0c;当某个城市不属于省份&#xff0c;需要从该城市开始&#xff0c;根据isConne…...

Android Native内存泄漏检测方案详解

文章目录 1. AddressSanitizer (ASan)2. LeakSanitizer (LSan)3. Valgrind4. 手动检测5. 实践建议6. 总结 在Android Native层开发过程中&#xff0c;内存泄漏是一个常见的问题。内存泄漏不仅会导致应用程序占用越来越多的内存&#xff0c;还可能引发性能问题和崩溃。因此&…...

有限单元法-编程与软件应用(崔济东、沈雪龙)【PDF下载】

专栏导读 作者简介&#xff1a;工学博士&#xff0c;高级工程师&#xff0c;专注于工业软件算法研究本文已收录于专栏&#xff1a;《有限元编程从入门到精通》本专栏旨在提供 1.以案例的形式讲解各类有限元问题的程序实现&#xff0c;并提供所有案例完整源码&#xff1b;2.单元…...

蓝桥杯练习系统(算法训练)ALGO-950 逆序数奇偶

资源限制 内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s 问题描述 老虎moreD是一个勤于思考的青年&#xff0c;线性代数行列式时&#xff0c;其定义中提到了逆序数这一概念。不过众所周知我们…...

uniapp踩坑 uni.showToast 和 uni.showLoading

uniapp踩坑 uni.showToast 和 uni.showLoading 一、问题描述 uni.showLoading 和 uni.showToast 混合使用时&#xff0c;showLoading和showToast会相互覆盖对方&#xff0c;调用hideLoading时也会将toast内容进行隐藏。 二、触发条件 1.uniapp中使用自己封装的axois&#x…...

BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU、TCN-BIGRU-ATTENTION合集

&#xff08;BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU、TCN-BIGRU-ATTENTION&#xff09;时&#xff0c;我们可以从它们的基本结构、工作原理、应用场景以及优缺点等方面进行详细介绍和分析。 BIGRU、CNN-BIGRU、CNN-BIGRU-ATTENTION、TCN-BIGRU等&#xff08;matlab…...

通过 Java 操作 redis -- 基本通用命令

目录 使用 String 类型的 get 和 set 方法 使用通用命令 exists &#xff0c;del 使用通用命令 keys 使用通用命令 expire,ttl 使用通用命令 type 要想通过 Java 操作 redis&#xff0c;首先要连接上 redis 服务器&#xff0c;推荐看通过 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…...

个股期权是什么期权?个股期权什么时候推出?

今天期权懂带你了解个股期权是什么期权&#xff1f;个股期权什么时候推出&#xff1f;期权也称选择权&#xff0c;是指期权的买方有权在约定的期限内&#xff0c;按照事先确定的价格&#xff0c;买入或卖出一定数量某种特定商品或金融指标的权利。 个股期权是什么期权&#xff…...

TCP UDP

传输层 端口号 tcp udp 网络层 IP地址 IP TCP&#xff0c;UDP 1&#xff0c;TCP是面向链接的协议&#xff0c;而UDP是无连接的协议; 2&#xff0c;TCP协议的传输是可靠的&#xff0c;而UDP协议的传输“尽力而为” 3&#xff0c;TCP可以实现流控&#xff0c;但UDP不行;…...

PCIE协议-1

1. PCIe结构拓扑 一个结构由点对点的链路组成&#xff0c;这些链路将一组组件互相连接 - 图1-2展示了一个结构拓扑示例。该图展示了一个称为层级结构的单一结构实例&#xff0c;由一个根复合体&#xff08;Root Complex, RC&#xff09;、多个端点&#xff08;I/O设备&#xf…...

[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含…...

海洋行业工业气体检测传感器的重要性

海洋行业是一个广阔而复杂的领域&#xff0c;涉及多个分支和应用&#xff0c;包括浮式生产、储存和卸载&#xff08;FPSO&#xff09;装置、渡轮和潜艇等。这些船舶和设施在执行任务时&#xff0c;都可能遇到各种潜在的气体危害。因此&#xff0c;对于海洋行业来说&#xff0c;…...

免费在线录屏、无需注册、免费可用、无限制

免费在线工具 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&#xff0c;一款性能卓越的DC-DC转换器&#xff0c;采用了集成10A、26mΩ功率的MOSFET电源开关转换器。它能够输出高达12V的电压&#xff0c;稳定可靠。这款产品以固定的600KHz运行&#xff0c;因此可以使用小型的外部感应器和电容器&#xff0…...

Java中枚举类的使用详解

Java中枚举类的使用详解 在Java编程中&#xff0c;枚举&#xff08;Enum&#xff09;是一种特殊的类&#xff0c;用于表示固定数量的常量。与常量相比&#xff0c;枚举类型具有类型安全、可读性强和易于管理的优点。下面我们将详细讲解Java中枚举类的使用&#xff0c;并通过示…...

C++11 设计模式6. 建造者模式,也叫做生成器模式

一 什么是建造者模式&#xff1f; // 小木公司对于SQL有配置&#xff0c;因此要输入sql url&#xff0c;然后输入 sql username&#xff0c;然后是 sql ps //因此小木就想到了使用 SystemConfig这个类来完成上述的三个初始化 //5.1号小木公司加入了redis的缓存机制&#xff0…...

GPS与精致农业 无人机应用 农业遥感 农业类

全球定位系统是美国国防部主要为满足军事部门对海上、陆地和空中设施进行高精度导航和定位的要求而建立的。GPS系统最基本的特点是以“多星、高轨、高频、测量-测距”为体制&#xff0c;以高精度的原子钟为核心。GPS作为新一代卫星导航与定位系统&#xff0c;不仅具有全球性、全…...

Kotlin注解简介

Kotlin注解 注解&#xff08;Annotations&#xff09;在 Kotlin 中和在 Java 中有类似的地位&#xff0c;它们都是元数据的形式&#xff0c;为代码提供了额外的信息。注解不会直接影响代码的操作&#xff0c;但可以被编译器或者运行时环境用来生成额外的代码、进行类型检查、处…...

代码随想录训练营

Day45代码随想录 322.零钱兑换 1.题目描述 给你一个整数数组 coins &#xff0c;表示不同面额的硬币&#xff1b;以及一个整数 amount &#xff0c;表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额&#xff0c;返回 -…...

Qt 5.14.2下MQTT开发全攻略:从源码编译到实战应用(附完整代码)

Qt 5.14.2下MQTT开发全流程实战指南 在物联网应用开发中&#xff0c;MQTT协议因其轻量级和高效性成为设备通信的首选方案。对于使用Qt框架的开发者而言&#xff0c;将MQTT集成到项目中可以构建出功能强大的跨平台物联网应用。本文将深入探讨在Windows平台上使用Qt 5.14.2进行MQ…...

弦音墨影保姆级教程:解决‘视频加载失败’‘墨迹不跟随目标’等10类高频问题

弦音墨影保姆级教程&#xff1a;解决‘视频加载失败’‘墨迹不跟随目标’等10类高频问题 1. 系统简介与核心价值 「弦音墨影」是一款将人工智能技术与传统美学完美融合的视频分析工具。它采用水墨丹青的视觉风格&#xff0c;通过先进的Qwen2.5-VL多模态技术&#xff0c;让视频…...

零基础实战:揭秘Python漫画下载器高效收藏完整指南

零基础实战&#xff1a;揭秘Python漫画下载器高效收藏完整指南 【免费下载链接】copymanga-downloader 使用python编译exe/bash/命令行参数来下载copymanga(拷贝漫画)中的漫画&#xff0c;支持批量选话下载和获取您收藏的漫画并下载&#xff01;(windows&linux支持&#xf…...

CMake实战:用ExternalProject_Add一键集成第三方库(附spdlog完整配置)

CMake实战&#xff1a;用ExternalProject_Add一键集成第三方库&#xff08;附spdlog完整配置&#xff09; 在C项目开发中&#xff0c;第三方库的集成往往是最耗时的环节之一。传统的手动下载、编译、配置头文件路径和链接库文件的方式&#xff0c;不仅效率低下&#xff0c;还会…...

深度解析Cassandra:分布式数据库的王者之路

深度解析Cassandra&#xff1a;分布式数据库的王者之路一篇让你彻底搞懂Cassandra的适用场景、优势劣势与应用实践前言 在大数据时代&#xff0c;传统的关系型数据库已经无法满足所有场景的需求。随着互联网应用的爆发式增长&#xff0c;高可用性、线性扩展、海量数据存储成为了…...

AI模型下载加速实战指南:突破ComfyUI大文件传输瓶颈

AI模型下载加速实战指南&#xff1a;突破ComfyUI大文件传输瓶颈 【免费下载链接】ComfyUI-Manager 项目地址: https://gitcode.com/gh_mirrors/co/ComfyUI-Manager 在AI模型训练与部署流程中&#xff0c;模型文件的高效获取常常成为制约工作流效率的关键环节。当面对动…...

别再死记硬背了!一张图帮你理清FS、FT、DTFT、DFS、DFT的来龙去脉

信号处理核心概念可视化指南&#xff1a;从傅里叶级数到离散傅里叶变换的认知地图 当信号处理初学者第一次面对FS、FT、DTFT、DFS、DFT这一系列缩写时&#xff0c;往往会陷入概念迷宫。这些名词背后隐藏着时域与频域、连续与离散、周期与非周期三组关键维度的复杂组合。本文将用…...

收藏!程序员转型AI大模型应用开发,必学四大核心技能(小白友好版)

当下AI大模型风口持续爆发&#xff0c;越来越多程序员想抓住机遇转型入局&#xff0c;但大多陷入“盲目跟风、无从下手、学了没用”的困境——其实&#xff0c;转型AI大模型应用开发无需急于求成&#xff0c;不用追求“面面俱到”&#xff0c;先吃透核心技能&#xff0c;搭建完…...

Qt 实时数据可视化工程实践:环形缓冲区实践

目录 前言 一、架构设计 1.1 分层架构图 1.2 数据写入流 1.3 数据刷新流 (定时器驱动 → 视图更新) 1.4 核心设计思想 二、核心实现详解 2.1 RingBuffer&#xff1a;环形缓冲区实现 2.1.1 append函数&#xff08;线程安全写入&#xff09; 函数主体实现&#xff1a; …...

简单认识了解MSE

了解MSE 的应用场景在传统的网页开发中&#xff0c;前端处理视频的方式非常被动&#xff1a;给 video标签指定一个src&#xff0c;剩下的下载、缓冲、解码工作完全由浏览器底层“黑盒”接管&#xff0c;开发者几乎无法干预。MSE&#xff08;Media Source Extensions&#xff0c…...