网站生成wap,2023年九月份新闻,电商网站开发重难点,wordpress自定义tag页面来源#xff1a;力扣#xff08;LeetCode#xff09;
描述#xff1a;
这里有一幅服务器分布图#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中#xff0c;1 表示单元格上有服务器#xff0c;0 表示没有。
如果两台服务器位于同一行或者同一列#xff…来源力扣LeetCode
描述
这里有一幅服务器分布图服务器的位置标识在 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.lengthn grid[i].length1 m 2501 n 250grid[i][j] 0 or 1
方法两次遍历 哈希表
思路与算法
我们可以使用两次遍历解决本题。
在第一次遍历中我们遍历数组 grid如果 grid[i, j] 的值为 1说明位置 (i, j) 有一台服务器我们可以将第 i 行服务器的数量以及第 j 行服务器的数量均加上 1。为了维护行列中服务器的数量我们可以使用两个哈希映射 row 和 colrow 中存储行的编号以及每一行服务器的数量col 存储列的编号以及每一列服务器的数量。
在第二次遍历中我们就可以根据 row 和 col 来判断每一台服务器是否能与至少其它一台服务器进行通信了。如果 grid(i, j) 的值为 1并且 row[i] 和 col[j] 中至少有一个严格大于 1就说明位置 (i, j) 的服务器能与同一行或者同一列的另一台服务器进行通信答案加 1。
代码
class Solution {
public:int countServers(vectorvectorint grid) {int m grid.size(), n grid[0].size();unordered_mapint, int rows, cols;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {rows[i];cols[j];}}}int ans 0;for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1 (rows[i] 1 || cols[j] 1)) {ans;}}}return ans;}
};时间 48ms 击败 66.06%使用 C 的用户 内存 21.43MB 击败 23.03%使用 C 的用户 复杂度分析 时间复杂度O(mn)。空间复杂度O(mn)即为哈希映射需要使用的空间。 author力扣官方题解
