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

Leetcode每日一题:1267. 统计参与通信的服务器

原题

这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。

如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

示例 1:

输入:grid = [[1,0],[0,1]]
输出:0
解释:没有一台服务器能与其他服务器进行通信。

示例 2:

输入:grid = [[1,0],[1,1]]
输出:3
解释:所有这些服务器都至少可以与一台别的服务器进行通信。

示例 3:

输入:grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出:4
解释:第一行的两台服务器互相通信,第三列的两台服务器互相通信,但右下角的服务器无法与其他服务器通信。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m <= 250
  • 1 <= n <= 250
  • grid[i][j] == 0 or 1

来源:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

解题思路

我们把题目读懂之后,就会发现题目要求我们统计每行每列中1大于等于2个行列上1的个数。一个简单的解题方法就是统计每行每列中1的个数,然后遍历每个值是1的点,看看所在行列上1的个数是否大于等于2。于是我们得到官方题解的实现:

class Solution {
public:int countServers(vector<vector<int>>& grid) {int m = grid.size(), n = grid[0].size();unordered_map<int, int> rows, cols;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1) {++rows[i];++cols[j];}}}int ans = 0;for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (grid[i][j] == 1 && (rows[i] > 1 || cols[j] > 1)) {++ans;}}}return ans;}
};作者:力扣官方题解
链接:https://leetcode.cn/problems/count-servers-that-communicate/solutions/101819/tong-ji-can-yu-tong-xin-de-fu-wu-qi-by-leetcode-so/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

优化题解

官方题解需要遍历两次全部的点,有没有优化的空间呢?其实我们遍历每行的时候,如果该行1的个数大于等于2,那么全都是符合结果的点。如果刚好等于1,那么需要后续判断这一列上1的点的个数是否大于等于2。因此我们可以先收集起来,最后判断,这样我们第二轮的时间复杂度可以降低到O(n)。基于这个思路,我们的优化版本:

class Solution {
public:int countServers(vector<vector<int>>& grid) {int m = grid.size();int n = grid[0].size();unordered_map<int, int> cols;int ans = 0,col = 0, rows=0;vector<int> srows;for(int i = 0; i < m;i++){rows=0;for(int j =0;j< n;j++){if(grid[i][j] == 1){++rows;++cols[j];col = j;}}if(rows >= 2){ans+=rows;}else if(rows == 1){srows.emplace_back(col);}}for(int &j:srows){if(cols[j]>=2){++ans;}}return ans;}
};

相关文章:

Leetcode每日一题:1267. 统计参与通信的服务器

原题 这里有一幅服务器分布图&#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中&#xff0c;1 表示单元格上有服务器&#xff0c;0 表示没有。 如果两台服务器位于同一行或者同一列&#xff0c;我们就认为它们之间可以进行通信。 请你统计并返回能够与至少一台其…...

HarmonyOS开发:超详细了解项目的工程结构

前言 系列文章目录&#xff1a; HarmonyOS开发第一步&#xff0c;熟知开发工具DevEco Studio 当我们熟练的掌握了DevEco Studio之后&#xff0c;就可以创建项目进行练习了&#xff0c;和市场上大多数IDE一样&#xff0c;DevEco Studio也给我们提供了很多的实例模板&#xff0c…...

HTML基础知识点

目录 ​编辑一、使用 vscode 二、研究代码的特点 三、HTML 常见标签 注释标签 标题标签 段落标签 换行标签 格式化标签 图片标签 超链接标签 表格标签 列表标签 表单标签&#xff1a; form 标签 input标签&#xff1a; select textarea标签&#xff1a; 无语…...

