LeetCode 题解工作台
统计参与通信的服务器
这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。 如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。 请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。 示例 1： 输入： grid = [[…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 图·搜索
答案摘要
我们可以统计每一行、每一列的服务器数量，然后遍历每个服务器，若当前服务器所在的行或者列的服务器数量超过 ，说明当前服务器满足条件，结果加 。 遍历结束后，返回结果即可。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 图·搜索 题型思路
题目描述
这里有一幅服务器分布图，服务器的位置标识在 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
解题思路
方法一：计数
我们可以统计每一行、每一列的服务器数量，然后遍历每个服务器，若当前服务器所在的行或者列的服务器数量超过 ，说明当前服务器满足条件，结果加 。
遍历结束后，返回结果即可。
时间复杂度 ，空间复杂度 。其中 和 分别为矩阵的行数和列数。
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
row = [0] * m
col = [0] * n
for i in range(m):
for j in range(n):
row[i] += grid[i][j]
col[j] += grid[i][j]
return sum(
grid[i][j] and (row[i] > 1 or col[j] > 1)
for i in range(m)
for j in range(n)
)
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | O(m \times n) |
| 空间 | O(1) |
面试官常问的追问
外企场景- question_mark
Look for an efficient grid traversal approach, possibly utilizing row and column counters.
- question_mark
Check if the candidate correctly applies DFS or BFS to avoid redundant counts.
- question_mark
See if the candidate focuses on optimizing the traversal to avoid unnecessary recalculations.
常见陷阱
外企场景- error
Not considering servers in isolated rows or columns which can't communicate with others.
- error
Overcomplicating the solution by attempting to check each server pair individually instead of using row and column counts.
- error
Failing to optimize the traversal, leading to unnecessary checks for already visited servers.
进阶变体
外企场景- arrow_right_alt
Grid with all cells having servers, where every server should communicate with every other server.
- arrow_right_alt
Grid with no servers, where the answer should be zero.
- arrow_right_alt
Sparse grids with servers scattered in isolated rows and columns.