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

这道题到底在问什么

输入

grid = [[1,0],[0,1]]

输出

0(两台各处一行一列,谁也碰不到谁)

输入

grid = [[1,0],[1,1]]

输出

3(三台都能找到同行或同列的伙伴)

输入

本节演示 3×4 网格

输出

3

最优解：一步一步想明白

1. 3记住这条:先一遍扫出每行、每列各有几台服务器,再看每台服务器的行总数或列总数是不是大于 1,大于 1 就有同伴、能通信。
2. 4先看清这张网格。中间 3 行 4 列是数据,绿色格子是服务器,浅色格子是空位。一共有 4 台服务器:在第 0 行第 0 列、第 0 行第 1 列、第 1 行第 0 列,还有孤零零的第 2 行第 3 列。右边那一列等会儿填每行的服务器总数,底下那一行填每列的服务器总数,现在都是空的小圆点。
3. 5扫到第 0 行第 0 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 0 行的行总数加到 1,第 0 列的列总数加到 1。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
4. 6扫到第 0 行第 1 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 0 行的行总数加到 2,第 1 列的列总数加到 1。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
5. 7扫到第 0 行第 2 列,这格是 0,空位。行计数、列计数都不加,第 0 行还是 2,第 2 列还是 0。空格子不算服务器,自然不进任何计数。
6. 8扫到第 0 行第 3 列,这格是 0,空位。行计数、列计数都不加,第 0 行还是 2,第 3 列还是 0。空格子不算服务器,自然不进任何计数。
7. 9扫到第 1 行第 0 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 1 行的行总数加到 1,第 0 列的列总数加到 2。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
8. 10扫到第 1 行第 1 列,这格是 0,空位。行计数、列计数都不加,第 1 行还是 1,第 1 列还是 1。空格子不算服务器,自然不进任何计数。
9. 11扫到第 1 行第 2 列,这格是 0,空位。行计数、列计数都不加,第 1 行还是 1,第 2 列还是 0。空格子不算服务器,自然不进任何计数。
10. 12扫到第 1 行第 3 列,这格是 0,空位。行计数、列计数都不加,第 1 行还是 1,第 3 列还是 0。空格子不算服务器,自然不进任何计数。
11. 13扫到第 2 行第 0 列,这格是 0,空位。行计数、列计数都不加,第 2 行还是 0,第 0 列还是 2。空格子不算服务器,自然不进任何计数。
12. 14扫到第 2 行第 1 列,这格是 0,空位。行计数、列计数都不加,第 2 行还是 0,第 1 列还是 1。空格子不算服务器,自然不进任何计数。
13. 15扫到第 2 行第 2 列,这格是 0,空位。行计数、列计数都不加,第 2 行还是 0,第 2 列还是 0。空格子不算服务器,自然不进任何计数。
14. 16扫到第 2 行第 3 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 2 行的行总数加到 1,第 3 列的列总数加到 1。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
15. 17十二个格子扫完,两张计数都齐了。右列的行总数是第 0 行 2 台、第 1 行 1 台、第 2 行 1 台;底行的列总数是第 0 列 2 台、第 1 列 1 台、第 2 列 0 台、第 3 列 1 台。注意这些总数都把服务器自己算进去了。接下来只盯着 4 台服务器,逐台判它能不能通信。
16. 18判定规则就一句:对每台服务器,看它所在行的总数,或者所在列的总数,只要有一个大于 1,就说明同行或同列还坐着别的服务器,它就能通信,计入答案。为什么是大于 1 不是大于 0?因为总数把它自己也数进去了,大于 1 才意味着除自己之外还有同伴。下面一台一台来。
17. 19看第 0 行第 0 列这台服务器:行总数 2、列总数 2。它所在第 0 行总共 2 台,大于 1,这一行还有别的服务器,能通信,计入答案,能通信数变成 1。
18. 20看第 0 行第 1 列这台服务器:行总数 2、列总数 1。它所在第 0 行总共 2 台,大于 1,这一行还有别的服务器,能通信,计入答案,能通信数变成 2。
19. 21看第 1 行第 0 列这台服务器:行总数 1、列总数 2。它所在第 0 列总共 2 台,大于 1,这一列还有别的服务器,能通信,计入答案,能通信数变成 3。
20. 22看第 2 行第 3 列这台服务器:行总数 1、列总数 1。两个都只有 1,说明它这一行、这一列都只有它自己,找不到能通信的同伴,不计入。把它标红,提醒这是台孤独的服务器。
21. 23四台判完:第 0 行的两台靠同一行互相通信,第 1 行第 0 列那台靠第 0 列和上面那台通信,这三台都是绿色、计入答案;只有第 2 行第 3 列那台,行里列里都只有它一个,标红出局。能通信的服务器一共 3 台,这就是最终答案。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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)
        )

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问