526互联

[LeetCode] 1267. Count Servers that Communicate

发布时间 2023-08-24 01:25:58作者: CNoodle

You are given a map of a server center, represented as a m * n integer matrix grid, where 1 means that on that cell there is a server and 0 means that it is no server. Two servers are said to communicate if they are on the same row or on the same column.

Return the number of servers that communicate with any other server. 

Example 1:

Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.

Example 2:

Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.

Example 3:

Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
Output: 4
Explanation: The two servers in the first row can communicate with each other. The two servers in the third column can communicate with each other. The server at right bottom corner can't communicate with any other server.

Constraints:

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

统计参与通信的服务器。

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

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

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

思路是用两个 hashmap 分别统计行和列的服务器的数量，需要对 input 矩阵扫描两边。第一遍扫描的事后，比如在 grid[i][j] 位置有一个服务器，我们就在存储行和列的 hashmap 里分别在 i 行和 j 列加 1。我们再次扫描一遍矩阵，当再次遇到某个点上有服务器的时候，此时我们去看两个 hashmap 里当前行和当前列，只要当前行和当前列这二者有任何一个存储的元素超过一个，就说明当前位置这个服务器可以和与他同一行或者同一列的其他某个服务器通信。

时间O(mn)

空间O(n)

Java实现

 1 class Solution {
 2     public int countServers(int[][] grid) {
 3         int m = grid.length;
 4         int n = grid[0].length;
 5         HashMap<Integer, Integer> rows = new HashMap<>();
 6         HashMap<Integer, Integer> cols = new HashMap<>();
 7         for (int i = 0; i < m; i++) {
 8             for (int j = 0; j < n; j++) {
 9                 if (grid[i][j] == 1) {
10                     rows.put(i, rows.getOrDefault(i, 0) + 1);
11                     cols.put(j, cols.getOrDefault(j, 0) + 1);
12                 }
13             }
14         }
15 
16         int res = 0;
17         for (int i = 0; i < m; i++) {
18             for (int j = 0; j < n; j++) {
19                 if (grid[i][j] == 1 && (rows.get(i) > 1 || cols.get(j) > 1)) {
20                     res++;
21                 }
22             }
23         }
24         return res;
25     }
26 }

 

LeetCode 题目总结