日期：2026年10月26日
LeetCode 題目連結：3619. Count Islands With Total Value Divisible by K
解題想法
中等難度題。題目給一個二維陣列 $grid$，其中正整數代表陸地，0 代表海洋，地圖邊緣視為海洋。陸地可以與右、下、左、上相鄰的陸地相連，如果周圍被海洋環繞一圈，這片相連的陸地是一座島嶼。計算 $grid$ 之中有幾座島嶼的數值加總可以被 $k$ 整除。
這題是標準的 BFS。用雙層 for 迴圈掃過 $grid$ 每一格，如果遇到正整，從這格開始 BFS 計算加總 $val$，計算的過程中同時對 $k$ 取餘數。將走過的陸地都標示為 0，直接修改 $grid$ 的內容即可，節省記憶體。BFS 結束之後，如果 $val$ 等於 0，答案 $ans$ 加 1。
Python 程式碼
Runtime: 270 ms, beats 90.00%. Memory: 30.06 MB, beats 93.79%.
class Solution:
def countIslands(self, grid: List[List[int]], k: int) -> int:
m, n, ans = len(grid), len(grid[0]), 0 # 地圖 m*n，答案
# 掃過每一格，如果這格不等於 0，BFS 走完相連的格子
for i in range(m):
for j in range(n):
if grid[i][j] != 0:
val = grid[i][j] % k
que = deque([(i, j)])
grid[i][j] = 0
while que:
r, c = que.popleft()
for dr, dc in ((0, 1), (1, 0), (0, -1), (-1, 0)):
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] != 0:
val = (val + grid[nr][nc]) % k
grid[nr][nc] = 0
que.append((nr, nc))
if val == 0: ans += 1 # 符合條件，答案加 1
return ans
C++ 程式碼
Runtime: 151 ms, beats 18.42%. Memory: 199.62 MB, beats 30.41%.
class Solution {
public:
int countIslands(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size(), ans = 0; // 地圖 m*n，答案
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查的位移量
/* 掃過每一格，如果這格不等於 0，BFS 走完相連的格子，計算加總 val 的過程要對 k 取餘數避免溢位 */
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
int val = grid[i][j] % k;
queue<pair<int, int>> que;
que.push({i, j});
grid[i][j] = 0;
while(!que.empty()) {
int r = que.front().first, c = que.front().second;
que.pop();
for(int d = 0; d < 4; d++) { // k 被題目用掉了
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {
val = (val + grid[nr][nc]) % k; // 對 k 取餘數
grid[nr][nc] = 0;
que.push({nr, nc});
}
}
}
if (val == 0) ans++; // 符合條件，答案加 1
}
}
}
return ans;
}
};
微調程式碼，將 $que$ 開在 for 迴圈外面，於 for 迴圈裡面開始 BFS 之前清空 $que$，這樣可以節省每次建立 $que$ 的時間及記憶體。但是 C++ 的 queue 沒有清空內容的 clear()，要用 while 迴圈清空內容。Runtime: 31 ms, beats 69.38%. Memory: 76.79 MB, beats 95.08%.
class Solution {
public:
int countIslands(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size(), ans = 0; // 地圖 m*n，答案
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查的位移量
queue<pair<int, int>> que; // 待走訪佇列開在外面
/* 掃過每一格，如果這格不等於 0，BFS 走完相連的格子，計算加總 val 的過程要對 k 取餘數避免溢位 */
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
int val = grid[i][j] % k;
while(!que.empty()) que.pop(); // 清空 que
que.push({i, j});
grid[i][j] = 0;
while(!que.empty()) {
int r = que.front().first, c = que.front().second;
que.pop();
for(int d = 0; d < 4; d++) { // k 被題目用掉了
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {
val = (val + grid[nr][nc]) % k; // 對 k 取餘數
grid[nr][nc] = 0;
que.push({nr, nc});
}
}
}
if (val == 0) ans++; // 符合條件，答案加 1
}
}
}
return ans;
}
};
C++ 的 deque，於 BFS 之前用 clear() 清空內容。Runtime: 32 ms, beats 67.45%. Memory: 76.69 MB, beats 95.08%.
class Solution {
public:
int countIslands(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size(), ans = 0; // 地圖 m*n，答案
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查的位移量
deque<pair<int, int>> que; // 待走訪佇列開在外面，要用 deque 才能 clear()
/* 掃過每一格，如果這格不等於 0，BFS 走完相連的格子，計算加總 val 的過程要對 k 取餘數避免溢位 */
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
int val = grid[i][j] % k;
que.clear();
que.push_back({i, j});
grid[i][j] = 0;
while(!que.empty()) {
int r = que.front().first, c = que.front().second;
que.pop_front();
for(int d = 0; d < 4; d++) { // k 被題目用掉了
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {
val = (val + grid[nr][nc]) % k; // 對 k 取餘數
grid[nr][nc] = 0;
que.push_back({nr, nc});
}
}
}
if (val == 0) ans++; // 符合條件，答案加 1
}
}
}
return ans;
}
};
先開好待走訪佇列。Runtime: 20 ms, beats 91.22%. Memory: 71.66 MB, beats 100.00%.
class Solution {
public:
int countIslands(vector<vector<int>>& grid, int k) {
int m = grid.size(), n = grid[0].size(), ans = 0; // 地圖 m*n，答案
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查的位移量
int que[100000][2]; // 待走訪佇列開在外面，避免重複建立陣列
/* 掃過每一格，如果這格不等於 0，BFS 走完相連的格子，計算加總 val 的過程要對 k 取餘數避免溢位 */
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
int val = grid[i][j] % k, head = 0, total = 1;
que[0][0] = i;
que[0][1] = j;
grid[i][j] = 0;
while(head < total) {
int r = que[head][0], c = que[head][1];
head++;
for(int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {
val = (val + grid[nr][nc]) % k; // 對 k 取餘數
grid[nr][nc] = 0;
que[total][0] = nr;
que[total][1] = nc;
total++;
}
}
}
if (val % k == 0) ans++; // 符合條件，答案加 1
}
}
}
return ans;
}
};
C 語言程式碼
Runtime: 12 ms, beats 100.00%. Memory: 21.84MB, beats 100.00%.
int countIslands(int** grid, int gridSize, int* gridColSize, int k) {
int m = gridSize, n = *gridColSize, ans = 0; // 地圖 m*n，答案
int dr[4] = {0, 1, 0, -1}, dc[4] = {1, 0, -1, 0}; // 四方位檢查的位移量
int que[100000][2]; // 待走訪佇列開在外面，避免重複建立陣列
/* 掃過每一格，如果這格不等於 0，BFS 走完相連的格子，計算加總 val 的過程要對 k 取餘數避免溢位 */
for(int i = 0; i < m; i++) {
for(int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
int val = grid[i][j] % k, head = 0, total = 1;
que[0][0] = i;
que[0][1] = j;
grid[i][j] = 0;
while(head < total) {
int r = que[head][0], c = que[head][1];
head++;
for(int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] != 0) {
val = (val + grid[nr][nc]) % k; // 對 k 取餘數
grid[nr][nc] = 0;
que[total][0] = nr;
que[total][1] = nc;
total++;
}
}
}
if (val % k == 0) ans++; // 符合條件，答案加 1
}
}
}
return ans;
}
沒有留言:
張貼留言