题目描述
思路解析
一句话答案：LeetCode 1267 统计参与通信的服务器：一台能通信当且仅当它那行或那列还坐着别人，两遍扫先数每行每列各几台、再逐台看行数或列数是否＞1，时间 O(m·n)、空间 O(m+n)。
哪些服务器不孤独，题目要数的就是它们
给一张 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，否则空格子会跟着行列高计数被误计。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这条:先一遍扫出每行、每列各有几台服务器,再看每台服务器的行总数或列总数是不是大于 1,大于 1 就有同伴、能通信。
总览 · 3×4 网格(右列放行总数,底行放列总数)：先看清这张网格。中间 3 行 4 列是数据,绿色格子是服务器,浅色格子是空位。一共有 4 台服务器:在第 0 行第 0 列、第 0 行第 1 列、第 1 行第 0 列,还有孤零零的第 2 行第 3 列。右边那一列等会儿填每行的服务器总数,底下那一行填每列的服务器总数,现在都是空的小圆点。
一遍扫 · 累加第 (0,0) 格：扫到第 0 行第 0 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 0 行的行总数加到 1,第 0 列的列总数加到 1。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
一遍扫 · 累加第 (0,1) 格：扫到第 0 行第 1 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 0 行的行总数加到 2,第 1 列的列总数加到 1。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
一遍扫 · 累加第 (0,2) 格：扫到第 0 行第 2 列,这格是 0,空位。行计数、列计数都不加,第 0 行还是 2,第 2 列还是 0。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (0,3) 格：扫到第 0 行第 3 列,这格是 0,空位。行计数、列计数都不加,第 0 行还是 2,第 3 列还是 0。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (1,0) 格：扫到第 1 行第 0 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 1 行的行总数加到 1,第 0 列的列总数加到 2。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
一遍扫 · 累加第 (1,1) 格：扫到第 1 行第 1 列,这格是 0,空位。行计数、列计数都不加,第 1 行还是 1,第 1 列还是 1。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (1,2) 格：扫到第 1 行第 2 列,这格是 0,空位。行计数、列计数都不加,第 1 行还是 1,第 2 列还是 0。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (1,3) 格：扫到第 1 行第 3 列,这格是 0,空位。行计数、列计数都不加,第 1 行还是 1,第 3 列还是 0。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (2,0) 格：扫到第 2 行第 0 列,这格是 0,空位。行计数、列计数都不加,第 2 行还是 0,第 0 列还是 2。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (2,1) 格：扫到第 2 行第 1 列,这格是 0,空位。行计数、列计数都不加,第 2 行还是 0,第 1 列还是 1。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (2,2) 格：扫到第 2 行第 2 列,这格是 0,空位。行计数、列计数都不加,第 2 行还是 0,第 2 列还是 0。空格子不算服务器,自然不进任何计数。
一遍扫 · 累加第 (2,3) 格：扫到第 2 行第 3 列,这格是 1,是一台服务器。把这 1 同时记两笔:第 2 行的行总数加到 1,第 3 列的列总数加到 1。一个格子的值既进行计数、又进列计数,这是这趟扫描的关键。
扫描完成 · 行总数 [2,1,1]、列总数 [2,1,0,1]：十二个格子扫完,两张计数都齐了。右列的行总数是第 0 行 2 台、第 1 行 1 台、第 2 行 1 台;底行的列总数是第 0 列 2 台、第 1 列 1 台、第 2 列 0 台、第 3 列 1 台。注意这些总数都把服务器自己算进去了。接下来只盯着 4 台服务器,逐台判它能不能通信。
判定规则 · 行总数 > 1 或 列总数 > 1：判定规则就一句:对每台服务器,看它所在行的总数,或者所在列的总数,只要有一个大于 1,就说明同行或同列还坐着别的服务器,它就能通信,计入答案。为什么是大于 1 不是大于 0?因为总数把它自己也数进去了,大于 1 才意味着除自己之外还有同伴。下面一台一台来。
逐台判定 · 第 (0,0) 台服务器：看第 0 行第 0 列这台服务器:行总数 2、列总数 2。它所在第 0 行总共 2 台,大于 1,这一行还有别的服务器,能通信,计入答案,能通信数变成 1。
逐台判定 · 第 (0,1) 台服务器：看第 0 行第 1 列这台服务器:行总数 2、列总数 1。它所在第 0 行总共 2 台,大于 1,这一行还有别的服务器,能通信,计入答案,能通信数变成 2。
逐台判定 · 第 (1,0) 台服务器：看第 1 行第 0 列这台服务器:行总数 1、列总数 2。它所在第 0 列总共 2 台,大于 1,这一列还有别的服务器,能通信,计入答案,能通信数变成 3。
逐台判定 · 第 (2,3) 台服务器：看第 2 行第 3 列这台服务器:行总数 1、列总数 1。两个都只有 1,说明它这一行、这一列都只有它自己,找不到能通信的同伴,不计入。把它标红,提醒这是台孤独的服务器。
答案 · 能通信服务器 = 3：四台判完:第 0 行的两台靠同一行互相通信,第 1 行第 0 列那台靠第 0 列和上面那台通信,这三台都是绿色、计入答案;只有第 2 行第 3 列那台,行里列里都只有它一个,标红出局。能通信的服务器一共 3 台,这就是最终答案。
边界都能手验:对角各一台返回 0;填满返回 4;[[1,0],[1,1]] 三台能通信。都和计数判定对得上。
面试三连:不用连通块因为关系不传递;一趟循环行列计数一起累加;空间已是 O(m+n)、还能压到 O(n) 但意义不大。
参考代码
from __future__ import annotationsfrom 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) )复杂度
- 时间：O(m·n)，第一趟扫每个格子累加行列计数是 m 乘 n;第二趟再扫一遍判定还是 m 乘 n。两趟相加仍是 O(m·n),也就是格子总数级别
- 空间：O(m + n)，按峰值算:只额外开了 row、col 两个一维数组,长度分别是 m 和 n,合起来 m 加 n。没有递归、不建图、不开和网格同样大的二维表,所以是线性而非平方
易错点
面试追问把动画讲成自己的话
追问为什么不用 DFS、BFS 或并查集?
追问行计数和列计数为什么能在同一趟循环里一起算?
追问空间还能再省吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
跳跃游戏 III
LeetCode 1306 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题