4.1 DFS
3004字约10分钟
LeetcodePython
2024-12-17
提示
适用于需要计算连通块个数、大小的题目。
部分题目也可以用 BFS 或并查集解决。
阿囧:挺像扫雷的(
class Solution: def numIslands(self, grid: List[List[str]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != '1': # 地图外面或者非陆地就返回 return grid[i][j] = '2' # 是陆地,插旗 dfs(i - 1, j) # 其他四个方向走走 dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) res = 0 for i, row in enumerate(grid): for j, c in enumerate(row): if c == '1': # 发现岛屿 res += 1 dfs(i, j) # 占领此岛,插满旗子 '2' return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1: return 0 grid[i][j] = 2 return 1 + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1) res = 0 for i, row in enumerate(grid): for j, c in enumerate(row): if grid[i][j] == 1: res = max(res, dfs(i, j)) return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
注意此题是 8 方向,这题才是扫雷,but who care ? 一力破万法
class Solution: def pondSizes(self, land: List[List[int]]) -> List[int]: m, n = len(land), len(land[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or land[i][j] != 0: return 0 land[i][j] = 1 return 1 + dfs(i - 1, j - 1) + dfs(i - 1, j) + dfs(i - 1, j + 1) + dfs(i, j - 1) + dfs(i, j + 1) + dfs(i + 1, j - 1) + dfs(i + 1, j) + dfs(i + 1, j + 1) res = [] for i, row in enumerate(land): for j, c in enumerate(row): if land[i][j] == 0: res.append(dfs(i, j)) res.sort() return res
时间复杂度:O(mn),其中 m 和 n 分别为 land 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
class Solution: def largestArea(self, grid: List[str]) -> int: grid = [list(i) for i in grid] m, n = len(grid), len(grid[0]) def dfs(i,j): nonlocal now if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] == '0': # 外面和里面0元素 return float('-inf') if grid[i][j]== now: # 现在只剩下里面非0元素,找到是同一主题的 grid[i][j] = "6" return dfs(i+1,j) + dfs(i-1,j)+ dfs(i,j-1)+dfs(i,j+1) + 1 else: return 0 res = 0 for i, row in enumerate(grid): for j, c in enumerate(row): now = grid[i][j] if c != '0' and c != '6': res = max(res, dfs(i, j)) return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
class Solution: def findMaxFish(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >=m or j >= n or grid[i][j] <= 0: return 0 fish = grid[i][j] grid[i][j] = -1 return fish + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1) res = 0 for i, row in enumerate(grid): for j, c in enumerate(row): if c > 0: res = max(res, dfs(i, j)) return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
class Solution: def findMaxFish(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >=m or j >= n or grid[i][j] <= 0: return 0 fish = grid[i][j] grid[i][j] = -1 return fish + dfs(i - 1, j) + dfs(i + 1, j) + dfs(i, j - 1) + dfs(i, j + 1) res = 0 for i, row in enumerate(grid): for j, c in enumerate(row): if c > 0: res = max(res, dfs(i, j)) return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
class Solution: def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) -> List[List[int]]: visited = set() border = [] target = grid[row][col] m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != target: # 不是连通的,返回False return False if (i, j) in visited: return True visited.add((i, j)) is_border = False # 默认不是边界 for (x, y) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]: # 遍历上下左右 if x < 0 or y < 0 or x >= m or y >= n or grid[x][y] != target: is_border = True # 如果旁边越界或者是其他颜色了,说明是边界 else: if dfs(x, y): # 如果是连通的,遍历他 continue if is_border: border.append((i, j)) return True # 是连通的 dfs(row, col) for i, j in border: grid[i][j] = color return grid
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
思路:直接遍历矩阵的边界,发现陆地,就去dfs,把与其相连的陆地(包括边界自己)都变成海洋,最后统计矩阵中剩余的陆地就是答案
class Solution: def numEnclaves(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid[i][j] != 1: # 外面和非1 return grid[i][j] = 0 dfs(i - 1, j) dfs(i + 1, j) dfs(i, j - 1) dfs(i, j + 1) for i in range(m): if grid[i][0]: dfs(i, 0) if grid[i][n - 1]: dfs(i, n - 1) for j in range(n): if grid[0][j]: dfs(0, j) if grid[m - 1][j]: dfs(m - 1, j) return sum(sum(g) for g in grid)
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
class Solution: def maxMoves(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): nonlocal res res = max(res, j) if j == n - 1: return for k in i - 1, i, i + 1: if 0 <= k < m and grid[k][j + 1] > grid[i][j]: dfs(k, j + 1) grid[i][j] = 0 # 避免下面的走重复的路 res = 0 for i in range(m): dfs(i, 0) return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
有点意思,方法一:用一个变量标记本次遍历是否是边界,不是边界才加一
class Solution: def closedIsland(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) def dfs(i, j): nonlocal is_close if i < 0 or j < 0 or i >= m or j >= n: is_close = False return if grid[i][j] != 0: return grid[i][j] = 2 for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): dfs(x, y) res = 0 for i, row in enumerate(grid): for j, c in enumerate(row): is_close = True if c == 0: dfs(i, j) if is_close: res += 1 return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
方法二:先外后内,把边界上连通的都变成海洋,再去正常二重 for 循环
class Solution: def closedIsland(self, grid: List[List[int]]) -> int: m, n = len(grid), len(grid[0]) if m < 3 or n < 3: return 0 def dfs(x: int, y: int) -> None: grid[x][y] = 1 # 标记 (x,y) 被访问,避免重复访问 # 访问四方向的 0 for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1): if 0 <= i < m and 0 <= j < n and grid[i][j] == 0: dfs(i, j) for i in range(m): # 如果是第一行和最后一行,访问所有格子 # 如果不是,只访问第一列和最后一列的格子 step = 1 if i == 0 or i == m - 1 else n - 1 for j in range(0, n, step): if grid[i][j] == 0: # 从没有访问过的 0 出发 dfs(i, j) ans = 0 for i in range(1, m - 1): for j in range(1, n - 1): if grid[i][j] == 0: # 从没有访问过的 0 出发 ans += 1 # 一定是封闭岛屿 dfs(i, j) return ans
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
从边界出发,先把边界上和 O 连通点找到, 把这些变成 B,然后遍历整个 board 把 O 变成 X, 把 B 变成 O
class Solution: def solve(self, board: List[List[str]]) -> None: """ Do not return anything, modify board in-place instead. """ m, n = len(board), len(board[0]) is_x = [["X"] * n for _ in range(m)] def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or board[i][j] != "O": return is_x[i][j] = "O" board[i][j] = "B" for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): dfs(x, y) for i in range(m): if board[i][0] == 'O': dfs(i, 0) if board[i][n - 1] == 'O': dfs(i, n - 1) for j in range(n): if board[0][j] == 'O': dfs(0, j) if board[m - 1][j] == 'O': dfs(m - 1, j) for i, row in enumerate(board): for j, c in enumerate(row): if c == "O": board[i][j] = "X" elif c == "B": board[i][j] = "O"
时间复杂度:O(mn),其中 m 和 n 分别为 board 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
思路:正常
dfs
遍历 grid2 ,每次遍历陆地grid2[i][j]
的时候要去查询一下grid1[i][j]
是不是陆地,如果grid1[i][j]
不是陆地,那么is_islands
设置为False
,不计入岛屿总和res
。class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: m, n = len(grid1), len(grid1[0]) def dfs(i, j): if i < 0 or j < 0 or i >= m or j >= n or grid2[i][j] != 1: return grid2[i][j] = 2 nonlocal is_islands if grid1[i][j] == 0: is_islands = False for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): dfs(x, y) res = 0 for i, row in enumerate(grid2): for j, c in enumerate(row): if c == 1: is_islands = True dfs(i, j) if is_islands: res += 1 return res
时间复杂度:O(mn),其中 m 和 n 分别为 grid1 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。
思路:开辟和二维矩阵
grid
一样大的二维矩阵is_arrive
来存放哪些地方可以到达,初始全False
,写一个connect
函数判断下一个位置(x, y)
和当前是否连通,如果连通且未访问过,那么进入dfs
,最后返回is_arrive
的最后一个点的真值即可。class Solution: def hasValidPath(self, grid: List[List[int]]) -> bool: m, n = len(grid), len(grid[0]) is_arrive = [[False] * n for _ in range(m)] def dfs(i, j): is_arrive[i][j] = True for x, y in (i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1): if 0 <= x < m and 0 <= y < n and connect(i, j, x, y) and not is_arrive[x][y]: dfs(x, y) def connect(i, j, x, y): if x == i + 1 and grid[i][j] in [2, 3, 4] and grid[x][y] in [2, 5, 6]: return True if x == i - 1 and grid[i][j] in [2, 5, 6] and grid[x][y] in [2, 3, 4]: return True if y == j + 1 and grid[i][j] in [1, 4, 6] and grid[x][y] in [1, 3, 5]: return True if y == j - 1 and grid[i][j] in [1, 3, 5] and grid[x][y] in [1, 4, 6]: return True return False dfs(0, 0) return is_arrive[-1][-1]
时间复杂度:O(mn),其中 m 和 n 分别为 grid 的行数和列数。
空间复杂度:O(mn)。最坏情况下,递归需要 O(mn) 的栈空间。