Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Xin chào mọi người! Mình là Loser1 từ Learning AI with Loser. Hôm nay chúng ta sẽ giải quyết một bài toán thú vị về mạng lưới server! Let’s connect! 🚀
Chào anh em, các ae có thể xem Đề bài và Solution của mình trên LeetCode nhé:
Bạn được cung cấp một bản đồ trung tâm máy chủ, được biểu diễn dưới dạng ma trận số nguyên grid
kích thước m x n
, trong đó:
1
: Có máy chủ tại ô này.0
: Không có máy chủ tại ô này.Hai máy chủ được coi là có thể giao tiếp nếu chúng nằm trên cùng một hàng hoặc cùng một cột.
Trả về số lượng máy chủ có thể giao tiếp với ít nhất một máy chủ khác.
Ví dụ 1:
Input: grid = [[1,0],[0,1]] Output: 0 Giải thích: Không có máy chủ nào có thể giao tiếp với máy chủ khác.
Ví dụ 2:
Input: grid = [[1,0],[1,1]] Output: 3 Giải thích: Cả ba máy chủ đều có thể giao tiếp với ít nhất một máy chủ khác.
Ví dụ 3:
Input: grid = [[1,1,0,0],[0,0,1,0],[0,0,1,0],[0,0,0,1]] Output: 4 Giải thích: Hai máy chủ ở hàng đầu tiên có thể giao tiếp với nhau. Hai máy chủ trong cột thứ ba cũng có thể giao tiếp với nhau. Máy chủ ở góc dưới bên phải không thể giao tiếp với bất kỳ máy chủ nào khác.
Ràng buộc:
m == grid.length
n == grid[i].length
1 <= m, n <= 250
grid[i][j]
là 0
hoặc 1
.Cho một ma trận grid m*n, trong đó:
Hai server được coi là communicate với nhau nếu chúng nằm cùng hàng hoặc cùng cột.
Nhiệm vụ: Tìm số lượng server có thể communicate với ít nhất một server khác.
Xin chào, Loser1 đây! Khi nhìn vào bài này, mình liên tưởng đến một trung tâm dữ liệu khổng lồ với các máy chủ được kết nối theo grid! 🏢
Hãy xem xét một ví dụ đơn giản:
Trung tâm dữ liệu của chúng ta:
1 1 0 0 Server 1 ←→ Server 2 (kết nối theo hàng)
0 0 1 0 ↕
0 0 1 0 Server 3 (kết nối theo cột)
0 0 0 1 Server 4 (đơn độc)
Tưởng tượng mỗi server như một node trong mạng:
Các kết nối theo hàng: Các kết nối theo cột:
🔵──🔵 ⭕️ ⭕️ 🔵 🔵 ⭕️ ⭕️
⭕️ ⭕️ 🔵 ⭕️ + ⭕️ ⭕️ 🔵 ⭕️
⭕️ ⭕️ 🔵 ⭕️ ⭕️ ⭕️ 🔵 ⭕️
⭕️ ⭕️ ⭕️ 🔵 ⭕️ ⭕️ ⭕️ 🔵
= Tổng hợp kết nối cuối cùng:
🟦──🟦 ⬜️ ⬜️
⬜️ ⬜️ 🟨 ⬜️
⬜️ ⬜️ 🟨 ⬜️
⬜️ ⬜️ ⬜️ ⭕️
Server A ↔ Server B nếu:
- Cùng hàng: grid[i][j1] = grid[i][j2] = 1
- HOẶC cùng cột: grid[i1][j] = grid[i2][j] = 1
Case 1: Đơn độc Case 2: Kết nối hàng Case 3: Kết nối cột
0 0 0 1 1 0 1 0 0
0 1 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0
Count: 0 Count: 2 Count: 2
Thay vì check từng cặp: Dùng frequency counting:
O(n^2) operations rows = {0: 2, 2: 1}
↓ cols = {0: 1, 2: 2}
Server 1 → check all ↓
Server 2 → check all Server at (i,j) communicates
... if rows[i] > 1 || cols[j] > 1
Standalone Pattern: Connected Pattern:
1 0 0 1 1 0
0 0 0 vs 1 0 0
0 0 1 0 0 0
(0 communicate) (3 communicate)
Step 1: Count Step 2: Check Step 3: Result
1 1 0 rows[0] = 2 🟦🟦⬜️
1 0 0 → cols[0] = 2 → 🟦⬜️⬜️
0 0 1 rows[2] = 1 ⬜️⬜️⭕️
{r0:2, r2:1} Server(0,0): ✅ Communicate: 3
{c0:2, c2:1} Server(0,1): ✅ Non-comm: 1
Server(1,0): ✅
Server(2,2): ❌
Đây là cách tư duy "frequency-based" thay vì "pair-checking", giúp tối ưu hóa solution của chúng ta! 🚀
Note: Các ký hiệu:
class Solution {
public:
int countServers(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
unordered_map<int, int> rows, cols;
// Count frequencies
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
rows[i]++;
cols[j]++;
}
}
}
// Count communicating servers
int result = 0;
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if(grid[i][j] == 1) {
if(rows[i] > 1 || cols[j] > 1) {
result++;
}
}
}
}
return result;
}
};
Cùng phân tích ví dụ:
Input: grid = [[1,0,0],
[1,1,0],
[0,0,1]]
Step 1: Count frequencies
- Duyệt ma trận:
* (0,0)=1 → rows[0]=1, cols[0]=1
* (1,0)=1 → rows[1]=1, cols[0]=2
* (1,1)=1 → rows[1]=2, cols[1]=1
* (2,2)=1 → rows[2]=1, cols[2]=1
Step 2: Check each server
(0,0): cols[0]=2 → communicate! ✅
(1,0): cols[0]=2 AND rows[1]=2 → communicate! ✅
(1,1): rows[1]=2 → communicate! ✅
(2,2): rows[2]=1 AND cols[2]=1 → không communicate ❌
Result: 3 servers communicate!
Visualization:
1 0 0 🟦⬜️⬜️
1 1 0 → 🟦🟨⬜️
0 0 1 ⬜️⬜️⭕️
🟦🟨: Communicate servers
⭕️: Non-communicate server
Chúc mọi người code vui! Hẹn gặp lại trong các bài Leetcode tiếp theo! 🚀
P/S: Follow mình tại Learning AI with Loser để cập nhật các bài giải Leetcode hàng ngày nhé! 💻✨
CODE EDITOR
#leetcode #leetcodedaily #algorithms #programming #learningwithlosers