1267 Count Servers that Communicate 统计参与通信的服务器
Description:
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:
Example 1:
[图片上传失败...(image-f3ce88-1660993325019)]
Input: grid = [[1,0],[0,1]]
Output: 0
Explanation: No servers can communicate with others.
Example 2:
[图片上传失败...(image-1d460e-1660993325019)]
Input: grid = [[1,0],[1,1]]
Output: 3
Explanation: All three servers can communicate with at least one other server.
Example 3:
[图片上传失败...(image-fc8c24-1660993325019)]
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 表示没有。
如果两台服务器位于同一行或者同一列，我们就认为它们之间可以进行通信。
请你统计并返回能够与至少一台其他服务器进行通信的服务器的数量。
示例：
示例 1：
[图片上传失败...(image-cc0a52-1660993325019)]
输入：grid = [[1,0],[0,1]]
输出：0
解释：没有一台服务器能与其他服务器进行通信。
示例 2：
[图片上传失败...(image-2033ba-1660993325019)]
输入：grid = [[1,0],[1,1]]
输出：3
解释：所有这些服务器都至少可以与一台别的服务器进行通信。
示例 3：
[图片上传失败...(image-feb2ee-1660993325019)]
输入：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
思路：
模拟
先按行和列统计服务器的数量
然后再查找当前行或列上除了本身还有其他服务器的服务器
时间复杂度为 O(n ^ 2), 空间复杂度为 O(n)
代码:
C++:
class Solution
{
public:
int countServers(vector<vector<int>>& grid)
{
int result = 0, m = grid.size(), n = grid.front().size();
vector<int> row(m), col(n);
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (grid[i][j])
{
++row[i];
++col[j];
}
}
}
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] and (row[i] > 1 or col[j] > 1)) ++result;
return result;
}
};
Java:
class Solution {
public int countServers(int[][] grid) {
int result = 0, m = grid.length, n = grid[0].length, row[] = new int[m], col[] = new int[n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
++row[i];
++col[j];
}
}
}
for (int i = 0; i < m; i++) for (int j = 0; j < n; j++) if (grid[i][j] != 0 && (row[i] > 1 || col[j] > 1)) ++result;
return result;
}
}
Python:
class Solution:
def countServers(self, grid: List[List[int]]) -> int:
return sum(grid[i][j] and ((count_row := [sum(row) for row in grid])[i] > 1 or (count_col := [sum(col) for col in zip(*grid)])[j] > 1) for i in range(len(grid)) for j in range(len(grid[0])))
网友评论