邯郸营销型网站,淘宝优秀软文范例100字,借贷网站开发是否合法,广西南宁公司网站制作【LetMeFly】1267.统计参与通信的服务器
力扣题目链接#xff1a;https://leetcode.cn/problems/count-servers-that-communicate/
这里有一幅服务器分布图#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中#xff0c;1 表示单元格上有服务器#xff0c;0 表…【LetMeFly】1267.统计参与通信的服务器
力扣题目链接https://leetcode.cn/problems/count-servers-that-communicate/
这里有一幅服务器分布图服务器的位置标识在 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
方法一计数
假设 g i r d gird gird的 s i z e size size为 n × m n\times m n×m开辟两个数组 r o w [ n ] row[n] row[n]和 c o l [ m ] col[m] col[m]分别记录某行服务器个数 和 某列的服务器个数。
遍历一遍地图矩阵 g r i d grid grid若此处有服务器(server) 且 此行或此列不只一台服务器则 a n s ans ans
时间复杂度 O ( n × m ) O(n\times m) O(n×m)空间复杂度 O ( n m ) O(n m) O(nm)
AC代码
C
class Solution {
public:int countServers(vectorvectorint grid) {int n grid.size(), m grid[0].size();vectorint row(n), col(m);for (int i 0; i n; i) {for (int j 0; j m; j) {row[i] grid[i][j], col[j] grid[i][j];}}int ans 0;for (int i 0; i n; i) {for (int j 0; j m; j) {ans grid[i][j] * (row[i] 1 || col[j] 1);}}return ans;}
};Python
# from typing import Listclass Solution:def countServers(self, grid: List[List[int]]) - int:n, m len(grid), len(grid[0])col, row [0] * n, [0] * mfor i in range(n):for j in range(m):col[i] grid[i][j]row[j] grid[i][j]ans 0for i in range(n):for j in range(m):ans grid[i][j] * (col[i] 1 or row[j] 1)return ans同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/132466649
