第五章 - 高频考题(中等)
1906. 查询差绝对值的最小值
0200. 岛屿数量

题目地址(200. 岛屿数量)

题目描述

1
给你一个由 '1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
2
3
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
4
5
此外,你可以假设该网格的四条边均被水包围。
6
7
8
9
示例 1:
10
11
输入:grid = [
12
["1","1","1","1","0"],
13
["1","1","0","1","0"],
14
["1","1","0","0","0"],
15
["0","0","0","0","0"]
16
]
17
输出:1
18
示例 2:
19
20
输入:grid = [
21
["1","1","0","0","0"],
22
["1","1","0","0","0"],
23
["0","0","1","0","0"],
24
["0","0","0","1","1"]
25
]
26
输出:3
27
28
29
提示:
30
31
m == grid.length
32
n == grid[i].length
33
1 <= m, n <= 300
34
grid[i][j] 的值为 '0' 或 '1'
Copied!

前置知识

  • DFS

公司

  • 阿里
  • 腾讯
  • 百度
  • 字节

思路

如图,我们其实就是要求红色区域的个数,换句话说就是求连续区域的个数。
200.number-of-islands
符合直觉的做法是用 DFS 来解:
  • 我们需要建立一个 visited 数组用来记录某个位置是否被访问过。
  • 对于一个为 1 且未被访问过的位置,我们递归进入其上下左右位置上为 1 的数,将其 visited 变成 true。
  • 重复上述过程
  • 找完相邻区域后,我们将结果 res 自增 1,然后我们在继续找下一个为 1 且未被访问过的位置,直至遍历完.
但是这道题目只是让我们求连通区域的个数,因此我们其实不需要额外的空间去存储 visited 信息。 注意到上面的过程,我们对于数字为 0 的其实不会进行操作的,也就是对我们“没用”。 因此对于已经访问的元素, 我们可以将其置为 0 即可。

关键点解析

  • 二维数组 DFS 解题模板
  • 将已经访问的元素置为 0,省去 visited 的空间开销

代码

  • 语言支持:C++, Java, JS, python3
C++ Code:
1
class Solution {
2
public:
3
int numIslands(vector<vector<char>>& grid) {
4
int res = 0;
5
for(int i=0;i<grid.size();i++)
6
{
7
for(int j=0;j<grid[0].size();j++)
8
{
9
if(grid[i][j] == '1')
10
{
11
dfs(grid, i, j);
12
res += 1;
13
}
14
}
15
}
16
return res;
17
18
}
19
void dfs(vector<vector<char>>& grid, int i, int j)
20
{
21
// edge
22
if(i<0 || i>= grid.size() || j<0 || j>= grid[0].size() || grid[i][j] != '1')
23
{
24
return;
25
}
26
grid[i][j] = '0';
27
dfs(grid, i+1, j);
28
dfs(grid, i-1, j);
29
dfs(grid, i, j+1);
30
dfs(grid, i, j-1);
31
}
32
};
Copied!
Java Code:
1
public int numIslands(char[][] grid) {
2
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
3
4
int count = 0;
5
for (int row = 0; row < grid.length; row++) {
6
for (int col = 0; col < grid[0].length; col++) {
7
if (grid[row][col] == '1') {
8
dfs(grid, row, col);
9
count++;
10
}
11
}
12
}
13
return count;
14
}
15
16
private void dfs(char[][] grid,int row,int col) {
17
if (row<0||row== grid.length||col<0||col==grid[0].length||grid[row][col]!='1') {
18
return;
19
}
20
grid[row][col] = '0';
21
dfs(grid, row-1, col);
22
dfs(grid, row+1, col);
23
dfs(grid, row, col+1);
24
dfs(grid, row, col-1);
25
}
Copied!
Javascript Code:
1
/*
2
* @lc app=leetcode id=200 lang=javascript
3
*
4
* [200] Number of Islands
5
*/
6
function helper(grid, i, j, rows, cols) {
7
if (i < 0 || j < 0 || i > rows - 1 || j > cols - 1 || grid[i][j] === "0")
8
return;
9
10
grid[i][j] = "0";
11
12
helper(grid, i + 1, j, rows, cols);
13
helper(grid, i, j + 1, rows, cols);
14
helper(grid, i - 1, j, rows, cols);
15
helper(grid, i, j - 1, rows, cols);
16
}
17
/**
18
* @param {character[][]} grid
19
* @return {number}
20
*/
21
var numIslands = function (grid) {
22
let res = 0;
23
const rows = grid.length;
24
if (rows === 0) return 0;
25
const cols = grid[0].length;
26
for (let i = 0; i < rows; i++) {
27
for (let j = 0; j < cols; j++) {
28
if (grid[i][j] === "1") {
29
helper(grid, i, j, rows, cols);
30
res++;
31
}
32
}
33
}
34
return res;
35
};
Copied!
python code:
1
class Solution:
2
def numIslands(self, grid: List[List[str]]) -> int:
3
if not grid: return 0
4
5
count = 0
6
for i in range(len(grid)):
7
for j in range(len(grid[0])):
8
if grid[i][j] == '1':
9
self.dfs(grid, i, j)
10
count += 1
11
12
return count
13
14
def dfs(self, grid, i, j):
15
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
16
return
17
grid[i][j] = '0'
18
self.dfs(grid, i + 1, j)
19
self.dfs(grid, i - 1, j)
20
self.dfs(grid, i, j + 1)
21
self.dfs(grid, i, j - 1)
Copied!
复杂度分析
  • 时间复杂度:$O(m * n)$
  • 空间复杂度:$O(m * n)$
欢迎关注我的公众号《脑洞前端》获取更多更新鲜的 LeetCode 题解

相关题目