自动生成作文的网站,中小企业营销型网站建设,佛山市做网站的公司,国内体育新闻最新消息原题
这里有一幅服务器分布图#xff0c;服务器的位置标识在 m * n 的整数矩阵网格 grid 中#xff0c;1 表示单元格上有服务器#xff0c;0 表示没有。
如果两台服务器位于同一行或者同一列#xff0c;我们就认为它们之间可以进行通信。
请你统计并返回能够与至少一台其…原题
这里有一幅服务器分布图服务器的位置标识在 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
来源力扣LeetCode官网 - 全球极客挚爱的技术成长平台 解题思路
我们把题目读懂之后就会发现题目要求我们统计每行每列中1大于等于2个行列上1的个数。一个简单的解题方法就是统计每行每列中1的个数然后遍历每个值是1的点看看所在行列上1的个数是否大于等于2。于是我们得到官方题解的实现
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;}
};作者力扣官方题解
链接https://leetcode.cn/problems/count-servers-that-communicate/solutions/101819/tong-ji-can-yu-tong-xin-de-fu-wu-qi-by-leetcode-so/
来源力扣LeetCode
著作权归作者所有。商业转载请联系作者获得授权非商业转载请注明出处。
优化题解
官方题解需要遍历两次全部的点有没有优化的空间呢其实我们遍历每行的时候如果该行1的个数大于等于2那么全都是符合结果的点。如果刚好等于1那么需要后续判断这一列上1的点的个数是否大于等于2。因此我们可以先收集起来最后判断这样我们第二轮的时间复杂度可以降低到O(n)。基于这个思路我们的优化版本
class Solution {
public:int countServers(vectorvectorint grid) {int m grid.size();int n grid[0].size();unordered_mapint, int cols;int ans 0,col 0, rows0;vectorint srows;for(int i 0; i m;i){rows0;for(int j 0;j n;j){if(grid[i][j] 1){rows;cols[j];col j;}}if(rows 2){ansrows;}else if(rows 1){srows.emplace_back(col);}}for(int j:srows){if(cols[j]2){ans;}}return ans;}
};
