LeetCode 1267. 统计参与通信的服务器
题目描述
题意分析
1表示服务器，0表示空格。两台服务器只要同行或同列就能通信，不要求相邻；返回至少能和另一台通信的服务器数量，而不是通信对数。对每台服务器，只需知道所在行或列是否还有别的服务器，无需建图搜索完整连通块。
解法：行列计数
核心思路
[!blue]
用
rowCount[row]记录一行的服务器总数，colCount[col]记录一列的服务器总数。先完整扫描网格，遇到服务器就同时增加对应行和列的计数。对服务器
(row, col)，计数已经包含它自己，所以rowCount[row] > 1才表示同行另有服务器，列也同理。两者只要一个成立就能通信；若两者都等于一，它就是孤立服务器。这给出了完整的判断条件。第二遍再逐格统计，保证使用的是完整行列数量，不会因为同伴尚未扫描到而漏算。每台服务器只执行一次“行或列”的判断，即使两个方向都有同伴，也只给答案加一。
解题步骤
- 创建长度分别为行数、列数的计数数组，初始值均为零。
- 第一遍扫描，只对
grid[row][col] == 1的格子增加行列计数。- 第二遍仍只检查服务器；若
rowCount[row] > 1 || colCount[col] > 1，答案加一。- 返回累计数量。没有服务器或只有一台时，没有位置满足条件，结果自然为零。
代码实现
class Solution {
public int countServers(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
int[] rowCount = new int[rows];
int[] colCount = new int[cols];
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
if (grid[row][col] == 1) {
// 同一台服务器同时计入所在行与所在列。
rowCount[row]++;
colCount[col]++;
}
}
}
int ans = 0;
for (int row = 0; row < rows; row++) {
for (int col = 0; col < cols; col++) {
// 只数服务器本身，行或列中有另一台就能通信。
if (grid[row][col] == 1 && (rowCount[row] > 1 || colCount[col] > 1)) {
ans++;
}
}
}
return ans;
}
}
func countServers(grid [][]int) int {
rows := len(grid)
cols := len(grid[0])
rowCount := make([]int, rows)
colCount := make([]int, cols)
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
if grid[row][col] == 1 {
// 同一台服务器同时计入所在行与所在列。
rowCount[row]++
colCount[col]++
}
}
}
ans := 0
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
// 只数服务器本身，行或列中有另一台就能通信。
if grid[row][col] == 1 && (rowCount[row] > 1 || colCount[col] > 1) {
ans++
}
}
}
return ans
}
复杂度分析
- 时间复杂度：$O(mn)$。
- 空间复杂度：$O(m+n)$，行列计数数组。
关键点总结
[!green]
- 空格即使所在行有很多服务器也不能计入。
- 通信条件是或，不需要行列同时有同伴。
易错点总结
[!yellow]
- 阈值写成大于零，会把自身当成同伴。
- 边统计边使用尚未完成的行列数，可能漏掉较早位置。
- 将行计数和列计数分别累加到答案，会重复计算同一台。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 361. 轰炸敌人 | 中等 | 同样按同行同列统计，原题被墙切成可见段，本题没有墙，整行整列都能通信。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！