无锡建网站电话,深入解析wordpress二手,一级消防工程师考试试题,百度做网站推广的费用目录
1267. 统计参与通信的服务器
题目描述#xff1a;
实现代码与解析#xff1a;
写法一#xff1a;两次遍历 hash
原理思路#xff1a;
写法二#xff1a;三次遍历
原理思路#xff1a; 1267. 统计参与通信的服务器
题目描述#xff1a; 这里有一幅服务器分…目录
1267. 统计参与通信的服务器
题目描述
实现代码与解析
写法一两次遍历 hash
原理思路
写法二三次遍历
原理思路 1267. 统计参与通信的服务器
题目描述 这里有一幅服务器分布图服务器的位置标识在 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
实现代码与解析
写法一两次遍历 hash
class Solution {
public:int countServers(vectorvectorint grid) {unordered_mapint, int row, col; for (int i 0; i grid.size(); i){for (int j 0; j grid[0].size(); j){if (grid[i][j] 1){row[i];col[j];}}}int res 0;for (int i 0; i grid.size(); i)for (int j 0; j grid[0].size(); j)if (grid[i][j] 1 (row[i] 1 || col[j] 1)) res;return res;}
};
原理思路 第一次遍历hash记录每一行每一列的有的1的个数。 第二次遍历如果此位置有1而且行或列有的服务器个数大于1res。 返回结果。
写法二三次遍历
class Solution {
public:int countServers(vectorvectorint grid) {int res 0;vectorbool row(grid.size(), false);vectorbool col(grid[0].size(), false);// 每行符合条件的for (int i 0; i grid.size(); i){int count 0;for (int j 0; j grid[0].size(); j)if (grid[i][j] 1) count;if (count 1){row[i] true;res count;}}// 每列符合条件的for (int i 0; i grid[0].size(); i){int count 0;for (int j 0; j grid.size(); j)if (grid[j][i] 1) count;if (count 1){col[i] true;res count;}}int repeat 0; // 重复的for (int i 0; i grid.size(); i)for (int j 0; j grid[0].size(); j)if (row[i] col[j] grid[i][j] 1) repeat;return res - repeat;}
};
原理思路 不用hash的写法。 第一次遍历行种符合条件的。 第二次遍历列中符合条件的。 第三次遍历重复计算的。 返回结果减去重复计算。
