怎么做 社区网站,wordpress提交表单插件,免费咨询男科医院,大型购物网站服务器【每日一题】1267. 统计参与通信的服务器 1267. 统计参与通信的服务器题目描述解题思路 1267. 统计参与通信的服务器
题目描述
这里有一幅服务器分布图#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中#xff0c;1 表示单元格上有服务器#xff0c;0 表示没有… 【每日一题】1267. 统计参与通信的服务器 1267. 统计参与通信的服务器题目描述解题思路 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.length n grid[i].length 1 m 250 1 n 250 grid[i][j] 0 or 1
解题思路
思路如果直接遍历二维数组时再分别对每一项分别遍历行或者列进而判断是否能够参与通信的时间复杂度较高故此时选择对于是否能够参与通信进行预处理即分别使用行数组row存储每一行是否能够参与通信、使用列数组col存储每一列是否能够参与通信其中每一行或者每一列是否能够参与通信的条件是为1的数量大于等于2。
class Solution {
public:int countServers(vectorvectorint grid) {// 数据预处理int mgrid.size();int ngrid[0].size();// 分别统计行和列vectorbool row(m,false);vectorbool col(n,false);// 遍历gird 统计行for(int i0;im;i){// 记录每行数量int num0;for(int j0;jn;j){if(grid[i][j]1)num;}if(num2)row[i]true;}// 遍历gird 统计列for(int i0;in;i){// 记录每列数量int num0;for(int j0;jm;j){if(grid[j][i]1)num;}if(num2)col[i]true;}int res0;// 遍历gridfor(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1(row[i]||col[j]))res;}}return res;}
};class Solution {
public:int countServers(vectorvectorint grid) {// 数据预处理int mgrid.size();int ngrid[0].size();// 分别统计行和列vectorint row(m,0);vectorint col(n,0);// 遍历gird 统计行for(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1){row[i];col[j];}}}int res0;// 遍历gridfor(int i0;im;i){for(int j0;jn;j){if(grid[i][j]1(row[i]2||col[j]2))res;}}return res;}
};总结第一次使用的数组是bool类型这样需要三次遍历第二次使用的数组是int类型这样只需要两次遍历。
