统计参与通信的服务器 图解题解

哪些服务器不孤独，题目要数的就是它们

给一张 m 乘 n 的方格图，格子写 1 是一台服务器，写 0 是空位。两台服务器只要同行或同列就能通信，不要求挨着。要数的是能和至少另一台通信的服务器有几台，空格子不参与。题面 grid=[[1,0],[0,1]] 两台各占一行一列、谁也够不着，返回 0；grid=[[1,0],[1,1]] 三台都能找到同行或同列的伙伴，返回 3。

别把它当连通块去建图搜索

通信、方格、相连，这几个词最容易勾出连通块的思路：建图跑 DFS 一路走到底再回头，或者用并查集，也就是把相通的服务器归到同一组。但这题的通信不传递，它只问每台『同行或同列有没有另一台』，是就地的一次判断，不必连成一大片。为局部问题建整张图、维护访问标记，纯属做重。

一台能通信，等于它那行或那列服务器数＞1

一台服务器能不能通信，只取决于它所在那一行、或那一列，除它自己外还有没有别的服务器。先把每行、每列各有几台数清楚，开两个一维数组，row[i] 记第 i 行台数，col[j] 记第 j 列台数。再看某台的 row[i] 或 col[j]，有一个＞1 就说明这行或这列除它自己还坐着别人，它能通信。

两遍扫：先攒行列计数，再逐台判

第一遍双重循环扫每个格子，遇到 grid[i][j] 是 1 就记两笔：row[i] 加一、col[j] 加一，一个格子既进行计数、又进列计数，一趟把两张计数攒齐。第二遍再扫一次，只对值为 1 的格子判定：row[i]＞1 或 col[j]＞1 就计入答案。判定前先确认这格真有服务器，空格哪怕行列再热闹，本身没服务器也不能算。

拿 3 行 4 列那张网格逐台数一遍

网格里四台服务器坐在第 0 行第 0 列、第 0 行第 1 列、第 1 行第 0 列，还有第 2 行第 3 列。第一遍扫完，行总数第 0 行 2 台、第 1 行 1 台、第 2 行 1 台，写成 row=[2,1,1]；列总数第 0 列 2 台、第 1 列 1 台、第 2 列 0 台、第 3 列 1 台，写成 col=[2,1,0,1]。每个总数都含服务器自己。

第二遍逐台判。第 0 行第 0 列这台 row[0]=2＞1，计入，答案到 1；第 0 行第 1 列这台 row[0]=2＞1，计入，答案到 2；第 1 行第 0 列这台 row[1]=1 不够，但 col[0]=2＞1，靠同列计入，答案到 3；最后第 2 行第 3 列这台，row[2]=1、col[3]=1 都只剩它自己，行里列里都没同伴，不计入。四台判完，答案 3。

阈值差一格，答案就多出一堆孤独服务器

两遍都走一遍全网格，m 乘 n 个格子，仍是 O(m·n)，格子总数级别；只额外开 row、col 两个一维数组，长度分别 m、n，空间 O(m+n)，没开和网格一样大的二维表。最容易写反的是判定阈值：写成 row[i]＞0 或 col[j]＞0，孤独服务器也会被算进去，因为计数含自己、＞0 恒成立，必须严格＞1。还有一处别漏：判定前先卡 grid[i][j] 是 1，否则空格子会跟着行列高计数被误计。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
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)
        )

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> row(m), col(n);
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                row[i] += grid[i][j];
                col[j] += grid[i][j];
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                ans += grid[i][j] && (row[i] > 1 || col[j] > 1);
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int countServers(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] row = new int[m];
        int[] col = new int[n];
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                row[i] += grid[i][j];
                col[j] += grid[i][j];
            }
        }
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1 && (row[i] > 1 || col[j] > 1)) {
                    ++ans;
                }
            }
        }
        return ans;
    }
}