JZX轻语：简
LeetCode 1267 - 统计参与通信的服务器
发表于2024年07月15日
本质就是找到一组服务器，其中每个服务器至少和另一个服务器处在同一行或同一列中。一开始想用的是并查集，但不用那么复杂。有两种方法，第一种也是官解的做法，即两次遍历+哈希表的做法，首先第一次遍历用于统计每一行和每一列的服务器数量，第二次遍历则检查服务器对应的行和列是否有其他服务器，如果有，则计数；
第二种方法也是遍历两次，但第二次遍历仅需遍历行即可，使用的是逆向思维：统计落单的服务器个数，最后结果即为总服务器数减去落单的服务器数。首先第一次遍历统计所有的服务器数量、每一列的服务器数量以及每一行中仅有一个服务器的情况下，该服务器的所在列，第二次则遍历每一行，如果该行中仅有一个服务器，且该服务器所在列的服务器数量为1，则该服务器为落单服务器。
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
col_cnt = [0] * n # 记录每一列中服务器的数量
row_to_unique_col = [-1] * m # 记录每一行中唯一的服务器所在列, 如果没有服务器或者有多个服务器，则为-1
all_server_cnt = 0
for i in range(m):
last_server_col = -1
row_server_cnt = 0
for j in range(n):
if grid[i][j] == 1:
all_server_cnt += 1
col_cnt[j] += 1
row_server_cnt += 1
last_server_col = j
if row_server_cnt == 1: # 该行中仅有一个服务器, 记录其所在列
row_to_unique_col[i] = last_server_col
single_server_cnt = 0 # 落单的服务器个数
for i in range(m):
single_server_cnt += (row_to_unique_col[i] != -1 and col_cnt[row_to_unique_col[i]] == 1)
return all_server_cnt - single_server_cnt