华为OD机考算法题:服务器广播
题目部分
题目 | 服务器广播 |
难度 | 难 |
题目说明 | 服务器连接方式包括直接相连,间接连接。A 和 B 直接连接,B 和 C 直接连接,则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。 给出一个 N * N 数组,代表 N 个服务器,matrix[i][j] == 1,则代表 i 和 j 直接连接;不等于 1 时,代表 i 和 j 不直接连接。 matrix[i][i] == 1,即自己和自己直接连接。matrix[i][j] == matrix[j][i]。 计算初始需要给几台服务器广播,才可以使每个服务器都收到广播。 |
输入描述 | 输入描述输入为 N 行,每行有 N 个数字,为 0 或 1,由空格分隔,构成 N * N 的数组,N 的范围为 1 <= N <= 50。 |
输出描述 | 输出一个数字,为需要广播的服务器数量。 |
补充说明 | 补充说明 |
------------------------------------------------------ | |
示例 | |
示例1 | |
输入 | 1 0 0 0 1 0 0 0 1 |
输出 | 3 |
说明 | 3 台服务器相互不连接,所以需要分别广播这 3 台服务器。 |
示例2 | |
输入 | 1 1 1 1 |
输出 | 1 |
说明 | 2 台服务器相互连接,所以只需要广播其中一台服务器。 |
解读与分析
题目解读:
在矩阵中,直接连接的服务器用 1 表示,不连接的用 0 表示,连接性是传递的。把相互连接的服务器放到同一个集合中,不连接的服务器在不同的集合中。求一共有多少个集合。
分析与思路:
本题虽标记为“难”,实际很简单。
逐一这个服务器,采用深度或广度遍历,逐一把遍历后连接的服务器放到同一个集合中。最后,集合的个数就是需要广播的服务器台数。
代码实现
Java代码
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;
import java.util.List;
import java.util.ArrayList;/*** 服务器广播* * @since 2023.10.15* @version 0.1* @author Frank**/
public class ServerBroadcastCount {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();String[] strNumbers = input.split(" ");int count = strNumbers.length;int[][] numbers = new int[count][count];for (int i = 0; i < count; i++) {if (i != 0) {// 首行已读取input = sc.nextLine();strNumbers = input.split(" ");}int[] lineNum = new int[count];for (int j = 0; j < count; j++) {lineNum[j] = Integer.parseInt(strNumbers[j]);}numbers[i] = lineNum;}processServerBroadcastCount(numbers);}}private static void processServerBroadcastCount( int numbers[][] ){Set<Integer> usedNumber = new HashSet<Integer>();List<Set<Integer>> connectionList = new ArrayList<Set<Integer>>();for( int i = 0; i < numbers.length; i ++ ){if( usedNumber.contains( i ) ){continue;}Set<Integer> newConnectionSet = new HashSet<Integer>();usedNumber.add( i );newConnectionSet.add( i );initConnectionSet( i, usedNumber, newConnectionSet, numbers);connectionList.add(newConnectionSet );}System.out.println( connectionList.size() );}private static void initConnectionSet(int idx, Set<Integer> usedNumber, Set<Integer> newConnectionSet,int numbers[][]) {for( int i = 0; i < numbers.length; i ++ ){if( i == idx ){continue;}int idxCheck = numbers[idx][i];if( usedNumber.contains( i ) || idxCheck == 0 ){continue;}usedNumber.add( i );newConnectionSet.add( i );initConnectionSet( i, usedNumber, newConnectionSet, numbers);}}}
JavaScript代码
const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {var strNumbers = line.split(" ");var count = strNumbers.length;var numbers = new Array();for (var i = 0; i < count; i++) {if (i != 0) {// 首行已读取line = await readline()strNumbers = line.split(" ");}var lineNum = new Array();for (var j = 0; j < count; j++) {lineNum[j] = parseInt(strNumbers[j]);}numbers[i] = lineNum;}processServerBroadcastCount(numbers);}
}();function processServerBroadcastCount(numbers) {var usedNumber = new Set();var connectionList = new Array();for (var i = 0; i < numbers.length; i++) {if (usedNumber.has(i)) {continue;}var newConnectionSet = new Set();usedNumber.add(i);newConnectionSet.add(i);initConnectionSet(i, usedNumber, newConnectionSet, numbers);connectionList.push(newConnectionSet);}console.log(connectionList.length);
}function initConnectionSet(idx, usedNumber, newConnectionSet,numbers) {for (var i = 0; i < numbers.length; i++) {if (i == idx) {continue;}var idxCheck = numbers[idx][i];if (usedNumber.has(i) || idxCheck == 0) {continue;}usedNumber.add(i);newConnectionSet.add(i);initConnectionSet(i, usedNumber, newConnectionSet, numbers);}
}
(完)
相关文章:
华为OD机考算法题:服务器广播
题目部分 题目服务器广播难度难题目说明服务器连接方式包括直接相连,间接连接。A 和 B 直接连接,B 和 C 直接连接,则 A 和 C 间接连接。直接连接和间接连接都可以发送广播。 给出一个 N * N 数组,代表 N 个服务器,mat…...

Android ViewBinding和DataBinding功能作用区别
简述 ViewBinding和DataBinding都是用于在 Android 应用程序中处理视图的工具,但它们有不同的作用和用途。 ViewBinding: ViewBinding 是 Android Studio 的一个工具,用于生成一个绑定类,能够轻松访问 XML 布局文件中的视图。ViewBinding 为…...

【云计算网络安全】DDoS 攻击类型:什么是 ACK 洪水 DDoS 攻击
文章目录 一、什么是 ACK 洪水 DDoS 攻击?二、什么是数据包?三、什么是 ACK 数据包?四、ACK 洪水攻击如何工作?五、SYN ACK 洪水攻击如何工作?六、文末送书《AWD特训营》内容简介读者对象 一、什么是 ACK 洪水 DDoS 攻…...

springboot 导出word模板
一、安装依赖 <dependency><groupId>com.deepoove</groupId><artifactId>poi-tl</artifactId><version>1.12.1</version></dependency>二、定义工具类 package com.example.springbootmp.utils;import com.deepoove.poi.XWP…...

Angular安全专辑之五 —— 防止URL中敏感信息泄露
URL 中的敏感数据是指在网址上的机密或者个人信息,包括 UserId, usernames, passwords, session, token 等其他认证信息。 由于URL 可能会被第三方拦截和查看(比如互联网服务商、代理或者其他监视网络流量的攻击者),所以URL中的敏…...

vueday01——文本渲染与挂载
1.定义html样式字符串 const rawHtml "<span stylecolor:red>htmlTest</span>" 2.创建标签,分别渲染普通文本和html文本 <p> 你好<span v-html"rawHtml"></span></p> 3.代码展示 4.结果展示...

Prometheus的Pushgateway快速部署及使用
prometheus-pushgateway安装 一. Pushgateway简介 Pushgateway为Prometheus整体监控方案的功能组件之一,并做于一个独立的工具存在。它主要用于Prometheus无法直接拿到监控指标的场景,如监控源位于防火墙之后,Prometheus无法穿透防火墙&…...
spring cloud config 占位符 application用法
前一篇讲过spring cloud config pattern 的用法,但是在使用spring cloud config的时候,我们经常会根据config client的application name来选择对应的central config的路径,当然spring cloud config官网也给出了相关的说明,但是说的并不算明朗,也没有举例说明在spring clou…...

SAP ERP系统解决光伏电池产业管理难题
无锡哲讯聚焦光伏行业的业务需求和流程,推出SAP光伏能源行业整体化解决方案。该系统着眼于“企业管理信息化、资源合理配置、利润扩张”三个方面,提供实用丰富的管理功能,同时具有较高的信息综合利用效率。SAP解决方案实现了光伏企业产、供、…...
el-table的formatter属性的使用方法
一、formatter是什么? formatter是el-table-column的一个属性,用来格式化内容。(比如后台给你返0或1,你需要展示成“否”和“是”) 二、详细使用 1.知道formatter之前: 代码如下(示例&#…...

高质量床上用品类网站带手机端的pbootcms模板
模板介绍: 这是一个基于PbootCMS内核开发的床上用品类网站模板,专为床上用品、家用纺织类企业设计和开发。它不仅提供了网站界面简洁简单、易于管理的特点,还附带了测试数据,方便用户进行演示和学习。 模板特点: 采用…...

paddlenlp:社交网络中多模态虚假媒体内容核查(特征篇)
初赛之特征构造 写在前面一、安装paddleOCR二、代码部分三、模型优缺点四、写在最后 写在前面 通过前面两篇文章的介绍,我们可以大致的知道模型用到的特征分为四块:qCap,qImg,captions,imgs。根据这些特征,…...

【网络】总览(待更新)
网络Ⅰ 零、概述0. 网络协议1. 网络协议分层OSI 七层模型TCP/IP 五层模型 2. 协议报头3. 通信过程 一、应用层1.1 🔗HTTP 协议1.2 🔗HTTPS 协议 二、传输层2.1 端口号2.2 netstat - - 查询网络状态2.3 pidof - - 查看服务器的进程 id2.4 🔗UD…...
策略模式——多重if-else解决方案
概念 大量的 if 判断操作,逻辑比较复杂,并且处理起来相对麻烦。可以采用策略模式来优化分支代码。 策略模式 💤:是一种行为设计模式,它允许你在运行时根据不同情况选择不同的算法或行为。 设计模式 🤌&…...

CTAmap 1.12版本2013年-2023年省市县矢量数据更新
中国行政区划数据CTAmap 1.12版本更新 从2022年起,笔者开始整理长时间序列的中国行政区划数据,通过以国家基础地理信息矢量数据为基础,以高德、民政部、gadm、乡镇界、村界、各省标准地图等区划矢量数据和相关行政区划变更文字资料为参考&am…...

【Linux初阶】多线程3 | 线程同步,生产消费者模型(普通版、BlockingQueue版)
文章目录 ☀️一、线程同步🌻1.条件变量🌻2.同步概念与竞态条件🌻3.条件变量函数🌻4.条件变量使用规范🌻5.代码案例 ☀️二、生产者消费者模型🌻1.为何要使用生产者消费者模型🌻2.生产者消费者模…...
JUC并发编程——四大函数式接口(基于狂神说的学习笔记)
四大函数式接口 函数式接口:只有一个方法的接口 ,例如:Runnable接口 Function 函数型接口,有一个输入参数,有一个输出 源码: /*** Represents a function that accepts one argument and produces a resul…...

【2】c++11新特性(稳定性和兼容性)—>超长整型 long long
c11标准要求long long整型可以在不同的平台上有不同的长度,但是至少64位,long long整型有两种: 有符号long long:–对应类型的数值可以使用LL或者ll后缀 long long num1 123456789LL; long long num2 123456789ll;无符号unsign…...

AI算法检测对无人军用车辆的MitM攻击
南澳大利亚大学和查尔斯特大学的教授开发了一种算法来检测和拦截对无人军事机器人的中间人(MitM)攻击。 MitM 攻击是一种网络攻击,其中两方(在本例中为机器人及其合法控制器)之间的数据流量被拦截,以窃听或…...

运维 | 如何在 Linux 系统中删除软链接 | Linux
运维 | 如何在 Linux 系统中删除软链接 | Linux 介绍 在 Linux 中,符号链接(symbolic link,或者symlink)也称为软链接,是一种特殊类型的文件,用作指向另一个文件的快捷方式。 使用方法 我们可以使用 ln…...
应用升级/灾备测试时使用guarantee 闪回点迅速回退
1.场景 应用要升级,当升级失败时,数据库回退到升级前. 要测试系统,测试完成后,数据库要回退到测试前。 相对于RMAN恢复需要很长时间, 数据库闪回只需要几分钟。 2.技术实现 数据库设置 2个db_recovery参数 创建guarantee闪回点,不需要开启数据库闪回。…...

CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序
一、开发环境准备 工具安装: 下载安装DevEco Studio 4.0(支持HarmonyOS 5)配置HarmonyOS SDK 5.0确保Node.js版本≥14 项目初始化: ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)
🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用
在工业制造领域,无损检测(NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统,以非接触式光学麦克风技术为核心,打破传统检测瓶颈,为半导体、航空航天、汽车制造等行业提供了高灵敏…...
pycharm 设置环境出错
pycharm 设置环境出错 pycharm 新建项目,设置虚拟环境,出错 pycharm 出错 Cannot open Local Failed to start [powershell.exe, -NoExit, -ExecutionPolicy, Bypass, -File, C:\Program Files\JetBrains\PyCharm 2024.1.3\plugins\terminal\shell-int…...