Leetcode题解（10）- 2018 力扣 Leetcode CN 高频题汇总 part 6 图论
# 单词接龙
Leetcode 127 题
# 问题
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
每次转换只能改变一个字母。 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 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" 不在字典中，所以无法进行转换。
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 思路
每个单词作为节点，如果两个单词之间只差一个字母，则连一条边。所以问题变成从起点到终点的最短路径。
当然，也要先进行一下预处理，也就是图的构建，如何找出只差一个字母的单词对。我们可以通过将单词中的一个字母用*代替的方式，快速地找出哪些单词之间只差一个字母，例如 dog和dig，都可以变成d*g。所以预处理阶段得到一个dict，key是带有*的通用状态，value是单词表。
基本的BFS写法见代码1。可以进行的一种优化是双向BFS，也即我们从begin和end同时开始搜索，当发现两边都访问到了某个节点时就停止，两边路径连起来就ok。双端BFS见代码2.
# 代码
1）基本BFS
from collections import defaultdict
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
l = len(beginWord)
# 构建辅助信息
mem = defaultdict(list)
for w in wordList:
for i in range(l):
mem[w[:i] + '*' + w[i+1:]].append(w)
# bfs
# 每个元素是 （单词，所处层级也即路径长度）
q = [(beginWord, 1)]
visited = set([beginWord, ])
while q:
w, level = q.pop(0)
for i in range(l):
inter = w[:i] + '*' + w[i+1:]
for word in mem[inter]:
if word == endWord:
return level + 1
if word not in visited:
visited.add(word)
q.append((word, level + 1))
mem[inter] = []
return 0
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
29
30
31
32
33
34
2）双端BFS。有两个queue和两个visited的记录，把公用的方法 visitWordNode抽象出来。每次两端都访问一次，遇到共同访问的节点，则return长度。
from collections import defaultdict
class Solution(object):
def __init__(self):
self.length = 0
self.mem = defaultdict(list)
def visitWordNode(self, q, v1, v2):
w, level = q.pop(0)
for i in range(self.length):
inter = w[:i] + '*' + w[i+1:]
for word in self.mem[inter]:
if word in v2:
return level + v2[word]
if word not in v1:
v1[word] = level + 1
q.append((word, level + 1))
return None
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: int
"""
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
self.length = len(beginWord)
# 构建辅助信息
for w in wordList:
for i in range(self.length):
self.mem[w[:i] + '*' + w[i+1:]].append(w)
# 双向bfs
# 每个元素是 （单词，所处层级也即路径长度）
q1 = [(beginWord, 1)]
q2 = [(endWord, 1)]
v1 = {beginWord: 1}
v2 = {endWord: 1}
ans = None
while q1 and q2:
ans = self.visitWordNode(q1, v1, v2)
if ans:
return ans
ans = self.visitWordNode(q2, v2, v1)
if ans:
return ans
return 0
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 岛屿数量
Leetcode 200 题
# 问题
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
示例 1:
输入:
11110
11010
11000
00000
输出: 1
示例 2:
输入:
11000
11000
00100
00011
输出: 3
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 思路
思路就是从头开始遍历每个点，遇到1，把计数+1，然后就从它开始进行相邻的1的BFS或者DFS，并把路过的点标记为0，这样的话如果遇到1，它所在的岛屿上的点会被全标记为0，最终计数就是岛屿的数量。
之前用的BFS，可以借助队列的形式来实现，现在DFS的话，可以借助栈来实现，DFS也可以直接用递归来实现。BFS和DFS两种都行，总之就是要把每个1的相邻的1全都走一遍并置为0。
# 代码
class Solution(object):
def dfs(self, grid, x, y):
if x >= 0 and x < len(grid) and y >= 0 and y < len(grid[0]) and grid[x][y] == '1':
grid[x][y] = '0'
self.dfs(grid, x-1, y)
self.dfs(grid, x+1, y)
self.dfs(grid, x, y-1)
self.dfs(grid, x, y+1)
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if len(grid) == 0 or len(grid[0]) == 0:
return 0
ret = 0
for i in range(0, len(grid)):
for j in range(0, len(grid[0])):
if grid[i][j] == '1':
ret += 1
self.dfs(grid, i, j)
return ret
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
# 课程表 I 和 II
leetcode 207题和210题。
# 问题
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
给定课程总量以及它们的先决条件，207题要求 判断是否可能完成所有课程的学习？210题要求是输出学习的顺序（多种可行的顺序输出一种即可）
示例 1:
输入: 2, [[1,0]]
输出: true
解释: 总共有 2 门课程。学习课程 1 之前，你需要完成课程 0。所以这是可能的。
示例 2:
输入: 2, [[1,0],[0,1]]
输出: false
解释: 总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0；并且学习课程 0 之前，你还应先完成课程 1。这是不可能的。
2
3
4
5
6
7
8
9
说明: 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。 你可以假定输入的先决条件中没有重复的边。
# 思路
上来直接就学习下现有题解吧。
这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。可以通过BFS或者DFS获得拓扑排序。
1） 拓扑排序 拓扑排序实际上应用的是贪心算法，贪心算法简而言之：每一步最优，全局就最优）。具体到拓扑排序，每一次都输出入度为 00 的结点，并移除它、修改它指向的结点的入度，依次得到的结点序列就是拓扑排序的结点序列。如果图中还有结点没有被移除，则说明“不能完成所有课程的学习”。
拓扑排序保证了每个活动（在这题中是“课程”）的所有前驱活动都排在该活动的前面，并且可以完成所有活动。拓扑排序的结果不唯一。拓扑排序还可以用于检测一个有向图是否有环。相关的概念还有 AOV 网
- DFS 首先构建逆邻接表（key是节点，value是指向该节点的其他节点）
# 代码
1）拓扑排序 具体实现时，使用邻接表记录节点的索引及它的后继节点，使用一个数组来记录各个节点的入度。首先扫描所有项目，将入度为0的放入队列，只要队列不空，就可以取出入度为0的节点，节点加入结果集中，同时将它指向的节点的入度-1，如果-1后为0了就把这个指向的节点也入队。最后队列空了的时候，检查结果集中的节点个数和课程数量是否一样即可。
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int
:type prerequisites: List[List[int]]
:rtype: List[int]
"""
clen = len(prerequisites)
if clen == 0:
return [i for i in range(numCourses)]
# 构建入度表和邻接表
in_degrees = [0 for _ in range(numCourses)]
adj = [set() for _ in range(numCourses)]
for course, pre in prerequisites:
in_degrees[course] += 1
adj[pre].add(course)
# 使用队列
res = []
q = []
for i in range(numCourses):
if in_degrees[i] == 0:
q.append(i)
while q:
top = q.pop(0)
res.append(top)
for nxt in adj[top]:
in_degrees[nxt] -= 1
if in_degrees[nxt] == 0:
q.append(nxt)
if len(res) != numCourses:
return []
else:
return res
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
29
30
31
32
33
34
- DFS
class Solution(object):
def findOrder(self, numCourses, prerequisites):
"""
:type numCourses: int 课程门数
:type prerequisites: List[List[int]] 课程与课程之间的关系
:rtype: bool
"""
# 课程的长度
clen = len(prerequisites)
if clen == 0:
# 没有课程，当然可以完成课程的学习
return [i for i in range(numCourses)]
# 逆邻接表
inverse_adj = [set() for _ in range(numCourses)]
# 想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]
# 1 -> 0，这里要注意：不要弄反了
for second, first in prerequisites:
inverse_adj[second].add(first)
visited = [0 for _ in range(numCourses)]
# print("in_degrees", in_degrees)
# 首先遍历一遍，把所有入度为 0 的结点加入队列
res = []
for i in range(numCourses):
if self.__dfs(i,inverse_adj, visited, res):
return []
return res
def __dfs(self, vertex, inverse_adj, visited, res):
"""
注意：这个递归方法的返回值是返回是否有环
:param vertex: 结点的索引
:param inverse_adj: 逆邻接表，记录的是当前结点的前驱结点的集合
:param visited: 记录了结点是否被访问过，2 表示当前正在 DFS 这个结点
:return: 是否有环
"""
# 2 表示这个结点正在访问
if visited[vertex] == 2:
# DFS 的时候如果遇到一样的结点，就表示图中有环，课程任务便不能完成
return True
if visited[vertex] == 1:
return False
# 表示正在访问这个结点
visited[vertex] = 2
# 递归访问前驱结点
for precursor in inverse_adj[vertex]:
# 如果没有环，就返回 False，
# 执行以后，逆拓扑序列就存在 res 中
if self.__dfs(precursor, inverse_adj, visited, res):
return True
# 能走到这里，说明所有的前驱结点都访问完了，所以可以输出了
# 并且将这个结点状态置为 1
visited[vertex] = 1
# 先把 vertex 这个结点的所有前驱结点都输出之后，再输出自己
res.append(vertex)
# 最后不要忘记返回 False 表示无环
return False
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
图的几个题就先到这里吧，主要熟悉下DFS和BFS的实现。这块的很多知识还很欠缺，后面听一下慕课网的课补一补，课程内容也会笔记到博客上。