基于CBAM-CNN卷积神经网络预测研究(Python代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

iOS开发Swift-基本运算符

1.一元、二元、三元运算符 一元单一操作对象-a !b c!二元两个操作对象2 3三元三目运算符a ? b : c 2.赋值运算符() let a 10 var b 5 b a let (x, y) (1, 2)赋值运算符不返回任何值&#xff0c;所以 if x y { ... } 无效。 3.算术运算符 - * / 默认不允许数…...

Flink java 工具类

flink 环境构建工具类 public class ExecutionEnvUtil {/*** 从配置文件中读取配置(生效优先级&#xff1a;配置文件<命令行参数<系统参数&#xff09;** param args* return org.apache.flink.api.java.utils.ParameterTool* date 2023/8/4 - 10:05 AM*/public static …...

2023年你需要知道的最佳预算Wi-Fi路由器清单

买新路由器?让我们帮助你挑选一些既有很多功能和性能,又经济实惠的产品。 购买Wi-Fi路由器并不一定要倾家荡产,尤其是如果你不需要一个提供数百Mbps速度的路由器。廉价路由器是一个很好的选择,它包含了许多功能,不会对钱包造成影响。 一、2023年在廉价Wi-Fi路由器中寻找…...

Go语言基础之流程控制

流程控制是每种编程语言控制逻辑走向和执行次序的重要部分&#xff0c;流程控制可以说是一门语言的“经脉”。 Go语言中最常用的流程控制有if和for&#xff0c;而switch和goto主要是为了简化代码、降低重复代码而生的结构&#xff0c;属于扩展类的流程控制。 if else(分支结构…...

Git 安装、配置并把项目托管到码云 Gitee

错误聚集篇&#xff1a; 由于我 git 碰见大量错误&#xff0c;所以集合了一下&#xff1a; git 把项目托管到 码云出现的错误集合_打不着的大喇叭的博客-CSDN博客https://blog.csdn.net/weixin_49931650/article/details/132460492 1、安装 git 1.1 安装步骤 1.1.1 下载对应…...

C++信息学奥赛1147:最高分数的学生姓名

#include <iostream> #include <string> using namespace std; int main() {int n;// 输入一个整数ncin>>n;cin.ignore();string arr;string str;int max0;int fen;// 循环读取n个评分和对应的字符串for(int i0;i<n;i){cin>>fen>>arr;if(fen&…...

STM32使用PID调速

STM32使用PID调速 PID原理 PID算法是一种闭环控制系统中常用的算法&#xff0c;它结合了比例&#xff08;P&#xff09;、积分&#xff08;I&#xff09;和微分&#xff08;D&#xff09;三个环节&#xff0c;以实现对系统的控制。它的目的是使 控制系统的输出值尽可能接近预…...

【UE5:CesiumForUnreal】——3DTiles数据属性查询和单体高亮

目录 0.1 效果展示 0.2 实现步骤 1 数据准备 2 属性查询 2.1 射线检测 2.2 获取FeatureID 2.3 属性查询 2.4 属性显示 3 单体高亮 3.1 构建材质参数集 3.2 材质参数设置 3.3 添加Cesium Encode Metadata插件 3.4 从纹理中取出特定FeatureId属性信息 3.5 创建…...

无涯教程-PHP - 返回类型声明

在PHP 7中&#xff0c;引入了一个新函数返回类型声明&#xff0c;返回类型声明指定函数应返回的值的类型&#xff0c;可以声明返回类型的以下类型。 intfloatbooleanstringinterfacesarraycallable 有效返回类型 <?phpdeclare(strict_types1);function returnIntValue(i…...

DOS常见命令

DOS常见命令 DOS是什么如何打开DOScmd常见的命令集合 DOS是什么 DOC命令是我们浏览器中的终端 &#xff0c;但不同的是我们打开软件的方式 使用的是点击文件图标&#xff0c;点击图标的同时 我们也相当于使用一个命令 只是我们看不见而已 在电脑上操作的时候 通常都是使用命令…...

Qt应用开发(拓展篇)——示波器/图表 QCustomPlot

一、介绍 QCustomPlot是一个用于绘图和数据可视化的Qt C小部件。它没有进一步的依赖关系&#xff0c;提供友好的文档帮助。这个绘图库专注于制作好看的&#xff0c;出版质量的2D绘图&#xff0c;图形和图表&#xff0c;以及为实时可视化应用程序提供高性能。 QCustomPl…...

【精度丢失】后端接口返回的Long类型参数,不同浏览器解析出的结果不一样

1、业务背景 有个同事找我帮他看一个问题&#xff0c;他给前端提供了一个接口。 这个接口是用来反查id的&#xff0c;他这里这个参数正常的返回值应该是 283232039247028226。 但前端反馈他&#xff0c;前端在浏览器&#xff08;火狐&#xff09;获取的值是 283232039247028…...

2023年国赛 高教社杯数学建模思路 - 案例:感知机原理剖析及实现

文章目录 1 感知机的直观理解2 感知机的数学角度3 代码实现 4 建模资料 # 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法&#xff0c;其…...

java-红黑树

节点内部存储 红黑树规则 或者&#xff1a; 红黑树添加节点规则&#xff1a; 添加节点默认是红色的&#xff08;效率高&#xff09; 红黑树示例 注&#xff1a;红黑树增删改查性能都很好...

vue2 vue中的常用指令

一、为什么要学习Vue 1.前端必备技能 2.岗位多&#xff0c;绝大互联网公司都在使用Vue 3.提高开发效率 4.高薪必备技能&#xff08;Vue2Vue3&#xff09; 二、什么是Vue 概念&#xff1a;Vue (读音 /vjuː/&#xff0c;类似于 view) 是一套 **构建用户界面 ** 的 渐进式 …...

AI驱动下的智能制造:工业自动化的新纪元

随着人工智能&#xff08;AI&#xff09;技术的持续进步&#xff0c;其在工业自动化领域的影响日益显著。作为现代科技的代表&#xff0c;AI不仅为各行业带来了前所未有的商机和技术思路&#xff0c;更在工业自动化领域中引发了一场深刻的变革。本文将深入探讨AI对智能制造的影…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

Python实现prophet 理论及参数优化

文章目录 Prophet理论及模型参数介绍Python代码完整实现prophet 添加外部数据进行模型优化 之前初步学习prophet的时候&#xff0c;写过一篇简单实现&#xff0c;后期随着对该模型的深入研究&#xff0c;本次记录涉及到prophet 的公式以及参数调优&#xff0c;从公式可以更直观…...

linux 错误码总结

1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

免费数学几何作图web平台

光锐软件免费数学工具&#xff0c;maths,数学制图&#xff0c;数学作图&#xff0c;几何作图&#xff0c;几何&#xff0c;AR开发,AR教育,增强现实,软件公司,XR,MR,VR,虚拟仿真,虚拟现实,混合现实,教育科技产品,职业模拟培训,高保真VR场景,结构互动课件,元宇宙http://xaglare.c…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...

「全栈技术解析」推客小程序系统开发:从架构设计到裂变增长的完整解决方案

在移动互联网营销竞争白热化的当下&#xff0c;推客小程序系统凭借其裂变传播、精准营销等特性&#xff0c;成为企业抢占市场的利器。本文将深度解析推客小程序系统开发的核心技术与实现路径&#xff0c;助力开发者打造具有市场竞争力的营销工具。​ 一、系统核心功能架构&…...

协议转换利器,profinet转ethercat网关的两大派系,各有千秋

随着工业以太网的发展&#xff0c;其高效、便捷、协议开放、易于冗余等诸多优点&#xff0c;被越来越多的工业现场所采用。西门子SIMATIC S7-1200/1500系列PLC集成有Profinet接口&#xff0c;具有实时性、开放性&#xff0c;使用TCP/IP和IT标准&#xff0c;符合基于工业以太网的…...

Linux中《基础IO》详细介绍

目录 理解"文件"狭义理解广义理解文件操作的归类认知系统角度文件类别 回顾C文件接口打开文件写文件读文件稍作修改&#xff0c;实现简单cat命令 输出信息到显示器&#xff0c;你有哪些方法stdin & stdout & stderr打开文件的方式 系统⽂件I/O⼀种传递标志位…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...