原題
這里有一幅服務(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.lengthn == grid[i].length1 <= m <= 2501 <= n <= 250grid[i][j] == 0 or 1
來(lái)源：力扣（LeetCode）官網(wǎng) - 全球極客摯愛(ài)的技術(shù)成長(zhǎng)平臺(tái)
解題思路
我們把題目讀懂之后，就會(huì)發(fā)現(xiàn)題目要求我們統(tǒng)計(jì)每行每列中1大于等于2個(gè)行列上1的個(gè)數(shù)。一個(gè)簡(jiǎn)單的解題方法就是統(tǒng)計(jì)每行每列中1的個(gè)數(shù)，然后遍歷每個(gè)值是1的點(diǎn)，看看所在行列上1的個(gè)數(shù)是否大于等于2。于是我們得到官方題解的實(shí)現(xiàn)：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-686488.html
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
unordered_map<int, 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/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。優(yōu)化題解
官方題解需要遍歷兩次全部的點(diǎn)，有沒(méi)有優(yōu)化的空間呢？其實(shí)我們遍歷每行的時(shí)候，如果該行1的個(gè)數(shù)大于等于2，那么全都是符合結(jié)果的點(diǎn)。如果剛好等于1，那么需要后續(xù)判斷這一列上1的點(diǎn)的個(gè)數(shù)是否大于等于2。因此我們可以先收集起來(lái)，最后判斷，這樣我們第二輪的時(shí)間復(fù)雜度可以降低到O(n)?；谶@個(gè)思路，我們的優(yōu)化版本：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-686488.html
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
unordered_map<int, int> cols;
int ans = 0,col = 0, rows=0;
vector<int> srows;
for(int i = 0; i < m;i++){
rows=0;
for(int j =0;j< n;j++){
if(grid[i][j] == 1){
++rows;
++cols[j];
col = j;
}
}
if(rows >= 2){
ans+=rows;
}else if(rows == 1){
srows.emplace_back(col);
}
}
for(int &j:srows){
if(cols[j]>=2){
++ans;
}
}
return ans;
}
};到了這里，關(guān)于Leetcode每日一題：1267. 統(tǒng)計(jì)參與通信的服務(wù)器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
