LeetCode 1267. 统计参与通信的服务器

2023-08-25 HGNULB 约 9 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

✅ 1267. 统计参与通信的服务器

题意分析

给一个只含 0 和 1 的矩阵，grid[i][j] == 1 表示第 i 行第 j 列放着一台服务器。两台服务器只要处在同一行或同一列就能互相通信。问有多少台服务器至少能和另外一台通信。

关键是把「能通信」这个条件翻译准确。它不是一个需要传播的关系，而是一个只看自己所在行列的局部判定：服务器 (i, j) 能通信 ⟺ 第 i 行的服务器数量 ≥ 2，或者第 j 列的服务器数量 ≥ 2。注意题目问的是「能和至少一台通信」，不是问连通块大小，也不是问有多少个连通块，所以完全不需要沿着「同行 → 同列 → 再同行」这样一路传递下去。

这一点值得反复确认，因为题目的标签里挂着并查集、DFS、BFS，很容易被带偏去建图。建图的做法答案其实也对——因为一个服务器只要同行或同列有同伴，它所在的连通块大小就 ≥ 2，反之孤立的服务器连通块大小为 1——但那是绕了一大圈得到同一个结论，代价是 $O(mn(m+n))$ 级别的连边和一整套并查集模板。

另一个要卡住的点是「本身必须是服务器」。行列计数只统计了 1 的个数，一个值为 0 的格子哪怕所在行有十台服务器，它自己也不是服务器，不能计入答案。

约束是 $1 \le m, n \le 250$，矩阵最大 62500 个格子，$O(mn)$ 和 $O(mn(m+n))$ 都能过，所以时限不会替你把错误方向筛掉，必须自己判断哪条路更干净。边界情况：只有一台服务器时答案是 0；整行全是服务器而其余全空时，这一行全部计入；矩阵可能是长条形，行数和列数不相等。

解法：行列计数

核心思路

暴力的写法是对每个值为 1 的格子，横着扫一遍这一行、竖着扫一遍这一列，看有没有别的 1。这是 $O(mn(m+n))$，逻辑正确但重复劳动极其严重：同一行会被这一行里的每一台服务器各扫一次。

瓶颈很清楚——「第 i 行有几台服务器」这个量被反复重算。它只跟行号有关，跟是哪台服务器在问无关，那就把它预先算出来存起来。

于是引入两个计数数组，定义为：rowCount[i] = 第 i 行中值为 1 的格子数量，colCount[j] = 第 j 列中值为 1 的格子数量。这两个数组一次遍历就能填满：每遇到一个 1，就同时给它所在的行和列各加一。

有了这两个量，通信判定被彻底本地化：格子 (i, j) 计入答案 ⟺ grid[i][j] == 1 且（rowCount[i] > 1 或 colCount[j] > 1）。

为什么阈值是「> 1」而不是「> 0」：rowCount[i] 把当前这台服务器自己也数进去了，所以恰好等于 1 意味着这一行只有它孤零零一台。判定里的这个「自己也在计数里」是全题唯一的思维陷阱。

为什么必须分两趟遍历：判定要用到完整的行列计数，而第一趟遍历到 (i, j) 时，第 i 行右边和第 j 列下面的格子还没数过。边数边判会用到残缺的计数，第一行第一列的服务器几乎必然被漏判。

这个解法把「关系」问题降维成了「计数」问题，本质上是利用了「同行/同列」这种关系可以由一个一维标签（行号、列号）完全刻画的特点，不需要显式的图结构。

解题步骤

开两个计数数组：rowCount 长度为行数 m，colCount 长度为列数 n。两个长度必须分开取，矩阵不保证是方阵，用同一个 n 会在长条形输入上越界或算错。

第一趟遍历统计：双层循环扫过整个矩阵，只在 grid[i][j] == 1 时执行 rowCount[i]++ 和 colCount[j]++。这两个自增必须同时做——一个 1 既贡献给它的行，也贡献给它的列，只加其中一个会让另一维的判定整体失效。

第二趟遍历判定：再扫一遍矩阵，对每个格子先确认 grid[i][j] == 1，再看 rowCount[i] > 1 || colCount[j] > 1，两个条件都满足才 ans++。这里是或不是且：只要行或列任意一边有同伴就够了。

返回 ans。不需要任何后处理，也不需要去重——每台服务器在第二趟里只被访问一次，天然不会重复计数。

以 grid = [[1, 0], [1, 1]] 走一遍。

第一趟：(0,0) 是 1，rowCount[0] 变为 1，colCount[0] 变为 1；(0,1) 是 0，跳过；(1,0) 是 1，rowCount[1] 变为 1，colCount[0] 变为 2；(1,1) 是 1，rowCount[1] 变为 2，colCount[1] 变为 1。结束时 rowCount = [1, 2]，colCount = [2, 1]。

第二趟：(0,0) 是服务器，rowCount[0] = 1 不满足，但 colCount[0] = 2 > 1 满足，计入，ans = 1——它靠的是同列的 (1,0)；(0,1) 是 0，直接跳过；(1,0) 是服务器，rowCount[1] = 2 > 1 满足，计入，ans = 2；(1,1) 是服务器，rowCount[1] = 2 > 1 满足，计入，ans = 3。返回 3。

