What is the primary algorithm used to solve the Count Islands With Total Value Divisible by K problem?

The problem is primarily solved using Depth-First Search (DFS) or Breadth-First Search (BFS) to find connected components (islands) in the grid.

How do I check if an island's total value is divisible by k?

Once an island is identified, sum the values of all its cells and check if the sum modulo k equals zero.

Can I solve the Count Islands With Total Value Divisible by K problem using a different approach?

Yes, you can use the Union-Find algorithm instead of DFS/BFS for finding connected components in the grid.

What is the time complexity for solving the Count Islands With Total Value Divisible by K problem?

The time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid.

What common mistake should I avoid when solving this problem?

A common mistake is forgetting to mark cells as visited during DFS/BFS, which could result in counting the same island multiple times.

#3619

Medium

auto_awesome图·搜索

LeetCode 题解工作台

总价值可以被 K 整除的岛屿数目

给你一个 m x n 的矩阵 grid 和一个正整数 k 。一个岛屿是由正整数（表示陆地）组成的，并且陆地间四周连通（水平或垂直）。一个岛屿的总价值是该岛屿中所有单元格的值之和。返回总价值可以被 k 整除的岛屿数量。示例 1: 输入: grid = [[0,2,1,0,0],[0…

数组深度优先搜索广度优先搜索并查集矩阵

题目描述

给你一个 m x n 的矩阵 grid 和一个正整数 k。一个岛屿是由正整数（表示陆地）组成的，并且陆地间四周连通（水平或垂直）。

一个岛屿的总价值是该岛屿中所有单元格的值之和。

返回总价值可以被 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⁵
0 <= grid[i][j] <= 10⁶
1 <= k < = 10⁶

lightbulb

解题思路

方法一：DFS

我们定义一个函数 $\textit{dfs}(i, j)$ ，它从位置 $(i, j)$ 开始进行 DFS 遍历，并且返回该岛屿的总价值。我们将当前位置的值加入总价值，然后将该位置标记为已访问（例如，将其值设为 0）。接着，我们递归地访问四个方向（上、下、左、右）的相邻位置，如果相邻位置的值大于 0，则继续进行 DFS，并将其值加入总价值。最后，我们返回总价值。

在主函数中，我们遍历整个网格，对于每个未访问的位置 $(i, j)$ ，如果其值大于 0，则调用 $\textit{dfs}(i, j)$ 来计算该岛屿的总价值。如果总价值可以被 $k$ 整除，则将答案加一。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m \times n)$ 。其中 $m$ 和 $n$ 分别是网格的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

class Solution:
    def countIslands(self, grid: List[List[int]], k: int) -> int:
        def dfs(i: int, j: int) -> int:
            s = grid[i][j]
            grid[i][j] = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                if 0 <= x < m and 0 <= y < n and grid[x][y]:
                    s += dfs(x, y)
            return s

        m, n = len(grid), len(grid[0])
        dirs = (-1, 0, 1, 0, -1)
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] and dfs(i, j) % k == 0:
                    ans += 1
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate understands how to identify islands using DFS/BFS.
question_mark
Candidate calculates the total value of islands correctly.
question_mark
Candidate can handle large grid sizes efficiently with proper space-time complexity analysis.

warning

常见陷阱

外企场景

error
Forgetting to mark cells as visited, causing redundant calculations.
error
Not correctly handling islands that touch the grid boundaries.
error
Incorrectly summing the values of an island, leading to wrong divisibility checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Using Union-Find to track connected components instead of DFS/BFS.
arrow_right_alt
Using different grid traversal techniques like spiral or wave traversal.
arrow_right_alt
Handling negative or zero values in the grid while adjusting divisibility checks.

help

常见问题

外企场景

继续练习

#2658 网格图中鱼的最大数目 #3607 电网维护 #3493 属性图