leetcode
leetcode 1201 ~ 1250
统计参与通信的服务器

统计参与通信的服务器

难度:

标签:

题目描述

这里有一幅服务器分布图,服务器的位置标识在 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

代码结果

运行时间: 40 ms, 内存: 17.9 MB


/*
 * 思路:
 * 1. 使用Java Stream API进行行和列的遍历,并统计每行和每列的服务器数量。
 * 2. 再次遍历矩阵,使用Stream判断每个服务器是否能与其他服务器通信。
 * 3. 统计能够与至少一台其他服务器进行通信的服务器数量。
 */

import java.util.stream.IntStream;

public class Solution {
    public int countServers(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] rowCount = new int[m];
        int[] colCount = new int[n];

        // 计算每一行和每一列的服务器数量
        IntStream.range(0, m).forEach(i -> IntStream.range(0, n).forEach(j -> {
            if (grid[i][j] == 1) {
                rowCount[i]++;
                colCount[j]++;
            }
        }));

        // 统计能够与至少一台其他服务器进行通信的服务器数量
        return (int) IntStream.range(0, m).flatMap(i -> IntStream.range(0, n).filter(j -> grid[i][j] == 1 && (rowCount[i] > 1 || colCount[j] > 1))).count();
    }
}

解释

方法:

这个题解首先使用一个一维数组 rowc 来存储每一列的服务器总数。数组的初始值设为 -1,表示该列的服务器数量还未计算。对于网格中的每一行,先计算该行中服务器的数量。如果一行中的服务器数量大于1,表示这行的所有服务器都可以互相通信,直接将该行的服务器数量加到最终结果中。如果一行中只有一个服务器,需要检查这个服务器所在的列是否已经计算过服务器总数,如果未计算,则遍历该列统计服务器数量并更新 rowc 数组。如果该服务器所在的列的服务器总数大于1,则这台服务器可以与其他服务器通信,将结果加1。

时间复杂度:

O(m * n)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法实现中,为什么初始化列计数器`rowc`数组的所有元素为-1?这里的-1具体代表什么含义?
在算法中,`rowc`数组用于存储每一列的服务器数量。初始化所有元素为-1的目的是作为一个标记,表示该列的服务器数量未被计算。这样,当算法遇到需要知道某一列的服务器数量时,如果对应的`rowc`值为-1,就知道需要遍历这个列来计算服务器数量,否则直接使用`rowc`数组中的值。这种做法避免了不必要的重复计算,提高了算法效率。
🦆
在解释中提到,对于每一个单独的服务器,还需要检查其对应的列,这在最坏情况下可能需要再次遍历整个列。请问这种情况是如何发生的?能否通过优化减少这种重复遍历的情况?
这种情况发生在当网格的某一行只有一个服务器,并且这个服务器所在的列的服务器数量尚未被计算时。在现有的算法实现中,每当遇到只有一个服务器的行,都可能需要遍历那个服务器所在的列来计算列的服务器总数。为了减少这种重复遍历,可以在算法一开始对所有列进行一次遍历,预先计算好每列的服务器数量,并存储在`rowc`数组中。这样,在处理每行数据时,就无需再次遍历列,直接从`rowc`中读取即可。虽然这增加了初始的计算开销,但避免了后续的重复遍历,特别是在大规模数据时,这种优化是有益的。
🦆
算法中将行中服务器数量大于1时的处理和只有一个服务器时的处理区分开来了,请问这样设计的原因是什么?
这样设计的主要原因是优化算法效率和处理逻辑的简化。当一行中的服务器数量大于1时,这行的所有服务器都可以互相通信,因此可以直接将该行的服务器数量累加到结果中。相反,如果一行只有一个服务器,需要额外检查该服务器是否能与其所在列的其他服务器通信(即该列的服务器总数是否大于1)。这种分开处理的方法让算法在遇到可以直接确定结果的情况下更快处理,同时对于需要额外检查的情况,能够具体问题具体分析。
🦆
代码中使用了双重循环遍历行和列来计算列中的服务器数量(当`rowc[j]`为-1时),这种方法是否最优?存在更高效的方法来处理这个问题吗?
代码中的双重循环方法虽然直观,但不是最优的。更高效的方法是,可以在算法的一开始就遍历整个网格一次,同时计算每一行和每一列的服务器数量,存储在两个数组中。这样,在后续的处理中,就无需再对列进行单独的遍历,可以直接使用预先计算好的列服务器数量。这种一次遍历预处理的方法减少了重复计算,提高了算法的整体效率,尤其是对于大规模数据集。

相关问题