深圳高端網(wǎng)站制作公司線上推廣如何引流
【每日一題】1267. 統(tǒng)計(jì)參與通信的服務(wù)器
- 1267. 統(tǒng)計(jì)參與通信的服務(wù)器
- 題目描述
- 解題思路
1267. 統(tǒng)計(jì)參與通信的服務(wù)器
題目描述
這里有一幅服務(wù)器分布圖,服務(wù)器的位置標(biāo)識(shí)在 m * n 的整數(shù)矩陣網(wǎng)格 grid 中,1 表示單元格上有服務(wù)器,0 表示沒(méi)有。
如果兩臺(tái)服務(wù)器位于同一行或者同一列,我們就認(rèn)為它們之間可以進(jìn)行通信。
請(qǐng)你統(tǒng)計(jì)并返回能夠與至少一臺(tái)其他服務(wù)器進(jìn)行通信的服務(wù)器的數(shù)量。
示例 1:
輸入:grid = [[1,0],[0,1]]
輸出:0
解釋:沒(méi)有一臺(tái)服務(wù)器能與其他服務(wù)器進(jìn)行通信。
示例 2:
輸入:grid = [[1,0],[1,1]]
輸出:3
解釋:所有這些服務(wù)器都至少可以與一臺(tái)別的服務(wù)器進(jìn)行通信。
示例 3:
輸入:grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]]
輸出:4
解釋:第一行的兩臺(tái)服務(wù)器互相通信,第三列的兩臺(tái)服務(wù)器互相通信,但右下角的服務(wù)器無(wú)法與其他服務(wù)器通信。
提示:
m == grid.length
n == grid[i].length
1 <= m <= 250
1 <= n <= 250
grid[i][j] == 0 or 1
解題思路
思路:如果直接遍歷二維數(shù)組時(shí)再分別對(duì)每一項(xiàng)分別遍歷行或者列進(jìn)而判斷是否能夠參與通信的時(shí)間復(fù)雜度較高,故此時(shí)選擇對(duì)于是否能夠參與通信進(jìn)行預(yù)處理,即分別使用行數(shù)組row存儲(chǔ)每一行是否能夠參與通信、使用列數(shù)組col存儲(chǔ)每一列是否能夠參與通信,其中每一行或者每一列是否能夠參與通信的條件是為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)計(jì)行和列vector<bool> row(m,false);vector<bool> col(n,false);// 遍歷gird 統(tǒng)計(jì)行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)計(jì)列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)計(jì)行和列vector<int> row(m,0);vector<int> col(n,0);// 遍歷gird 統(tǒng)計(jì)行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類型,這樣只需要兩次遍歷。