深度优先搜索
DFS模板
733. 图像渲染
有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。
给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。
为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。
最后返回经过上色渲染后的图像。
DFS
1 | """先递归，再判断条件""" |
1 | """先判断条件，再递归""" |
BFS
1 | class Solution(object): |
130.被围绕的区域
给定一个二维的矩阵，包含 ‘X’ 和 ‘O’（字母 O）。
找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。
DFS
将边界上及与边界上的’O’相连的’O’标记为’G’，然后将所有标记’G’的改为’O’，其他标记为’X’
1 | class Solution(object): |
BFS
1 | class Solution(object): |
01矩阵
给定一个由 0 和 1 组成的矩阵，找出每个元素到最近的 0 的距离。
两个相邻元素间的距离为 1 。
DFS (超时)
从0开始入手，超时1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix or not matrix[0]:
return []
m,n=len(matrix),len(matrix[0])
for i in range(m):
for j in range(n):
if matrix[i][j]==1:
matrix[i][j]=float('inf')
for i in range(m):
for j in range(n):
if matrix[i][j]==0:
self.dfs(matrix, i, j, 0)
return matrix
def dfs(self, matrix, i, j, d):
if i<0 or i>=len(matrix) or j<0 or j>=len(matrix[0]) or matrix[i][j]<d:
return
matrix[i][j]=d
for x, y in ((i+1,j),(i-1,j),(i,j+1),(i,j-1)):
self.dfs(matrix, x, y, d+1)
DFS
从与0相邻的1开始1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution(object):
def updateMatrix(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: List[List[int]]
"""
if not matrix or not matrix[0]:
return []
m,n=len(matrix),len(matrix[0])
for i in range(m):
for j in range(n):
mark=((i>0 and matrix[i-1][j]==0) or (i+1<m and matrix[i+1][j]==0) or \
(j>0 and matrix[i][j-1]==0) or (j+1<n and matrix[i][j+1]==0))
if matrix[i][j]==1 and not mark:
matrix[i][j]=float('inf')
def dfs(matrix, i, j):
for x,y in zip((i+1,i-1,i,i),(j,j,j+1,j-1)):
if 0<=x<m and 0<=y<n and matrix[x][y]>matrix[i][j]+1:
matrix[x][y]=matrix[i][j]+1
dfs(matrix,x,y)
for i in range(m):
for j in range(n):
if matrix[i][j]==1:
dfs(matrix, i, j)
return matrix
1 | class Solution(object): |
BFS
1 | class Solution(object): |
[286. Walls and Gates]
You are given a m x n 2D grid initialized with these three possible values.1
2
3
4-1 - A wall or an obstacle.
0 - A gate.
INF - Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
DFS (待完善)
1 | class Solution(object): |
329. 矩阵中的最长递增路径
给定一个整数矩阵，找出最长递增路径的长度。
对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。
dp[i][j]表示matrix[i][j]开始的递增路径长度1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution(object):
def longestIncreasingPath(self, matrix):
"""
:type matrix: List[List[int]]
:rtype: int
"""
if not matrix or not matrix[0]:
return 0
m,n=len(matrix),len(matrix[0])
dp=[[0]*n for _ in range(m)]
def dfs(i,j):
if not dp[i][j]:
dp[i][j]=1+max(
dfs(i-1,j) if i>0 and matrix[i-1][j]>matrix[i][j] else 0,
dfs(i+1,j) if i+1<m and matrix[i+1][j]>matrix[i][j] else 0,
dfs(i,j-1) if j>0 and matrix[i][j-1]>matrix[i][j] else 0,
dfs(i,j+1) if j+1<n and matrix[i][j+1]>matrix[i][j] else 0,
)
return dp[i][j] # 记得要返回值
return max([dfs(i,j) for i in range(m) for j in range(n)])
1 | class Solution(object): |
1 | class Solution(object): |
1 | class Solution(object): |
695. 岛屿的最大面积
给定一个包含了一些 0 和 1的非空二维数组 grid , 一个 岛屿 是由四个方向 (水平或垂直) 的 1 (代表土地) 构成的组合。你可以假设二维矩阵的四个边缘都被水包围着。
找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为0。)
DFS
1 | class Solution(object): |
BFS
1 | class Solution(object): |
690. 员工的重要性
给定一个保存员工信息的数据结构，它包含了员工唯一的id，重要度 和 直系下属的id。
比如，员工1是员工2的领导，员工2是员工3的领导。他们相应的重要度为15, 10, 5。那么员工1的数据结构是[1, 15, [2]]，员工2的数据结构是[2, 10, [3]]，员工3的数据结构是[3, 5, []]。注意虽然员工3也是员工1的一个下属，但是由于并不是直系下属，因此没有体现在员工1的数据结构中。
现在输入一个公司的所有员工信息，以及单个员工id，返回这个员工和他所有下属的重要度之和。
DFS
1 | """ |
BFS
1 | """ |