797. 所有可能的路径
class Solution:
def __init__(self):
self.res = []
# self.path = [0]
def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
path = [0]
# l = set()
self.tracebacking( graph, 0, path)
return self.res
def tracebacking(self, graph, node, path):
if(node == len(graph)-1):
self.res.append(path[:])
# print(self.res)
return
for index, node in enumerate(graph[node]):
path.append(node)
self.tracebacking( graph, node, path)
path.pop()
200. 岛屿数量
class Solution:
def __init__(self):
self.dir = [[0,1],# right
[1,0],#down
[-1,0],#up
[0,-1]]#left
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid) #hang
n = len(grid[0])#lie
print(m, n)
visited = [[False]*n for _ in range(m)]
result = 0
for i in range(m):
for j in range(n):
# print( grid[i][j] == 1))
if visited[i][j] == False and grid[i][j] == "1":
self.dfs(grid, visited, i, j)
#self.bfs(grid, visited, i, j)
result += 1
# print(visited)
return result
def dfs(self, grid, visited, x, y):
if grid[x][y] == "0" or visited[x][y] == True:
return
visited[x][y] = True
for i in range(4):
nextx = x + self.dir[i][0]
nexty = y + self.dir[i][1]
if nextx<0 or nextx>=len(grid) or nexty<0 or nexty>=len(grid[0]):
continue
self.dfs(grid, visited, nextx, nexty)
def bfs(self, grid, visited, x, y):
q = deque()
q.append((x, y))
visited[x][y] = True
while q:
x, y = q.popleft()
# print(x,y)
for i in range(4):
nextx = x + self.dir[i][0]
nexty = y + self.dir[i][1]
if nextx<0 or nextx>=len(grid) or nexty<0 or nexty>=len(grid[0]) or visited[nextx][nexty] == True or grid[nextx][nexty] == "0":
continue
visited[nextx][nexty] = True
q.append((nextx, nexty))
695. 岛屿的最大面积
对岛屿数量进行修改就可以了
区别在于最大面积计算递归次数(dfs),或者入栈次数(bfs)
class Solution:
def __init__(self):
self.dir = [[0,1],# right
[1,0],#down
[-1,0],#up
[0,-1]]#left
self.maxsize = 0
self.count = 0
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m = len(grid) #hang
n = len(grid[0])#lie
# print(m, n)
visited = [[False]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if visited[i][j] == False and grid[i][j] == 1:
#bfs
# self.maxsize = max(self.maxsize, self.bfs(grid, visited, i, j))
#dfs
self.count = 0
self.dfs(grid, visited, i, j)
self.maxsize = max(self.maxsize, self.count)
return self.maxsize
# def bfs(self, grid, visited, x, y):
# q = deque()
# q.append((x, y))
# visited[x][y] = True
# maxtem = 1
# while q:
# x, y = q.popleft()
# for i in range(4):
# nextx = x + self.dir[i][0]
# nexty = y + self.dir[i][1]
# if nextx<0 or nextx>=len(grid) or nexty<0 or nexty>=len(grid[0]) or visited[nextx][nexty] == True or grid[nextx][nexty] == 0:
# continue
# visited[nextx][nexty] = True
# maxtem += 1
# q.append((nextx, nexty))
# return maxtem
def dfs(self, grid, visited, x, y):
if grid[x][y] == 0 or visited[x][y] == True:
return 0
visited[x][y] = True
self.count += 1
for i in range(4):
nextx = x + self.dir[i][0]
nexty = y + self.dir[i][1]
if nextx<0 or nextx>=len(grid) or nexty<0 or nexty>=len(grid[0]):
continue
self.dfs(grid, visited, nextx, nexty)