Leetcode 200:岛屿的个数(最详细的解法!!!)

给定一个由 '1'(陆地)和 '0'(水)组成的的二维网格,计算岛屿的数量。一个岛被水包围,并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

1
2
3
4
5
6
7
输入:
11110
11010
11000
00000

输出: 1

示例 2:

1
2
3
4
5
6
7
输入:
11000
11000
00100
00011

输出: 3

解题思路

这个问题实际上和之前的问题Leetcode 79:单词搜索(最详细的解法!!!)类似,应该说是一模一样。所以我们直接在前面一个问题的基础上稍微修改一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution:
def _numIslands(self, grid, x, y, visited):
d = [(-1, 0), (0, 1), (1, 0), (0, -1)]
def inArea(x, y):
return x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0])

visited[x][y] = True
for i in range(4):
x_ = x + d[i][0]
y_ = y + d[i][1]
if inArea(x_, y_) and not visited[x_][y_] and grid[x_][y_] == '1':
self._numIslands(grid, x_, y_, visited)

def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
visited = list()
for val in grid:
t = list()
for _ in val:
t.append(False)

visited.append(t)

result = 0
for i, val in enumerate(grid):
for j, _ in enumerate(val):
if grid[i][j] == '1' and not visited[i][j]:
result += 1
self._numIslands(grid, i, j, visited)

return result

这个问题比上一个问题特殊,我们没法针对问题得到先验知识,所以我们无法在算法的初始对算法进行优化。难道就没什么优化了吗?有。我们不使用visited记录访问过的元素,而是通过对已访问过的元素直接赋0的方式,因为我们知道已访问过的元素,我们不会再访问了。这是一步非常强力的优化。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0

result = 0
m, n = len(grid), len(grid[0])
for row in range(m):
for col in range(n):
if grid[row][col] == '1':
result += 1
self._numIslands(grid, row, col)

return result

def _numIslands(self, grid, r, c):
grid[r][c] = '0'
if 0 < r and grid[r - 1][c] == '1':
self._numIslands(grid, r - 1,c)

if 0 < c and grid[r][c - 1] == '1':
self._numIslands(grid, r, c - 1)

if c < len(grid[0]) -1 and grid[r][c + 1] =='1':
self._numIslands(grid, r, c + 1)

if r < len(grid) - 1 and grid[r + 1][c] == '1':
self._numIslands(grid, r + 1, c)

很多人注意到了我上面没有使用for i in range(4)这种写法,实际上我在之前的问题c++版本中也是采用了上面这种写法。为什么呢?因为这样更快。

同样的,对于递归解决的问题,我们都应该思考一下怎么通过迭代去解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution:
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0

result = 0
m, n = len(grid), len(grid[0])

def _numIslands(grid, r, c):
if grid[r][c] != '1':
return

stack = list()
stack.append((r, c))
while stack:
x, y = stack.pop()
if grid[x][y] != '1':
continue

grid[x][y] = '0'
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
for d in directions:
nr = x + d[0]
nc = y + d[1]
if 0 <= nr < m and 0 <= nc < n:
stack.append((nr, nc))

for row in range(m):
for col in range(n):
if grid[row][col] == '1':
result += 1
_numIslands(grid, row, col)

return result

我们只要将self._numIslands写成迭代形式即可。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!