题目
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
[‘1′,’1′,’1′,’1′,’0’],
[‘1′,’1′,’0′,’1′,’0’],
[‘1′,’1′,’0′,’0′,’0’],
[‘0′,’0′,’0′,’0′,’0’]
]
输出：1
示例 2：
输入：grid = [
[‘1′,’1′,’0′,’0′,’0’],
[‘1′,’1′,’0′,’0′,’0’],
[‘0′,’0′,’1′,’0′,’0’],
[‘0′,’0′,’0′,’1′,’1’]
]
输出：3
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] 的值为 ‘0’ 或 ‘1’
我的代码（Python）
version 1
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
toBeChecked = []
islands = set()
cnt = 0
m = len(grid)
n = len(grid[0])
def findIsland(grid, m, n, islands) -> (int, int):
for i in range(m):
for j in range(n):
if (i, j) not in islands and grid[i][j] == '1':
return (i, j)
return (-1, -1)
tar = findIsland(grid, m, n, islands)
print(f'tar: {tar}')
while tar[0] != -1:
toBeChecked.append(tar)
while toBeChecked:
checkTar = toBeChecked.pop()
i, j = checkTar
# up
if i != 0:
if grid[i - 1][j] == '1':
if (i - 1, j) not in islands:
toBeChecked.append((i - 1, j))
# left
if j != 0:
if grid[i][j - 1] == '1':
if (i, j - 1) not in islands:
toBeChecked.append((i, j - 1))
# down
if i != m - 1:
if grid[i + 1][j] == '1':
if (i + 1, j) not in islands:
toBeChecked.append((i + 1, j))
# right
if j != n - 1:
if grid[i][j + 1] == '1':
if (i, j + 1) not in islands:
toBeChecked.append((i, j + 1))
islands.add(checkTar)
cnt += 1
tar = findIsland(grid, m, n, islands)
return cnt最直接的想法，暴力，超时了。
version 2
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
toBeChecked = []
cnt = 0
m = len(grid)
n = len(grid[0])
for ii in range(m):
for jj in range(n):
if grid[ii][jj] == '1':
toBeChecked.append((ii, jj))
while toBeChecked:
checkTar = toBeChecked.pop()
i, j = checkTar
grid[i][j] = '0'
# up
if i != 0:
if grid[i - 1][j] == '1':
toBeChecked.append((i - 1, j))
# left
if j != 0:
if grid[i][j - 1] == '1':
toBeChecked.append((i, j - 1))
# down
if i != m - 1:
if grid[i + 1][j] == '1':
toBeChecked.append((i + 1, j))
# right
if j != n - 1:
if grid[i][j + 1] == '1':
toBeChecked.append((i, j + 1))
cnt += 1
return cnt根据官方的解法做了优化，其实只优化了搜索的起点，然后把官方的递归用迭代的方式实现了。判断条件写得比较啰嗦，和官方用数组的解法是一样的。
点评
想法很容易，不过总觉得有更方便的解法，所以想得很复杂。
尝试了在已知一行的岛的情况下，再加一行如何变化，需要考虑连通性，不是不能实现，但是很复杂，肯定不是这个“中等”难度的题目应该有的，于是放弃了。
本来想着一个300*300的数组，即使每次从头开始搜索也不会太花时间，结果这部分做了优化后时间效率从超时变成靠前了。
总觉得有点意犹未尽……
baddif@gmail.com
AI简历优化站
AI求职跟踪器（建设中）
主站（建设中）
相关平台
Github Issues / Notion / Blog