Medium

题目描述

给你一个 m x n 的矩阵 grid 和一个正整数 k。岛屿是由正整数（代表陆地）组成的 4 方向连通（水平或垂直）的区域。

岛屿的总价值是岛屿中所有单元格的值的总和。

返回总价值能被 k 整除的岛屿数量。

示例 1：

输入：grid = [[0,2,1,0,0],[0,5,0,0,5],[0,0,1,0,0],[0,1,4,7,0],[0,2,0,0,8]], k = 5
输出：2
解释：网格包含四个岛屿。蓝色高亮的岛屿总价值能被 5 整除，而红色高亮的岛屿不能。

示例 2：

输入：grid = [[3,0,3,0], [0,3,0,3], [3,0,3,0]], k = 3
输出：6
解释：网格包含六个岛屿，每个岛屿的总价值都能被 3 整除。

提示：

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 1000
  • 1 <= m * n <= 10^5
  • 0 <= grid[i][j] <= 10^6
  • 1 <= k <= 10^6

解题思路

这是一个典型的连通分量问题，需要找到所有岛屿并计算每个岛屿的总价值。

解题思路：

  1. 岛屿识别：岛屿由值大于0的相邻单元格组成，值为0的单元格代表水域
  2. 连通性遍历：使用DFS或BFS遍历每个连通分量（岛屿）
  3. 价值计算：在遍历过程中累加岛屿中所有单元格的值
  4. 整除判断：检查岛屿总价值是否能被k整除

算法步骤：

  • 遍历整个网格，对于每个未访问且值大于0的单元格，开始一次DFS/BFS
  • 在DFS过程中，标记访问过的单元格，并累加当前岛屿的总价值
  • DFS结束后，检查岛屿总价值是否能被k整除，如果能则计数加1
  • 继续遍历直到所有单元格都被访问

推荐使用DFS解法，因为实现相对简洁，且对于这种规模的问题性能足够。BFS和并查集也可以解决，但实现相对复杂。

代码实现

class Solution {
public:
    int countIslands(vector<vector<int>>& grid, int k) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        int result = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i][j] && grid[i][j] > 0) {
                    long long sum = 0;
                    dfs(grid, visited, i, j, sum);
                    if (sum % k == 0) {
                        result++;
                    }
                }
            }
        }
        
        return result;
    }
    
private:
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, 
             int i, int j, long long& sum) {
        int m = grid.size(), n = grid[0].size();
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j] == 0) {
            return;
        }
        
        visited[i][j] = true;
        sum += grid[i][j];
        
        dfs(grid, visited, i + 1, j, sum);
        dfs(grid, visited, i - 1, j, sum);
        dfs(grid, visited, i, j + 1, sum);
        dfs(grid, visited, i, j - 1, sum);
    }
};

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        result = 0
        
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or grid[i][j] == 0:
                return 0
            
            visited[i][j] = True
            total = grid[i][j]
            
            total += dfs(i + 1, j)
            total += dfs(i - 1, j)
            total += dfs(i, j + 1)
            total += dfs(i, j - 1)
            
            return total
        
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] > 0:
                    island_sum = dfs(i, j)
                    if island_sum % k == 0:
                        result += 1
        
        return result

public class Solution {
    public int CountIslands(int[][] grid, int k) {
        int m = grid.Length, n = grid[0].Length;
        bool[,] visited = new bool[m, n];
        int result = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (!visited[i, j] && grid[i][j] > 0) {
                    long sum = 0;
                    DFS(grid, visited, i, j, ref sum);
                    if (sum % k == 0) {
                        result++;
                    }
                }
            }
        }
        
        return result;
    }
    
    private void DFS(int[][] grid, bool[,] visited, int i, int j, ref long sum) {
        int m = grid.Length, n = grid[0].Length;
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i, j] || grid[i][j] == 0) {
            return;
        }
        
        visited[i, j] = true;
        sum += grid[i][j];
        
        DFS(grid, visited, i + 1, j, ref sum);
        DFS(grid, visited, i - 1, j, ref sum);
        DFS(grid, visited, i, j + 1, ref sum);
        DFS(grid, visited, i, j - 1, ref sum);
    }
}

var countIslands = function(grid, k) {
    const m = grid.length, n = grid[0].length;
    const visited = Array(m).fill().map(() => Array(n).fill(false));
    let result = 0;
    
    const dfs = (i, j) => {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || grid[i][j]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(m × n)需要遍历整个网格，每个单元格最多被访问一次
空间复杂度O(m × n)visited数组的空间开销，递归调用栈在最坏情况下深度为O(m × n)

相关题目