2025-12-26：总价值可以被 K 整除的岛屿数目。用go语言，给定一个大小为 m×n 的矩阵 grid 和一个正整数 k。矩阵中数值大于 0 的格子视为陆地；若若干这样的格子通过上下或左右相邻连接在一起，则构成同一块连通的陆地区域。把某块区域内所有格子的数值相加得出该区域的总价值。请计算并返回那些总价值能够被 k 整除的陆地区域的个数。m == grid.length。n == grid[i].length。1 <= m, n <= 1000。1 <= m * n <= 100000。0 <= grid[i][j] <= 1000000。1 <= k < = 1000000。输入: 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），就递归调用 dfs 函数继续探索。递归返回的结果会累加到当前结果中。• 终止条件：当所有相邻格子都被探索完毕（即遇到水或已访问的格子）时，递归结束，返回累加的总价值。3. 遍历网格并统计符合条件的岛屿程序使用双重循环遍历网格中的每一个格子。• 发现新岛屿：对于格子 (i, j)，如果它的值大于 ，说明找到了一块未被访问的陆地的起点，也就是一个新岛屿的开始。• 计算总价值并判断：立即调用 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 <= m * n <= 100000 也确保了该算法在空间上是可行的。Go完整代码如下：.package mainimport ("fmt")funccountIslands(grid [][]int, k int) (ans int) { dirs := []struct{ x, y int }{{, -1}, {, 1}, {-1, }, {1, }} m, n := len(grid), len(grid[])var dfs func(int, int)int dfs = func(i, j int)int { res := grid[i][j] grid[i][j] = // 标记 (i,j) 访问过for _, d := range dirs { x, y := i+d.x, j+d.yif <= x && x < m && <= y && y < n && grid[x][y] > { res += dfs(x, y) } }return res }for i, row := range grid {for j, x := range row {if x > && dfs(i, j)%k == { ans++ } } }return}funcmain() { grid := [][]int{{3, , 3, }, {, 3, , 3}, {3, , 3, }} k := 3 result := countIslands(grid, k) fmt.Println(result)}Python完整代码如下：.# -*-coding:utf-8-*-from typing import Listdef count_islands(grid: List[List[int]], k: int) -> int: dirs = [(, -1), (, 1), (-1, ), (1, )] m, n = len(grid), len(grid[]) def dfs(i: int, j: int) -> int: res = grid[i][j] grid[i][j] = # 标记 (i, j) 访问过for dx, dy in dirs: x, y = i + dx, j + dyif <= x < m and <= y < n and grid[x][y] > : res += dfs(x, y)return res ans = for i in range(m):for j in range(n):if grid[i][j] > : total = dfs(i, j)if total % k == : ans += 1return ansif __name__ == "__main__": grid = [[3, , 3, ], [, 3, , 3], [3, , 3, ]] k = 3 result = count_islands(grid, k)print(result) C++完整代码如下：.#include <iostream>#include <vector>using namespace std;int countIslands(vector<vector<int>>& grid, int k) {// 四个方向：上、下、左、右 vector<pair<int, int>> dirs = {{, -1}, {, 1}, {-1, }, {1, }};int m = grid.size();int n = grid[].size();int ans = ;// 深度优先搜索函数，返回连通分量的节点值之和 auto dfs = [&](auto&& self, int i, int j) -> int {int res = grid[i][j]; grid[i][j] = ; // 标记为已访问for (auto& d : dirs) {int x = i + d.first;int y = j + d.second;if (x >= && x < m && y >= && y < n && grid[x][y] > ) { res += self(self, x, y); } }return res; };for (int i = ; i < m; i++) {for (int j = ; j < n; j++) {if (grid[i][j] > ) {int sum = dfs(dfs, i, j);if (sum % k == ) { ans++; } } } }return ans;}int main() { vector<vector<int>> grid = {{3, , 3, }, {, 3, , 3}, {3, , 3, }};int k = 3;int result = countIslands(grid, k); cout << result << endl;return;}
·
我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。
·
启灯网配资提示：文章来自网络，不代表本站观点。
