闲着没事(误)开始刷题了，突然觉得自己的算法基础真的是太差了，有时间的时候还是刷刷题目吧。
最近一直用 Python ，所以刷题也继续用了。今天做的都是简单题，简单题中比较难的就刷到一道“岛屿的个数”问题。
题目
描述：
给一个01矩阵，求不同的岛屿的个数。
0代表海，1代表岛，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
样例输入：
[
[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]
]
样例输出：3
总结
总体思路
- 设置一个同大小的标记矩阵 mark ，初始全为 True
- 设置一个计数变量 count
- 按行列遍历 元素为 True 时将对应标记为 False，count+1
- 对于此元素的前后左右进行检查并标记，为 True 时加入列表，按广度优先的方式继续检查直至到达边界
- 继续遍历至结束，注意各种对grid和mark相应的检查
踩到的坑
- 特殊值如
grid = [] or [1] - grid 并不是方阵，行列数可能不一致
- 对周围元素的检查应当不只是右后，而是上下左右，使用队列可以实现广度优先的检查以便向周围扩展，在编码时注意对 grid 和 mark 的各种检查
- 二维数组的浅拷贝问题，可以看这篇
实现代码
# coding: utf-8
# http://www.lintcode.com/zh-cn/problem/number-of-islands/
# 岛屿的个数
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 # 计数
# 行列数
r, l = len(grid), len(grid[0])
# 标记初始为True 扩展到的为False不再进行检测
mark = self._mark(r, l)
for i in range(r):
for j in range(l):
if grid[i][j]:
if mark[i][j]: # 检查标记
count += 1
mark[i][j] = False # 有必要？
self._expand(i, j, grid, mark)
return count
def _mark(self, r, l):
mark = []
for i in range(r):
mark.append([True] * l)
return mark
def _expand(self, x, y, grid, mark):
# 向右向下扩展，广度优先
t = [(x, y)]
# 用于检查边界
r, l = 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]:
mark[i-1][j] = False
t.append((i-1, j))
# 右
if i < r - 1:
if mark[i+1][j]:
if grid[i+1][j]:
mark[i+1][j] = False
t.append((i+1, j))
# 上
if j > 0:
if mark[i][j-1]:
if grid[i][j-1]:
mark[i][j-1] = False
t.append((i, j-1))
# 下
if j < l - 1:
if mark[i][j+1]:
if grid[i][j+1]:
mark[i][j+1] = False
t.append((i, j+1))
if __name__ == '__main__':
g0 = []
g1 = [1]
g2 = [0]
g3 = [[0]]
g4 = [
[1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 0, 1],
[1, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1]]
g5 = [[1, 1, 0, 0, 0],
[0, 1, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 1]]
s = Solution()
for g in [g0, g1, g2, g3, g4, g5]:
print s.numIslands(g)
