吴良超的学习笔记

LeetCode解题报告(200,130)--图的孤立子图

200. Number of Islands题目描述如下:

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

11110
11010
11000
00000

Answer: 1

上面的问题是一个经典的图论问题,需要求孤立的岛屿的个数,而岛屿仅可通过上下左右来连接,这种问题可以通过深度优先搜索(DFS)或广度优先搜索(BFS)来解决,每次遇到一个没访问过的岛屿就对当前岛屿进行DFS或DFS,并记录这个过程中访问过的岛屿,直至最终所有岛屿都被访问

采用DFS的的python代码如下所示:

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
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""

if len(grid) == 0: return 0
m, n, result = len(grid), len(grid[0]), 0
visited = [[0 for j in xrange(n)] for i in xrange(m)]
for i in xrange(m):
for j in xrange(n):
if grid[i][j] == '1' and visited[i][j] == 0:
self.dfs(grid, visited, i, j)
result += 1
return result

def dfs(self, grid, visited, i, j):
visited[i][j] = 1
m, n = len(grid), len(grid[0])
if 0<= i-1 <m and grid[i-1][j] == '1' and visited[i-1][j] == 0:
self.dfs(grid, visited, i-1, j)
if 0<= i+1 <m and grid[i+1][j] == '1' and visited[i+1][j] == 0:
self.dfs(grid, visited, i+1, j)
if 0<= j-1 <n and grid[i][j-1] == '1' and visited[i][j-1] == 0:
self.dfs(grid, visited, i, j-1)
if 0<= j+1 <n and grid[i][j+1] == '1' and visited[i][j+1] == 0:
self.dfs(grid, visited, i, j+1)

假如将上面的题目改为一个岛屿邻接的岛屿除了上下左右,还有左上、左下、右上、右下,也就是有八个可能连接的地方,那么答案该如何修改?

实际上方法也很简单,对上面代码中的dfs方法增加检查左上、左下、右上、右下这四个点的代码即可。

上面的DFS中利用了visited数组检查某个点是否已经被访问过,空间复杂度为O(m*n)。实际上在原来的grid可修改的情况下,可以通过修改grid中的值为’1’,’0’以外的值,从而使得空间复杂度为O(1)。下面的BFS方法利用了这点

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
from collections import deque
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""

m = len(grid)
if m == 0:
return 0
n = len(grid[0])
count = 0
for i in xrange(m):
for j in xrange(n):
if grid[i][j] == '1':
self.bfs(i, j, grid)
count += 1
return count
def bfs(self, row, col, grid):
m, n = len(grid), len(grid[0])
que = deque()
que.append((row, col))
grid[row][col] = '2'
while que:
row, col = que.popleft()
if row>0 and grid[row-1][col]=='1':
que.append((row-1, col))
grid[row-1][col] = '2'
if row<m-1 and grid[row+1][col] == '1':
que.append((row+1, col))
grid[row+1][col] = '2'
if col>0 and grid[row][col-1]=='1':
que.append((row, col-1))
grid[row][col-1] = '2'
if col<n-1 and grid[row][col+1] == '1':
que.append((row, col+1))
grid[row][col+1] = '2'

此外,130. Surrounded Regions跟上面的题目也类似,只是需要对边上的点进行BFS或DFS,具体代码见这里