发表于 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

• LC 题目链接