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

題目描述

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

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

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

示例 1：

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

示例 2：

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

示例 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ù)組時再分別對每一項分別遍歷行或者列進而判斷是否能夠參與通信的時間復雜度較高，故此時選擇對于是否能夠參與通信進行預處理，即分別使用行數(shù)組row存儲每一行是否能夠參與通信、使用列數(shù)組col存儲每一列是否能夠參與通信，其中每一行或者每一列是否能夠參與通信的條件是為1的數(shù)量大于等于2。

class Solution {
public:
    int countServers(vector<vector<int>>& grid) {
        // 數(shù)據(jù)預處理
        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;
        // 遍歷grid
        for(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ù)預處理
        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;
        // 遍歷grid
        for(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類型，這樣只需要兩次遍歷。文章來源地址http://www.zghlxwxcb.cn/news/detail-672804.html

到了這里，關(guān)于【每日一題】1267. 統(tǒng)計參與通信的服務(wù)器的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！