1267. 統(tǒng)計參與通信的服務(wù)器

題目描述

這里有一幅服務(wù)器分布圖，服務(wù)器的位置標(biāo)識在 m * n 的整數(shù)矩陣網(wǎng)格 grid 中，1 表示單元格上有服務(wù)器，0 表示沒有。

如果兩臺服務(wù)器位于同一行或者同一列，我們就認(rèn)為它們之間可以進(jìn)行通信。

請你統(tǒng)計并返回能夠與至少一臺其他服務(wù)器進(jìn)行通信的服務(wù)器的數(shù)量。

示例 1：

輸入：grid = [[1,0],[0,1]]
輸出：0
解釋：沒有一臺服務(wù)器能與其他服務(wù)器進(jìn)行通信。

示例 2：

輸入：grid = [[1,0],[1,1]]
輸出：3
解釋：所有這些服務(wù)器都至少可以與一臺別的服務(wù)器進(jìn)行通信。

示例 3：

輸入：grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
輸出：4
解釋：第一行的兩臺服務(wù)器互相通信，第三列的兩臺服務(wù)器互相通信，但右下角的服務(wù)器無法與其他服務(wù)器通信。

提示：

m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1

解題思路

思路：如果直接遍歷二維數(shù)組時再分別對每一項分別遍歷行或者列進(jìn)而判斷是否能夠參與通信的時間復(fù)雜度較高，故此時選擇對于是否能夠參與通信進(jìn)行預(yù)處理，即分別使用行數(shù)組row存儲每一行是否能夠參與通信、使用列數(shù)組col存儲每一列是否能夠參與通信，其中每一行或者每一列是否能夠參與通信的條件是為1的數(shù)量大于等于2。

class Solution {
public:int countServers(vector<vector<int>>& grid) {// 數(shù)據(jù)預(yù)處理int m=grid.size();int n=grid[0].size();// 分別統(tǒng)計行和列vector<bool> row(m,false);vector<bool> col(n,false);// 遍歷gird 統(tǒng)計行for(int i=0;i<m;i++){// 記錄每行數(shù)量int num=0;for(int j=0;j<n;j++){if(grid[i][j]==1)num++;}if(num>=2)row[i]=true;}// 遍歷gird 統(tǒng)計列for(int i=0;i<n;i++){// 記錄每列數(shù)量int num=0;for(int j=0;j<m;j++){if(grid[j][i]==1)num++;}if(num>=2)col[i]=true;}int res=0;// 遍歷gridfor(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&(row[i]||col[j]))res++;}}return res;}
};

class Solution {
public:int countServers(vector<vector<int>>& grid) {// 數(shù)據(jù)預(yù)處理int m=grid.size();int n=grid[0].size();// 分別統(tǒng)計行和列vector<int> row(m,0);vector<int> col(n,0);// 遍歷gird 統(tǒng)計行for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1){row[i]++;col[j]++;}}}int res=0;// 遍歷gridfor(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1&&(row[i]>=2||col[j]>=2))res++;}}return res;}
};

總結(jié)：第一次使用的數(shù)組是bool類型，這樣需要三次遍歷；第二次使用的數(shù)組是int類型，這樣只需要兩次遍歷。