DFS
797. 所有可能的路径
给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
示例 1：
输入：graph = [[1,2],[3],[3],[]] 输出：[[0,1,3],[0,2,3]] 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
示例 2：
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]] 输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]
示例 3：
输入：graph = [[1],[]] 输出：[[0,1]]
示例 4：
输入：graph = [[1,2,3],[2],[3],[]] 输出：[[0,1,2,3],[0,2,3],[0,3]]
示例 5：
输入：graph = [[1,3],[2],[3],[]] 输出：[[0,1,2,3],[0,3]]
提示：
- n == graph.length
- 2 <= n <= 15
- 0 <= graph[i][j] < n
- graph[i][j] != i（即，不存在自环）
- graph[i] 中的所有元素 互不相同
- 保证输入为 有向无环图（DAG）
答案
class Solution:def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:n = len(graph)res = []def dfs(cur, path):if cur == n - 1:res.append(path[::])returnfor index in graph[cur]:path.append(index)dfs(index, path)path.pop()dfs(0, [0])return res
关键点是
if cur == n - 1:res.append(path[::])return
之所以这么判断，是因为这个题目给出的条件就是DAG图， 如果当前节点到最后了， 则说明不能继续往下走了
200. 岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ [“1”,”1”,”1”,”1”,”0”], [“1”,”1”,”0”,”1”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”0”,”0”,”0”] ] 输出：1
示例 2：
输入：grid = [ [“1”,”1”,”0”,”0”,”0”], [“1”,”1”,”0”,”0”,”0”], [“0”,”0”,”1”,”0”,”0”], [“0”,”0”,”0”,”1”,”1”] ] 输出：3
提示：
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 300
- grid[i][j] 的值为 ‘0’ 或 ‘1’
通过次数333,979
提交次数599,378
class Solution:def numIslands(self, grid: List[List[str]]) -> int:res = 0direction = [[0, 1], [1, 0], [0, -1], [-1, 0]]def is_in_grid(x, y):nonlocal gridreturn 0 <= x < len(grid) and 0 <= y < len(grid[0])def dfs(x, y):if not is_in_grid(x, y):returnnonlocal grid, directionif grid[x][y] == '2' or grid[x][y] == '0':returngrid[x][y] = '2'for i in direction:new_x = x + i[0]new_y = y + i[1]dfs(new_x, new_y)for x in range(len(grid)):for y in range(len(grid[0])):if grid[x][y] == '1':dfs(x, y)res += 1return res
130. 被围绕的区域
给你一个 m x n 的矩阵 board ，由若干字符 ‘X’ 和 ‘O’ ，找到所有被 ‘X’ 围绕的区域，并将这些区域里所有的 ‘O’ 用 ‘X’ 填充。 
示例 1：
输入：board = [[“X”,”X”,”X”,”X”],[“X”,”O”,”O”,”X”],[“X”,”X”,”O”,”X”],[“X”,”O”,”X”,”X”]] 输出：[[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”X”,”X”,”X”],[“X”,”O”,”X”,”X”]] 解释：被围绕的区间不会存在于边界上，换句话说，任何边界上的 ‘O’ 都不会被填充为 ‘X’。 任何不在边界上，或不与边界上的 ‘O’ 相连的 ‘O’ 最终都会被填充为 ‘X’。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。
示例 2：
输入：board = [[“X”]] 输出：[[“X”]]
提示：
- m == board.length
- n == board[i].length
- 1 <= m, n <= 200
- board[i][j] 为 ‘X’ 或 ‘O’
通过次数130,700
提交次数293,497
class Solution:def solve(self, board: List[List[str]]) -> None:# 将边界上的 'X'全部改为'#'if not board:return Nonem = len(board)n = len(board[0])direction = [[0,1],[0,-1], [1,0], [-1,0]]def is_valid(x, y):nonlocal m, nreturn 0 <= x < m and 0 <= y < ndef dfs(x, y):nonlocal board, directionif not is_valid(x, y):returnif board[x][y] != 'O':returnboard[x][y] = '#'for i in direction:dfs(x + i[0], y + i[1])for c in range(n):if board[0][c] == 'O':dfs(0, c)if board[m - 1][c] == 'O':dfs(m - 1, c)for r in range(m):if board[r][0] == 'O':dfs(r, 0)if board[r][n - 1] == 'O':dfs(r, n - 1)for x in range(m):for y in range(n):if board[x][y] == 'O':board[x][y] = 'X'for x in range(m):for y in range(n):if board[x][y] == '#':board[x][y] = 'O'return board
133. 克隆图
给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。
图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。
class Node { public int val; public List
测试用例格式：
简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。
邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
给定节点将始终是图中的第一个节点（值为 1）。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
示例 1：
输入：adjList = [[2,4],[1,3],[2,4],[1,3]] 输出：[[2,4],[1,3],[2,4],[1,3]] 解释： 图中有 4 个节点。 节点 1 的值是 1，它有两个邻居：节点 2 和 4 。 节点 2 的值是 2，它有两个邻居：节点 1 和 3 。 节点 3 的值是 3，它有两个邻居：节点 2 和 4 。 节点 4 的值是 4，它有两个邻居：节点 1 和 3 。
示例 2：
输入：adjList = [[]] 输出：[[]] 解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。
示例 3：
输入：adjList = [] 输出：[] 解释：这个图是空的，它不含任何节点。
示例 4：
输入：adjList = [[2],[1]] 输出：[[2],[1]]
提示：
- 节点数不超过 100 。
- 每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。
- 无向图是一个简单图，这意味着图中没有重复的边，也没有自环。
- 由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。
- 图是连通图，你可以从给定节点访问到所有节点。
通过次数73,564
提交次数108,802
BFS
207. 课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi。
- 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
示例 1：
输入：numCourses = 2, prerequisites = [[1,0]] 输出：true 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
示例 2：
输入：numCourses = 2, prerequisites = [[1,0],[0,1]] 输出：false 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
提示：
- 1 <= numCourses <= 105
- 0 <= prerequisites.length <= 5000
- prerequisites[i].length == 2
- 0 <= ai, bi < numCourses
- prerequisites[i] 中的所有课程对 互不相同
答案
from collections import defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
dic_pre = defaultdict(list) # 当前课程: 前置课程
dic_post = defaultdict(list) # 前置课程: 后续的课程
for cur, pre in prerequisites:
dic_pre[cur].append(pre)
dic_post[pre].append(cur)
indegree = [len(dic_pre[i]) for i in range(numCourses)] # indegree 保存当前课程的前置课程数量
queue = [i for i in range(numCourses) if indegree[i] == 0]
count = 0
while queue:
course = queue.pop(0)
count += 1
for i in dic_post[course]:
indegree[i] -= 1
if indegree[i] == 0: queue.append(i) # 如果当前课程的入度为0 ，则加入队列中
return count == numCourses
210. 课程表 II
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。
可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。
示例 1:
输入: 2, [[1,0]] 输出: [0,1] 解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。
示例 2:
输入: 4, [[1,0],[2,0],[3,1],[3,2]] 输出: [0,1,2,3] or [0,2,1,3] 解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。 因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。
说明:
- 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
- 你可以假定输入的先决条件中没有重复的边。
提示:
- 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
- 通过 DFS 进行拓扑排序 - 一个关于Coursera的精彩视频教程（21分钟），介绍拓扑排序的基本概念。
- 拓扑排序也可以通过 BFS 完成。
通过次数85,782
提交次数158,364
答案
from collections import defaultdict
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
dic_pre = defaultdict(list)
dic_post = defaultdict(list)
for cur, pre in prerequisites:
dic_pre[cur].append(pre)
dic_post[pre].append(cur)
ingreed = [len(dic_pre[i]) for i in range(numCourses)]
queue = [i for i in range(numCourses) if ingreed[i] == 0]
res = []
while queue:
course = queue.pop(0)
res.append(course)
for c in dic_post[course]:
ingreed[c] -= 1
if ingreed[c] == 0: queue.append(c)
if len(res) == numCourses:
return res
else:
return []
127. 单词接龙
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
- 序列中第一个单词是 beginWord 。
- 序列中最后一个单词是 endWord 。
- 每次转换只能改变一个字母。
转换过程中的中间单词必须是字典 wordList 中的单词。
给你两个单词beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出：5 解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。
示例 2：
输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”] 输出：0 解释：endWord “cog” 不在字典中，所以无法进行转换。
提示：
- 1 <= beginWord.length <= 10
- endWord.length == beginWord.length
- 1 <= wordList.length <= 5000
- wordList[i].length == beginWord.length
- beginWord、endWord 和 wordList[i] 由小写英文字母组成
- beginWord != endWord
- wordList 中的所有字符串 互不相同
通过次数122,833
提交次数262,625
参考： 基础算法(二) — BFS
490. 迷宫
由空地（用 0 表示）和墙（用 1 表示）组成的迷宫 maze 中有一个球。球可以途经空地向 上、下、左、右 四个方向滚动，且在遇到墙壁前不会停止滚动。当球停下时，可以选择向下一个方向滚动。 
给你一个大小为 m x n 的迷宫 maze ，以及球的初始位置 start 和目的地 destination ，其中 start = [startrow, startcol] 且 destination = [destinationrow, destinationcol] 。请你判断球能否在目的地停下：如果可以，返回 true ；否则，返回 false 。
你可以 假定迷宫的边缘都是墙壁（参考示例）。
示例 1：
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4] 输出：true 解释：一种可能的路径是 : 左 -> 下 -> 左 -> 下 -> 右 -> 下 -> 右。 
示例 2：
输入：maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [3,2] 输出：false 解释：不存在能够使球停在目的地的路径。注意，球可以经过目的地，但无法在那里停驻。
示例 3：
输入：maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], start = [4,3], destination = [0,1] 输出：false
提示：
- m == maze.length
- n == maze[i].length
- 1 <= m, n <= 100
- maze[i][j] is 0 or 1.
- start.length == 2
- destination.length == 2
- 0 <= startrow, destinationrow <= m
- 0 <= startcol, destinationcol <= n
- 球和目的地都在空地上，且初始时它们不在同一位置
- 迷宫 至少包括 2 块空地
通过次数6,605
提交次数13,704
505. 迷宫 II
由空地和墙组成的迷宫中有一个球。球可以向上下左右四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。
给定球的起始位置，目的地和迷宫，找出让球停在目的地的最短距离。距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。如果球无法停在目的地，返回 -1。
迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。
示例 1:
输入 1: 迷宫由以下二维数组表示 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4) 输入 3: 目的地坐标 (rowDest, colDest) = (4, 4) 输出: 12 解析: 一条最短路径 : left -> down -> left -> down -> right -> down -> right。 总距离为 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12。
示例 2:
输入 1: 迷宫由以下二维数组表示 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 输入 2: 起始位置坐标 (rowStart, colStart) = (0, 4) 输入 3: 目的地坐标 (rowDest, colDest) = (3, 2) 输出: -1 解析: 没有能够使球停在目的地的路径。
注意:
- 迷宫中只有一个球和一个目的地。
- 球和目的地都在空地上，且初始时它们不在同一位置。
- 给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
- 迷宫至少包括2块空地，行数和列数均不超过100。
通过次数5,543
提交次数11,498
若有收获，就点个赞吧
0 人点赞
