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.lengthn == grid[i].length1 <= m <= 2501 <= n <= 250grid[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. 统计参与通信的服务器
原题 这里有一幅服务器分布图,服务器的位置标识在 m * n 的整数矩阵网格 grid 中,1 表示单元格上有服务器,0 表示没有。 如果两台服务器位于同一行或者同一列,我们就认为它们之间可以进行通信。 请你统计并返回能够与至少一台其…...
HarmonyOS开发:超详细了解项目的工程结构
前言 系列文章目录: HarmonyOS开发第一步,熟知开发工具DevEco Studio 当我们熟练的掌握了DevEco Studio之后,就可以创建项目进行练习了,和市场上大多数IDE一样,DevEco Studio也给我们提供了很多的实例模板,…...
HTML基础知识点
目录 编辑一、使用 vscode 二、研究代码的特点 三、HTML 常见标签 注释标签 标题标签 段落标签 换行标签 格式化标签 图片标签 超链接标签 表格标签 列表标签 表单标签: form 标签 input标签: select textarea标签: 无语…...
基于CBAM-CNN卷积神经网络预测研究(Python代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&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)赋值运算符不返回任何值,所以 if x y { ... } 无效。 3.算术运算符 - * / 默认不允许数…...
Flink java 工具类
flink 环境构建工具类 public class ExecutionEnvUtil {/*** 从配置文件中读取配置(生效优先级:配置文件<命令行参数<系统参数)** 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语言基础之流程控制
流程控制是每种编程语言控制逻辑走向和执行次序的重要部分,流程控制可以说是一门语言的“经脉”。 Go语言中最常用的流程控制有if和for,而switch和goto主要是为了简化代码、降低重复代码而生的结构,属于扩展类的流程控制。 if else(分支结构…...
Git 安装、配置并把项目托管到码云 Gitee
错误聚集篇: 由于我 git 碰见大量错误,所以集合了一下: 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算法是一种闭环控制系统中常用的算法,它结合了比例(P)、积分(I)和微分(D)三个环节,以实现对系统的控制。它的目的是使 控制系统的输出值尽可能接近预…...
【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中,引入了一个新函数返回类型声明,返回类型声明指定函数应返回的值的类型,可以声明返回类型的以下类型。 intfloatbooleanstringinterfacesarraycallable 有效返回类型 <?phpdeclare(strict_types1);function returnIntValue(i…...
DOS常见命令
DOS常见命令 DOS是什么如何打开DOScmd常见的命令集合 DOS是什么 DOC命令是我们浏览器中的终端 ,但不同的是我们打开软件的方式 使用的是点击文件图标,点击图标的同时 我们也相当于使用一个命令 只是我们看不见而已 在电脑上操作的时候 通常都是使用命令…...
Qt应用开发(拓展篇)——示波器/图表 QCustomPlot
一、介绍 QCustomPlot是一个用于绘图和数据可视化的Qt C小部件。它没有进一步的依赖关系,提供友好的文档帮助。这个绘图库专注于制作好看的,出版质量的2D绘图,图形和图表,以及为实时可视化应用程序提供高性能。 QCustomPl…...
【精度丢失】后端接口返回的Long类型参数,不同浏览器解析出的结果不一样
1、业务背景 有个同事找我帮他看一个问题,他给前端提供了一个接口。 这个接口是用来反查id的,他这里这个参数正常的返回值应该是 283232039247028226。 但前端反馈他,前端在浏览器(火狐)获取的值是 283232039247028…...
2023年国赛 高教社杯数学建模思路 - 案例:感知机原理剖析及实现
文章目录 1 感知机的直观理解2 感知机的数学角度3 代码实现 4 建模资料 # 0 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 感知机的直观理解 感知机应该属于机器学习算法中最简单的一种算法,其…...
java-红黑树
节点内部存储 红黑树规则 或者: 红黑树添加节点规则: 添加节点默认是红色的(效率高) 红黑树示例 注:红黑树增删改查性能都很好...
vue2 vue中的常用指令
一、为什么要学习Vue 1.前端必备技能 2.岗位多,绝大互联网公司都在使用Vue 3.提高开发效率 4.高薪必备技能(Vue2Vue3) 二、什么是Vue 概念:Vue (读音 /vjuː/,类似于 view) 是一套 **构建用户界面 ** 的 渐进式 …...
AI驱动下的智能制造:工业自动化的新纪元
随着人工智能(AI)技术的持续进步,其在工业自动化领域的影响日益显著。作为现代科技的代表,AI不仅为各行业带来了前所未有的商机和技术思路,更在工业自动化领域中引发了一场深刻的变革。本文将深入探讨AI对智能制造的影…...
Vue记事本应用实现教程
文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展:显示创建时间8. 功能扩展:记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...
python/java环境配置
环境变量放一起 python: 1.首先下载Python Python下载地址:Download Python | Python.org downloads ---windows -- 64 2.安装Python 下面两个,然后自定义,全选 可以把前4个选上 3.环境配置 1)搜高级系统设置 2…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
STM32F4基本定时器使用和原理详解
STM32F4基本定时器使用和原理详解 前言如何确定定时器挂载在哪条时钟线上配置及使用方法参数配置PrescalerCounter ModeCounter Periodauto-reload preloadTrigger Event Selection 中断配置生成的代码及使用方法初始化代码基本定时器触发DCA或者ADC的代码讲解中断代码定时启动…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
【p2p、分布式,区块链笔记 MESH】Bluetooth蓝牙通信 BLE Mesh协议的拓扑结构 定向转发机制
目录 节点的功能承载层(GATT/Adv)局限性: 拓扑关系定向转发机制定向转发意义 CG 节点的功能 节点的功能由节点支持的特性和功能决定。所有节点都能够发送和接收网格消息。节点还可以选择支持一个或多个附加功能,如 Configuration …...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现指南针功能
指南针功能是许多位置服务应用的基础功能之一。下面我将详细介绍如何在HarmonyOS 5中使用DevEco Studio实现指南针功能。 1. 开发环境准备 确保已安装DevEco Studio 3.1或更高版本确保项目使用的是HarmonyOS 5.0 SDK在项目的module.json5中配置必要的权限 2. 权限配置 在mo…...
02.运算符
目录 什么是运算符 算术运算符 1.基本四则运算符 2.增量运算符 3.自增/自减运算符 关系运算符 逻辑运算符 &&:逻辑与 ||:逻辑或 !:逻辑非 短路求值 位运算符 按位与&: 按位或 | 按位取反~ …...
6.9-QT模拟计算器
源码: 头文件: widget.h #ifndef WIDGET_H #define WIDGET_H#include <QWidget> #include <QMouseEvent>QT_BEGIN_NAMESPACE namespace Ui { class Widget; } QT_END_NAMESPACEclass Widget : public QWidget {Q_OBJECTpublic:Widget(QWidget *parent nullptr);…...
数据结构第5章:树和二叉树完全指南(自整理详细图文笔记)
名人说:莫道桑榆晚,为霞尚满天。——刘禹锡(刘梦得,诗豪) 原创笔记:Code_流苏(CSDN)(一个喜欢古诗词和编程的Coder😊) 上一篇:《数据结构第4章 数组和广义表》…...
