Python LeetCode-200.数据结构 岛屿的个数 深
2019-04-04 本文已影响0人
Jayce_xi
在做这个题目的时候，可以先看下这篇文章python-数据结构 队列和广度优先搜索（BFS）
1.题目 岛屿的个数
给定一个由 "1"（陆地）和 "0"（水）组成的的二维网格(这里要注意 "1"和 "0"都是字符串)，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
Given a 2d grid map of "1" is (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.
2. 示例
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
2.三种结题方式
1.广度优先 （非递归的方式）其中有队列思想
参考出处
思路：
- 先看代码再看思路，这一版是参考别人的，下面有优化版。
- 利用一个
mark二位数组，标记已经被认定为岛屿的点，这些点就不会再去计数。 - 利用一个列表来做一个先进先出的队列，广度优先的寻找为"1"的点，将这些点都标记为
False -
广度优先查找的感觉类似这样
- 可以参考我的这篇文章，来理解队列在广度优先查找中的思想python-数据结构 队列和广度优先搜索（BFS）或者我的博客看看
class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def numIslands(self, grid):
# 特殊值检错
if not grid:
return 0
if isinstance(grid[0], bool) or isinstance(grid[0], int):
return 1 if grid[0] else 0
# Write your code here
count = 0 # 计数
# 行列数
m, n = len(grid), len(grid[0])
# 标记初始为True 扩展到的为False不再进行检测
mark = self._mark(m, n)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
if mark[i][j]: # 检查标记
count += 1
mark[i][j] = False
self._expand(i, j, grid, mark)
return count
@staticmethod
def _mark(m, n):
mark = []
for i in range(m):
mark.append([True] * n)
return mark
@staticmethod
def _expand(i, j, grid, mark):
# 向右向下扩展，广度优先,利用队列，进行广度优先查询
t = [(i, j)]
# 用于检查边界
m, n = len(grid), len(grid[0])
while len(t) != 0:
i, j = t.pop()
# 左
if i > 0:
if mark[i - 1][j]:
if grid[i - 1][j] == "1":
mark[i - 1][j] = False
t.append((i - 1, j))
# 右
if i < m - 1:
if mark[i + 1][j]:
if grid[i + 1][j] == "1":
mark[i + 1][j] = False
t.append((i + 1, j))
# 上
if j > 0:
if mark[i][j - 1]:
if grid[i][j - 1] == "1":
mark[i][j - 1] = False
t.append((i, j - 1))
# 下
if j < n - 1:
if mark[i][j + 1]:
if grid[i][j + 1] == "1":
mark[i][j + 1] = False
t.append((i, j + 1))
if __name__ == '__main__':
s = Solution()
g0 = []
g1 = [["0"]]
g2 = [["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]]
for g in [g0, g1, g2]:
print(s.numIslands(g))
2.广度优先优化版本（非递归，强调内存的重复利用）
思路
- 思想是和上一个完全一样的，但是利用了原来
grid的数据结构，节约了内存空间，这个思想在LeetCode中的很多题目都会体现，特别是在要求不使用额外的内存的算法题当中，类似这一题-->LeetCode-442-数组中重复的数据（难度-中等）
class Solution:
# @param {boolean[][]} grid a boolean 2D matrix
# @return {int} an integer
def numIslands(self, grid):
# 特殊值检错
if not grid:
return 0
if isinstance(grid[0], bool) or isinstance(grid[0], int):
return 1 if grid[0] else 0
# Write your code here
count = 0 # 计数
# 行列数
m, n = len(grid), len(grid[0])
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
count += 1
grid[i][j] = "0"
self._expand(i, j, grid)
return count
@staticmethod
def _expand(i, j, grid):
# 向右向下扩展，广度优先
t = [(i, j)] # 相当一个先进先出队列，进行广度优先查询
# 用于检查边界
m, n = len(grid), len(grid[0])
while len(t) != 0:
i, j = t.pop()
# 左
if i > 0:
if grid[i - 1][j] == "1":
grid[i - 1][j] = False
t.append((i - 1, j))
# 右
if i < m - 1:
if grid[i + 1][j] == "1":
grid[i + 1][j] = False
t.append((i + 1, j))
# 上
if j > 0:
if grid[i][j - 1] == "1":
grid[i][j - 1] = False
t.append((i, j - 1))
# 下
if j < n - 1:
if grid[i][j + 1] == "1":
grid[i][j + 1] = False
t.append((i, j + 1))
return grid
if __name__ == '__main__':
s = Solution()
g0 = []
g1 = [["0"]]
g2 = [["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]]
for g in [g0, g1, g2]:
print(s.numIslands(g))
3.深度优先解答（递归）
思路：
- 先大致浏览下代码再看思路
- 使用递归的思路，当一个点是"1"标记是岛屿的时候，将这个点置为"0"，且将它的上下左右四个点为"1"的也全部置"0"，且这四个点的上下左右接着进行查询是否有"1"，不断递归下去，直到遇到递归终止条件。
- 递归的终止条件为
i或者j到达边界（i >= len(grid) or j >= len(grid[0]) or i < 0 or j < 0）。递归最重要的就是找终止条件。
class Solution:
def numIslands(self, grid):
if grid is None or not grid or len(grid) == 0 or len(grid[0]) == 0: # 对于特殊值的处理
return 0
m = len(grid)
n = len(grid[0])
res = 0 # 判定岛屿的数量
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
res += 1
self.dfs(grid, i, j)
return res
def dfs(self, grid, i, j):
if i >= len(grid) or j >= len(grid[0]) or i < 0 or j < 0:
return
if grid[i][j] == "1":
grid[i][j] = "0"
self.dfs(grid, i + 1, j)
self.dfs(grid, i - 1, j)
self.dfs(grid, i, j + 1)
self.dfs(grid, i, j - 1)
if __name__ == '__main__':
s = Solution()
g0 = []
g1 = [["0"]]
g2 = [["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]]
for g in [g0, g1, g2]:
print(s.numIslands(g))
