题目描述
思路解析动画文字版
记住这条:先一遍扫出每行、每列各有几台服务器,再看每台服务器的行总数或列总数是不是大于 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题