当前位置: 首页 > 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;返回 -…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容

基于 ​UniApp + WebSocket​实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配​微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

c++ 面试题(1)-----深度优先搜索(DFS)实现

操作系统&#xff1a;ubuntu22.04 IDE:Visual Studio Code 编程语言&#xff1a;C11 题目描述 地上有一个 m 行 n 列的方格&#xff0c;从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子&#xff0c;但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

安宝特方案丨船舶智造的“AR+AI+作业标准化管理解决方案”(装配)

船舶制造装配管理现状&#xff1a;装配工作依赖人工经验&#xff0c;装配工人凭借长期实践积累的操作技巧完成零部件组装。企业通常制定了装配作业指导书&#xff0c;但在实际执行中&#xff0c;工人对指导书的理解和遵循程度参差不齐。 船舶装配过程中的挑战与需求 挑战 (1…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

tomcat指定使用的jdk版本

说明 有时候需要对tomcat配置指定的jdk版本号&#xff0c;此时&#xff0c;我们可以通过以下方式进行配置 设置方式 找到tomcat的bin目录中的setclasspath.bat。如果是linux系统则是setclasspath.sh set JAVA_HOMEC:\Program Files\Java\jdk8 set JRE_HOMEC:\Program Files…...

Kubernetes 网络模型深度解析:Pod IP 与 Service 的负载均衡机制,Service到底是什么?

Pod IP 的本质与特性 Pod IP 的定位 纯端点地址&#xff1a;Pod IP 是分配给 Pod 网络命名空间的真实 IP 地址&#xff08;如 10.244.1.2&#xff09;无特殊名称&#xff1a;在 Kubernetes 中&#xff0c;它通常被称为 “Pod IP” 或 “容器 IP”生命周期&#xff1a;与 Pod …...