2025-12-26：总价值可以被 K 整除的岛屿数目。用go语言，给定一个大小为 m×n 的矩阵 grid 和一个正整数 k。
矩阵中数值大于 0 的格子视为陆地；若若干这样的格子通过上下或左右相邻连接在一起，则构成同一块连通的陆地区域。
把某块区域内所有格子的数值相加得出该区域的总价值。
请计算并返回那些总价值能够被 k 整除的陆地区域的个数。
m == grid.length。
n == grid[i].length。
1
1
0
1
输入: grid = [[3,0,3,0], [0,3,0,3], [3,0,3,0]], k = 3。
输出: 6。
解释:
网格中包含六个岛屿，每个岛屿的总价值都可以被 3 整除。
题目来自力扣3619。
问题解决步骤
1. 初始化与准备工作
代码首先定义了一个方向数组 dirs，包含上下左右四个移动方向（上 {0, -1}、下 {0, 1}、左 {-1, 0}、右 {1, 0}）。然后获取网格的行数 m 和列数 n。
2. 定义深度优先搜索（DFS）函数
核心是一个递归的DFS函数 dfs，其作用是探索并计算一个完整岛屿区域的总价值。
• 参数与返回值：函数接收当前格子的坐标 (i, j)，返回以该格子为起点的整个连通区域所有格子数值的总和。
• 标记已访问：为了防止重复计算，函数一进入就将当前格子的值 grid[i][j] 设为 0。这既标记了该格子已被访问，也“淹没”了这块陆地。
• 探索相邻格子：函数检查当前格子的四个相邻格子。如果一个相邻格子坐标合法（在网格范围内）且是陆地（值大于0），就递归调用 dfs 函数继续探索。递归返回的结果会累加到当前结果中。
• 终止条件：当所有相邻格子都被探索完毕（即遇到水或已访问的格子）时，递归结束，返回累加的总价值。
3. 遍历网格并统计符合条件的岛屿
程序使用双重循环遍历网格中的每一个格子。
• 发现新岛屿：对于格子 (i, j)，如果它的值大于 0，说明找到了一块未被访问的陆地的起点，也就是一个新岛屿的开始。
• 计算总价值并判断：立即调用 dfs(i, j) 函数。这个调用会“淹没”并探索整个连通的岛屿区域，最终返回该岛屿的总价值。
• 条件计数：程序检查这个总价值是否能被给定的正整数 k 整除（即 总价值 % k == 0）。如果条件满足，就将结果计数器 ans 加 1。
4. 返回最终结果
当整个网格遍历完成后，计数器 ans 的值就是总价值能被 k 整除的岛屿数量，函数将其返回。
⏱️ 复杂度分析
• 时间复杂度：O(m × n)
算法需要遍历网格中的每一个格子（m × n 个）。虽然DFS递归本身有开销，但每个格子最多被访问一次（一旦被访问就被标记为0）。因此，总的时间复杂度主要由网格的大小决定，为 O(m × n)。
• 额外空间复杂度：O(m × n)
主要的额外空间消耗来自DFS的递归调用栈。在最坏的情况下，如果整个网格是一个巨大的连续岛屿，递归深度可能达到 m × n。因此，空间复杂度为 O(m × n)。 题目给定的约束条件 1
Go完整代码如下：
package main
import (
"fmt"
)
func countIslands(grid [][]int, k int) (ans int) {
dirs := []struct{ x, y int }{{0, -1}, {0, 1}, {-1, 0}, {1, 0}}
m, n := len(grid), len(grid[0])
var dfs func(int, int)int
dfs = func(i, j int)int {
res := grid[i][j]
grid[i][j] = 0// 标记 (i,j) 访问过
for _, d := range dirs {
x, y := i+d.x, j+d.y
if0 0 {
res += dfs(x, y)
}
}
return res
}
for i, row := range grid {
for j, x := range row {
if x > 0 && dfs(i, j)%k == 0 {
ans++
}
}
}
return
}
func main {
grid := [][]int{{3, 0, 3, 0}, {0, 3, 0, 3}, {3, 0, 3, 0}}
k := 3
result := countIslands(grid, k)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
from typing import List
def count_islands(grid: List[List[int]], k: int) -> int:
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
m, n = len(grid), len(grid[0])
def dfs(i: int, j: int) -> int:
res = grid[i][j]
grid[i][j] = 0 # 标记 (i, j) 访问过
for dx, dy in dirs:
x, y = i + dx, j + dy
if0 0:
res += dfs(x, y)
return res
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] > 0:
total = dfs(i, j)
if total % k == 0:
ans += 1
return ans
if __name__ == "__main__":
grid = [[3, 0, 3, 0], [0, 3, 0, 3], [3, 0, 3, 0]]
k = 3
result = count_islands(grid, k)
print(result)
C++完整代码如下：
#include
#include
using namespace std;
int countIslands(vector>& grid, int k) {
// 四个方向：上、下、左、右
vector> dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
int m = grid.size;
int n = grid[0].size;
int ans = 0;
// 深度优先搜索函数，返回连通分量的节点值之和
auto dfs = [&](auto&& self, int i, int j) -> int {
int res = grid[i][j];
grid[i][j] = 0; // 标记为已访问
for (auto& d : dirs) {
int x = i + d.first;
int y = j + d.second;
if (x >= 0 && x = 0 && y 0) {
res += self(self, x, y);
}
}
return res;
};
for (int i = 0; i
for (int j = 0; j
if (grid[i][j] > 0) {
int sum = dfs(dfs, i, j);
if (sum % k == 0) {
ans++;
}
}
}
}
return ans;
}
int main {
vector> grid = {{3, 0, 3, 0},
{0, 3, 0, 3},
{3, 0, 3, 0}};
int k = 3;
int result = countIslands(grid, k);
cout
return0;
}
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。
欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
股票配资平台网站提示：文章来自网络，不代表本站观点。
