200. Number of Islands
https://leetcode.com/problems/number-of-islands/
solution
flood fill
dfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
visited = [[False] * n for _ in range(m)]
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
res: int = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1' and not visited[i][j]:
res += 1
self.dfs(i, j, grid, dirs, visited)
return res
def dfs(self, i, j, grid, dirs, visited):
if grid[i][j] == '0' or visited[i][j]:
return
visited[i][j] = True
for dir in dirs:
new_i = i + dir[0]
new_j = j + dir[1]
if new_i < 0 or new_i >= len(grid) or new_j < 0 or new_j >= len(grid[0]):
continue
self.dfs(new_i, new_j, grid, dirs, visited) 时间复杂度：O(mn) 空间复杂度：O(mn)
class Solution:
def __init__(self):
self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
res = 0
m = len(grid)
n = len(grid[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 grid[i][j] == '0':
return
grid[i][j] = '0'
for d in self.dirs:
new_i = i + d[0]
new_j = j + d[1]
if 0 <= new_i < len(grid) and 0 <= new_j < len(grid[0]):
self.dfs(grid, new_i, new_j)bfs
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
n = len(grid[0])
res = 0
visited = [[False] * n for _ in range(m)]
dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
for i in range(m):
for j in range(n):
if visited[i][j] == False and grid[i][j] == '1':
res += 1
self.bfs(grid, i, j, visited, dirs, m, n)
return res
def bfs(self, grid, i, j, visited, dirs, m, n):
q = collections.deque([(i, j)])
visited[i][j] = True
while q:
i, j = q.popleft()
for dir in dirs:
new_i = i + dir[0]
new_j = j + dir[1]
if new_i >= 0 and new_i < m and new_j >= 0 and new_j < n and grid[new_i][new_j] == '1' and visited[new_i][new_j] == False:
q.append([new_i, new_j])
visited[new_i][new_j] = True时间复杂度：O(mn) 空间复杂度：O()
union find
follow up-岛屿类
大数据量: grid特别大，放不进内存，你怎么做？
union-find有巨大优势，可以一行一行的处理，这样每次读入内存两行数据就行
遍历图1为水、图2为岛的图2所有岛屿，标记为水；然后统计图2的岛屿
class Solution:
def __init__(self):
self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
m = len(grid1)
n = len(grid1[0])
for i in range(m):
for j in range(n):
if grid1[i][j] == 0 and grid2[i][j] == 1: # 注意这里的逻辑
self.dfs(i, j, grid2)
res = 0
for i in range(m):
for j in range(n):
if grid2[i][j] == 1:
res += 1
self.dfs(i, j, grid2)
return res
def dfs(self, i, j, grid2):
grid2[i][j] = 0
for dir in self.dirs:
new_i = i + dir[0]
new_j = j + dir[1]
if 0 <= new_i < len(grid2) and 0 <= new_j < len(grid2[0]) and grid2[new_i][new_j] == 1:
self.dfs(new_i, new_j, grid2)时间复杂度：O() 空间复杂度：O()
class Solution:
def __init__(self):
self.dirs = [(-1, 0), (0, -1), (0, 1), (1, 0)]
def largestIsland(self, grid: List[List[int]]) -> int:
n = len(grid)
islands = {}
def bfs(row, column, island_id):
queue = deque([(row, column, island_id)])
area = 1
visited.add((row, column)) # list is unhashable
while queue:
row, column, island_id = queue.pop()
islands[(row, column)] = island_id
for dir in self.dirs:
r = row + dir[0]
c = column + dir[1]
if 0 <= r < n and 0 <= c < n and grid[r][c] == 1 and (r, c) not in visited:
queue.append([r, c, island_id])
visited.add((r, c))
area += 1
return area
visited = set()
area = {}
island_id = 0
for row in range(n):
for column in range(n):
if grid[row][column] == 1 and (row, column) not in visited:
area[island_id] = bfs(row, column, island_id)
island_id += 1
if len(islands.keys()) == n**2: return n**2 # 特殊情况
largest_area = 1
for row in range(n):
for column in range(n):
if grid[row][column] == 1:
continue
neighbors = set() # 以要改变的0为基准，从四个方向中寻找邻居的island
this_area = 1
for dir in self.dirs:
r = row + dir[0]
c = column + dir[1]
if 0 <= r < n and 0 <= c < n and grid[r][c] == 1 and islands[(r, c)] not in neighbors:
neighbors.add(islands[(r, c)])
this_area += area[islands[(r, c)]]
largest_area = max(largest_area, this_area)
return largest_area时间复杂度：O() 空间复杂度：O()
时间复杂度：O() 空间复杂度：O()
1254. Number of Closed Islands
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
def dfs(i: int, j: int) -> None:
if i < 0 or i == m or j < 0 or j == n:
return
if grid[i][j] == 1:
return
grid[i][j] = 1
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
# Remove the lands connected to the edge.
for i in range(m):
for j in range(n):
if i * j == 0 or i == m - 1 or j == n - 1:
if grid[i][j] == 0:
dfs(i, j)
ans = 0
# Reduce to 200. Number of Islands
for i in range(m):
for j in range(n):
if grid[i][j] == 0:
dfs(i, j)
ans += 1
return ans时间复杂度：O() 空间复杂度：O()
有case不通过的错误做法, 还没去找原因
class Solution:
def __init__(self):
self.dirs = [[1, 0], [0, 1], [-1, 0], [0, -1]]
def closedIsland(self, grid: List[List[int]]) -> int:
m = len(grid)
n = len(grid[0])
if m < 3 or n < 3:
return 0
visited = [[False] * n for _ in range(m)]
res = 0
# 去掉最外圈后开始循环查找
for i in range(1, m - 1):
for j in range(1, n - 1):
if visited[i][j]:
continue
if grid[i][j] == 0:
if self.dfs(grid, i, j, visited):
res += 1
return res
def dfs(self, grid, i, j, visited):
visited[i][j] = True
for x, y in self.dirs:
move_x = i + x
move_y = j + y
if move_x < 0 or move_x >= len(grid) or move_y < 0 or move_y >= len(grid[0]):
return False
if not visited[move_x][move_y] and grid[move_x][move_y] == 0:
self.dfs(grid, move_x, move_y, visited)
return True# 记录岛屿cell数量与neighbour数量 -> 引申题目, 求最大周长的岛屿
# 注意: neighbor是一个双向关系，定义好哪个cell的时候求即可
时间复杂度：O() 空间复杂度：O()
Last updated