再拿 grid = [[1, 0], [0, 1]] 做对照。第一趟得到 rowCount = [1, 1]，colCount = [1, 1]。第二趟两台服务器的行计数和列计数全部等于 1，都不满足条件，返回 0。这组用例正好能打死「把阈值写成 > 0」的写法——那样会错误地返回 2。

代码实现

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)$，m、n 分别是矩阵的行数和列数。两趟独立的双层循环，每趟访问每个格子恰好一次，循环体内全是常数级的数组读写，没有任何嵌套搜索。相比暴力的 $O(mn(m+n))$，省下的正是被重复扫描的整行整列。

空间复杂度：$O(m + n)$，只额外开了 rowCount 和 colCount 两个一维数组，与矩阵中 1 的个数无关，也不像并查集解法那样需要 $O(mn)$ 的父节点数组和秩数组。

关键点总结

先判断关系是否需要传播。「同行同列可通信」听上去像连通性，但题目只问「有没有同伴」，判定半径是 1 跳，不是任意跳。分清「问邻居」和「问连通块」，能省掉一整套图算法。

把被重复计算的量提出来预处理，是从 $O(mn(m+n))$ 降到 $O(mn)$ 的唯一动作。识别的标准是：这个量只依赖循环的部分变量（这里只依赖行号或列号），却在更内层被反复求值。

计数包含自身，所以阈值要偏移一位。凡是「统计同类中除我之外还有没有别人」的场景，都要检查你的计数里有没有把自己算进去，> 1 和 > 0 差之毫厘。

需要全局信息的判定必须放在第二趟。一趟边统计边判定是这类题最常见的结构性错误，因为前面的元素看不到后面的统计结果。

面试视角：面试官抛出这题时，多半在观察你会不会条件反射地掏出并查集。正确的开场是先把「能通信 ⟺ 所在行或列的服务器数 > 1」这个等价条件说出来，说明为什么不需要建图，再给出 $O(mn)$ 时间、$O(m+n)$ 空间的两趟扫描。如果被追问「用并查集怎么做」，可以答：按行、按列分别把该行/该列的所有服务器合并到第一台上，最后统计所在集合大小大于 1 的服务器数量，复杂度同样是近似 $O(mn)$，但常数和代码量都大得多。

易错点总结

错误写法：判定条件写成 rowCount[i] > 0 || colCount[j] > 0 → 对 [[1,0],[0,1]] 会返回 2，正确答案是 0。因为每台服务器都会把自己数进所在行列，计数永远至少是 1。

错误写法：判定条件用 && 连接 → 对 [[1,0],[1,1]]，(0,0) 的行计数是 1，会被排除，返回 2 而不是 3。行和列只要满足一边即可。

错误写法：省掉 grid[i][j] == 1 的前提，只看行列计数 → 对 [[1,1,0],[0,0,0]]，第 0 行计数为 2，于是空格 (0,2) 也被判为「能通信」，返回 3 而不是 2。空格子永远不能计入答案。

错误写法：一趟循环里边累加计数边判定 → 对 [[1,0],[1,1]]，扫到 (0,0) 时 colCount[0] 才等于 1，(1,0) 还没统计，(0,0) 被漏判，返回 2。

错误写法：colCount 也开成行数长度（或两个数组都用 grid.length） → 在 3 × 250 这类长条矩阵上直接数组越界；在 250 × 3 上则会把不存在的列计数误当成 0，答案偏小。

错误写法：第一趟里只写 rowCount[i]++ 忘了 colCount[j]++ → 对 [[1,0],[1,0]]，两台服务器分属两行，行计数都是 1，列计数全为 0，返回 0，正确答案是 2。

错误写法：把答案统计成「行计数大于 1 的行里所有格子数之和」 → 混淆了「格子」和「服务器」，空格也被计入；[[1,1,0]] 会返回 3 而不是 2。

错误写法：为了「优化」只遍历值为 1 的格子并把坐标先收集进 list，却在收集时就做判定 → 本质还是边统计边判定，问题同上；收集坐标本身没错，但判定必须等两个计数数组填满之后。

错误写法：走「总数减孤立数」的反向思路，却把孤立判定写成 rowCount[i] == 1 || colCount[j] == 1 → 正确的孤立条件是两者都等于 1。对 [[1,0],[1,1]]，(0,0) 的行计数为 1 会被误判为孤立减掉，返回 2 而不是 3。

相似题目

题目	难度	考察点
419. 棋盘上的战舰	中等	同样避开搜索，靠「只统计每艘战舰的左上角格子」做一趟 $O(1)$ 空间的局部判定
200. 岛屿数量	中等	真正需要连通性传播的对照题，四联通必须 DFS/BFS 淹没，无法用行列计数降维
547. 省份数量	中等	问的是连通块个数而非「有无同伴」，必须并查集或 DFS，恰好是本题不需要建图的反例
73. 矩阵置零	中等	同样先记录「哪些行、哪些列被标记」再第二趟统一处理，两趟扫描的结构完全一致
2352. 相等行列对	中等	也是行与列的配对统计，但比较的是整行整列的内容，需要哈希整行而非只数个数
1254. 统计封闭岛屿的数目	中等	在连通块基础上追加「不触边界」的约束，说明何时才真的绕不开洪水填充
289. 生命游戏	中等	判定同样依赖邻域的完整快照，必须避免边算边改，与本题「两趟遍历」的动机同源