Number of Islands
你会得到一个由等长字符串组成的列表，用来表示地图，其中 '1' 表示一格陆地，'0' 表示一格水域。上下左右相邻的陆地格属于同一座岛屿。仅在角上相接的格子不相连。返回岛屿的数量。
函数
- gridstring-array
- 地图，每行一个字符串
- 返回值integer
- 岛屿数量
约束条件
1 ≤ grid.length ≤ 1501 ≤ grid[i].length ≤ 150- 每一行的长度都相同。
- 每个字符都是
'0'或'1'。
示例
- 输入
- grid = ["11000", "11000", "00100", "00011"]
- 输出
- 3
- 解释
- 左上角的四个方格组成一个岛屿。第三行中间的方格只在角上与它们相连，因此它是第二个岛屿。右下角的两个方格组成第三个岛屿。
- 输入
- grid = ["01110", "01000", "00011", "11001"]
- 输出
- 3
- 解释
- 顶行的三个方格和其左端下方的一个方格组成一个岛。第三行右侧的两个方格向下连接到底行最右侧的方格，组成第二个岛。底行左侧的两个方格是第三个岛。
进阶
现在，地图上的水域中会逐个出现陆地格子。每出现一个新格子，你能在不重新扫描整张地图的情况下，报告岛屿的数量吗？
提示
逐个打开提示，每个都会多透露一点。
逐格扫描地图。当你到达一个尚未被之前的岛屿占据的陆地格子时，你发现了多少个新岛屿？
找到一座新岛屿后，访问与它相连的每个陆地格子，并将它们标记为已查看，这样扫描时就不会重复计算同一座岛屿。
使用队列进行广度优先搜索，或使用显式栈进行深度优先搜索，遍历尚未访问的方格。如果地图上有一座巨大的岛屿，递归搜索可能会耗尽调用栈，而使用自己的队列或栈进行循环则不会。
题解
把每个陆地格看作一个节点，并与相邻的陆地格相连：一个岛屿就是一片连通的区域。扫描地图，每当你遇到一块尚未访问过的陆地，就将岛屿数量加一，并对它进行洪泛填充，标记其中的每个格子，这样扫描时就不会再次计数。
使用显式栈进行泛洪填充（深度优先搜索）
思路
一个未标记的陆地格子不可能属于你已经统计过的岛屿，因为统计岛屿时会标记整座岛。因此，它会开始一座新岛屿。你自己管理的栈会标记其余部分：每次弹出一个格子，就把它未标记的陆地邻居压入栈中；栈为空时，整座岛屿就都被标记了。
自己管理栈很重要，因为在一张全是陆地的 150 × 150 地图上，递归填充可能深入 22,500 层。每个格子最多入栈一次，并检查四个邻居，因此时间复杂度为 O(rows × cols)。当地图全是陆地时，标记和栈占用 O(rows × cols) 的空间。
算法
- 为每个方格创建一个已访问标记，并将计数设为 0。
- 扫描每个方格，跳过水域和已经访问过的方格。
- 遇到未访问过的陆地时，将计数加 1，标记该方格，并将它压入栈中。
- 当栈不为空时，弹出一个方格，并将地图内每个未访问过的陆地邻格标记后压入栈中。
- 扫描结束后返回计数。
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
# Land that no island has claimed yet: a new island.
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
# Mark on push, so no square enters the stack twice.
seen[ni][nj] = True
stack.append((ni, nj))
return count使用队列进行泛洪填充（BFS）
思路
计数方式相同，只有访问顺序会改变。队列从前端取出方格，并将未标记的陆地邻格添加到后端，因此它会按环状顺序访问岛屿：先访问第一个方格，然后访问距离它一步的所有方格，再访问距离它两步的所有方格。每个方格仍只会被访问一次，时间和空间复杂度均为 O(rows × cols)。
环状顺序会给出每个方格到起点的距离，因此，只需为每个方格额外记录一个数字，同一个循环就能解答网格上的最短路径问题。
算法
- 为每个方格创建一个已访问标记，并将计数设为 0。
- 扫描每个方格，跳过水域和已访问的方格。
- 遇到未访问的陆地方格时，将计数加 1，标记该方格，并将它放入一个空队列。
- 只要队列中还有方格，就从队首取出一个，并将地图范围内每个未访问的陆地邻格加入队尾，同时标记这些方格。
- 扫描结束时返回计数。
def numIslands(grid):
rows, cols = len(grid), len(grid[0])
seen = [[False] * cols for _ in range(rows)]
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] != '1' or seen[r][c]:
continue
count += 1
seen[r][c] = True
stack = [(r, c)]
while stack:
i, j = stack.pop()
for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
seen[ni][nj] = True
stack.append((ni, nj))
return count
易错点和边界情况
- 在把方格放入栈或队列时，而不是取出时标记它。这样同一个方格就会被放入多次。
- 将方格与数字 1 比较，而不是与字符
'1'比较。每一行都是字符串，因此每个方格都是一个字符。 - 在检查
0 ≤ row < rows和0 ≤ col < cols之前就读取相邻方格。这样，边缘上的陆地格子就会读取地图外的内容。 - 用递归编写填充算法。Python 默认会在调用 1,000 次后停止，其他语言也可能在遇到一个大型岛屿时发生栈溢出。
- 使用
pop(0)取出 Python 列表的第一个元素，这会花费与列表长度成正比的时间。请使用collections.deque和popleft()。
常见问题4
岛屿数量的时间复杂度是多少？
O(rows × cols)。扫描会遍历每个方格一次，每个陆地方格只会进入栈或队列一次，并检查四个相邻方格。如果地图全是陆地，已访问标记和栈或队列会占用 O(rows × cols) 的空间。
求解岛屿数量时，应该使用 BFS 还是 DFS？
两者的时间和空间复杂度相同，而且都是正确的，因为计数只需要标记岛屿中的每个方格。使用队列的 BFS 不会进行递归；使用显式栈时，DFS 同样安全。
你能用并查集解决岛屿数量问题吗？
是的。将每个陆地格子分别放入一个集合，并将计数设为陆地格子的数量。合并每一对相邻的陆地格子；每当合并连接了两个不同的集合，就将计数减一。使用路径压缩后，时间复杂度接近 O(rows × cols)。
你能不使用单独的已访问数组来统计岛屿吗？
可以，如果你可以修改地图：每到达一个陆地格子，就立即把它变成水。许多语言无法原地修改字符串，所以你要先把各行复制到字符网格中，这会占用与已访问标记相同的空间。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def numIslands(grid):
# 在这里编写代码测试 #1
测试 #2
参数
grid = ["11000", "11000", "00100", "00011"]
预期输出
3