建材企业网站推广方案,门户网站导航建设方案,dedecms怎么部署网站,宁波网站建设网站这里有一幅服务器分布图#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 思路
暴力遍历。。。。我这种肯定不是最优的
先按行遍历如果出现第一个先记录位置然后看看有没有第二个的出现。
ac code
class Solution {public int countServers(int[][] grid) {int ans 0;int n grid.length;int m grid[0].length;boolean[][] vis new boolean[n][m];for (int i 0;in;i) {int flag 0;int firstX -1;int firstY -1;for (int j 0;jm;j) {if (grid[i][j] 1) {if (flag 1) {ans 1;vis[i][j] true;} else if (flag 1) {ans 2;vis[i][j] true;vis[firstX][firstY] true;} else {firstX i;firstY j;}flag 1;}}}for (int i0;im;i) {int flag 0;int firstX -1;int firstY -1;for (int j0;jn;j) {if (grid[j][i] 1) {if (flag 1) {ans (vis[j][i] ? 0 : 1);vis[j][i] true;} else if (flag 1) {ans (vis[j][i] ? 0 : 1);ans (vis[firstX][firstY] ? 0 : 1);vis[j][i] true;vis[firstX][firstY] true;} else {firstX j;firstY i;}flag 1;}}}return ans;}
}
还有更优的比如可以通过hashmap去记录行列是否出现或者是通过一维数组一个变量去记录放一个更优的解法。
class Solution:def countServers(self, grid: List[List[int]]) - int:m,nlen(grid),len(grid[0])col_alone[-1]*nans0for i in range(m):row_alone-1for j in range(n):if grid[i][j]0:continueif row_alone-1 and col_alone[j]-1:##同行同列没有服务器row_alonejcol_alone[j]ielse:if row_alone0:ans1col_alone[row_alone]-2ans(col_alone[j]0)1row_alone-2col_alone[j]-2return ans
