岛屿问题
About 3 min
2024-04-29 momenta 面试考过的,竟然没有一点思路, 没想到这么简单的题竟然不会,难受了
leetcode 200 岛屿问题 -mid
没什么好注意的 (可能边界条件?)
想到 bfs 就能秒
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
def dfs(x, y):
if x < 0 or y < 0 or x >= len(grid) or y >= len(grid[0]):
return
if (grid[x][y]) == "0":
return
if (grid[x][y]) == "1":
grid[x][y] = "0"
dfs(x + 1, y)
dfs(x - 1, y)
dfs(x, y + 1)
dfs(x, y - 1)
return
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if (grid[i][j]) == "1":
dfs(i, j)
count += 1
return count
leetcode 2054 闭合岛屿问题 -mid
这里注意选择 bfs 的对象由土地变成了水, 但水接触了边界后就返回错误.
也有另一种做法, 把所有接水的边上岛屿淹没, 感觉不如我这个想法
class Solution:
def closedIsland(self, grid: List[List[int]]) -> int:
def dfs(i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
return False
if grid[i][j] == 1:
return True
if grid[i][j] == 0:
grid[i][j] = 1
left = dfs(i - 1, j)
right = dfs(i + 1, j)
up = dfs(i, j + 1)
down = dfs(i, j - 1)
sum = left and right and up and down
return sum
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 0:
solution = dfs(i, j)
if solution is True:
count += 1
return count
leetcode 695 最大岛屿问题 -mid
没什么好注意的,非常简单
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
max_land = 0
def dfs(i, j) -> int:
curr_land = 0
if i < 0 or j < 0 or len(grid) <= i or len(grid[0]) <= j:
return 0
if grid[i][j] == 0:
return 0
if grid[i][j] == 1:
grid[i][j] = 0
curr_land = 1
left = dfs(i - 1, j)
right = dfs(i + 1, j)
up = dfs(i, j + 1)
down = dfs(i, j - 1)
sum = left + right + up + down + curr_land
return sum
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
max_land = max(max_land, dfs(i, j))
return max_land
leetcode 1905 子覆盖, 同一个思路
leetcode 463 岛屿周长:
算岛屿问题的一个另类, 但要注意这里面的思想, 并没有用到 dfs(虽然也可以用) 同时也要想办法尝试去解决这样的问题:
如: 最小岛屿周长
如: 最小闭合岛屿周长等, 要注意各种 combination
class Solution:
def islandPerimeter(self, grid: List[List[int]]) -> int:
land = 0
border = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
land += 1
if i + 1 < len(grid):
if (grid[i + 1][j]) == 1:
border += 1
if j + 1 < len(grid[0]):
if (grid[i][j + 1]) == 1:
border += 1
return 4 * land - 2 * border
leetcode 1293-hard 打穿格子最短路径
想法是使用 DFS 做, 非常不幸, 失败了,于是决定用 BFS 做, 顺便开取了 BFS专题
还有注意形如[[0]*10]*10 这样的二维数组生成方式是 python 陷阱, 正常应该用 [[0] * 40 for _ in range(40)]
class Solution:
def shortestPath(self, grid: List[List[int]], k: int) -> int:
max_int = 100
visitid = [[0] * 40 for _ in range(40)]
if k > len(grid) + len(grid[0]) - 2:
return len(grid) + len(grid[0]) - 2
def dfs(i, j, count, k):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
return max_int
if i == len(grid) - 1 and j == len(grid[0]) - 1:
return count
if visitid[i][j] == 1:
return max_int
if grid[i][j] == 1:
if k > 0:
k -= 1
else:
return max_int
visitid[i][j] = 1
count += 1
left_min = dfs(i - 1, j, count, k)
right_min = dfs(i + 1, j, count, k)
up_min = dfs(i, j + 1, count, k)
down_min = dfs(i, j - 1, count, k)
visitid[i][j] = 0 # BACKTRACKING
return min(left_min, right_min, up_min, down_min)
answer = dfs(0, 0, 0, k)
return -1 if answer == max_int else answer