X

LEETCODE 1267. Count Servers that Communicate 解题思路分析

题目大意:

统计参与通信的服务器

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1267

解题思路分析:

题目给出的条件是,只要当前行或者列上有2台以上的服务器,那么,当前列或者行上的所有服务器都是相互连通的,根据这个条件,我们可以先遍历一遍二维数组,统计一下每行每列上各有多少台服务器。统计完成之后,再遍历一遍二维数组,如果当前位置存在服务器,并且当前位置所在的行或者列的服务器数大于1,那么当前服务器是合理解,返回结果加一,当整个数组遍历结束后,也就能统计出所有符合条件的个数。

这里有一处可以优化的地方,如果当前行存在的服务器台数大于1,那么这一行上的所有服务器都是合理解,可以直接将该行的台数加入返回结果,继续循环到下一行。如果当前行不存在服务器,同样可以直接跳到下一行。剩下的情况只有当前行仅有1台服务器的情况,我们在当前行遍历每一列,找到仅有的那一台所在的列,查看其所在列上的服务器台数是否大于1,如果是,代表当前服务器为合理解,返回结果加一。因为此行仅存在这一台,所以此处的列循环可以结束。

实现代码:

public int countServers(int[][] grid) {
    // 每一行服务器的台数
    int[] countRow=new int[grid.length];
    // 每一列服务器的台数
    int[] countCol=new int[grid[0].length];
    for(int i=0;i<grid.length;i++){ // 循环数组
        for(int j=0;j<grid[0].length;j++){
            if(grid[i][j]==1){ // 当前位置存在服务器
                countRow[i]++; // 当前行个数加一
                countCol[j]++; // 当前列个数加一
            }
        }
    }
    int res=0; // 返回结果
    for(int i=0;i<grid.length;i++){ // 循环行
        if(countRow[i]>1){ // 当前行服务器台数大于1
            res+=countRow[i]; // 将当前行服务器台数加入返回结果
            continue; // 循环到下一行
        }
        if(countRow[i]==0){ // 当前行没有服务器
            continue; // 循环到下一行
        }
        // 当前行只有一台服务器的情况,循环列
        for(int j=0;j<grid[0].length;j++){
            // 找到存在服务器的列
            if(grid[i][j]==1){
                // 当前列台数大于1,说明当前服务器为合理解
                if(countCol[j]>1) res++;
                break; // 退出列循环
            }
        }
    }
    return res;
}

本解法执行时间为2ms。

Runtime: 2 ms, faster than 99.90% of Java online submissions for Count Servers that Communicate.

Memory Usage: 55.1 MB, less than 100.00% of Java online submissions for Count Servers that Communicate.


本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1267-count-servers-that-communicate-解题思路分析/
Categories: leetcode
kwantong: