1267. 统计参与通信的服务器

难度: 中等

来源: 每日一题 2023.08.24

---

这里有一幅服务器分布图，服务器的位置标识在 m * n 的整数矩阵网格 grid 中，1 表示单元格上有服务器，0 表示没有。

如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。

请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。

示例 1：

输入：grid = [[1,0],[0,1]]
输出：0
解释：没有一台服务器能与其他服务器进行通信。

示例 2：

输入：grid = [[1,0],[1,1]]
输出：3
解释：所有这些服务器都至少可以与一台别的服务器进行通信。

示例 3：

输入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
输出：4
解释：第一行的两台服务器互相通信，第三列的两台服务器互相通信，但右下角的服务器无法与其他服务器通信。

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m <= 250
• 1 <= n <= 250
• grid[i][j] == 0 or 1

class Solution {
    public int countServers(int[][] grid) {

    }
}

分析与题解

---

• HashMap + 循环查找

  对于这个题目, 我们想要找到是否某一个电脑最少能与另外一台电脑互联, 我们只需要知道这台电脑 所在行 和所在列 电脑数量 不小于2个 即可满足题目要求.

  第一步, 我们需要构建一个HashMap来存储行和列的信息. 这样可以方便后期的快速查找.

  HashMap<String, Integer> cache = new HashMap<String, Integer>();
  for(int i = 0; i < grid.length; i++) {
      for(int j = 0; j < grid[i].length; j++) {
          if (grid[i][j] == 1) {
              if (cache.get("row_" + i) == null) {
                  cache.put("row_" + i, 1);
              } else {
                  Integer count = cache.get("row_" + i);
                  count++;
                  cache.put("row_" + i, count);
              }
              if (cache.get("column_" + j) == null) {
                  cache.put("column_" + j, 1);
              } else {
                  Integer count = cache.get("column_" + j);
                  count++;
                  cache.put("column_" + j, count);
              }
          }
      }
  }
  

  然后再次遍历整个矩阵, 判断电脑 所有行 和 所在列 的电脑数量情况.

  int result = 0;
  for(int i = 0; i < grid.length; i++) {
      for(int j = 0; j < grid[i].length; j++) {
          if (grid[i][j] == 1) {
              if(cache.get("row_" + i) >= 2 || cache.get("column_" + j) >= 2) {
                  result++;
              }
          }
      }
  }
  

  最终的解题过程如下所示.

  class Solution {
      public int countServers(int[][] grid) {
          HashMap<String, Integer> cache = new HashMap<String, Integer>();
          for(int i = 0; i < grid.length; i++) {
              for(int j = 0; j < grid[i].length; j++) {
                  if (grid[i][j] == 1) {
                      if (cache.get("row_" + i) == null) {
                          cache.put("row_" + i, 1);
                      } else {
                          Integer count = cache.get("row_" + i);
                          count++;
                          cache.put("row_" + i, count);
                      }
                      if (cache.get("column_" + j) == null) {
                          cache.put("column_" + j, 1);
                      } else {
                          Integer count = cache.get("column_" + j);
                          count++;
                          cache.put("column_" + j, count);
                      }
                  }
              }
          }
          int result = 0;
          for(int i = 0; i < grid.length; i++) {
              for(int j = 0; j < grid[i].length; j++) {
                  if (grid[i][j] == 1) {
                      if(cache.get("row_" + i) >= 2 || cache.get("column_" + j) >= 2) {
                          result++;
                      }
                  }
              }
          }
          return result;
      }
  }
  

  
  

  复杂度分析:

  • 时间复杂度: O(2ij), 时间复杂度与 grid 矩阵元素个数相关.
  • 空间复杂度: O(i+j), 要构建和 grid 矩阵行列的和的空间.

  结果如下所示.