leetcode题目按类型
宽度优先BFS
BFS 算法框架
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def BFS(start, target):
q = []
visited = {}
q.append(start) # 队列queue
visited.add(start) # 像二叉树一样的结构，没有子节点到父节点的指针，不会走回头路，就不需要visited
step = 0
while q:
for _ in range(len(queue)):
cur = q.pop(0) # Notice is 0
if cur is target:
return step
for x in cur.adj(): # 将 cur 的相邻节点加⼊队列
if x not in visited:
q.append(x)
visited.add(x)
step += 1 # 遍历完一层后step++
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
Queue<Node> q; // 核⼼数据结构
Set<Node> visited; // 避免⾛回头路
q.offer(start); // 将起点加⼊队列
visited.add(start);
int step = 0; // 记录扩散的步数
while (q not empty) {
int sz = q.size();
/* 将当前队列中的所有节点向四周扩散 */
for (int i = 0; i < sz; i++) {
Node cur = q.poll();
/* 划重点：这⾥判断是否到达终点 */
if (cur is target)
return step;
/* 将 cur 的相邻节点加⼊队列 */
for (Node x : cur.adj())
if (x not in visited) {
q.offer(x);
visited.add(x);
}
}
/* 划重点：更新步数在这⾥ */
step++;
}
}
存储入度 — 🚩(50m) 210. 课程表 II
难度中等423收藏分享切换为英文接收动态反馈
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [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
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
G = [[] for _ in range(numCourses)]
indegree = [0] * numCourses # 注意 要存储入度个数！入度为0时才可以选择
for pre in prerequisites:
G[pre[1]].append(pre[0])
indegree[pre[0]] += 1
print(G)
visited = set()
res = []
# 注意！！ 要先把所有入度为0的点加到queue里
queue = [i for i in range(numCourses) if indegree[i]==0 ]
while queue:
cur = queue.pop(0)
res.append(cur)
for nei in G[cur]:
# 注意 要存储入度个数！入度为0时才可以选择
indegree[nei] -= 1
if indegree[nei]==0:
queue.append(nei)
if len(res) != numCourses:
res = []
return res
注意：
一定要存储入度个数
————————————-
✅ (30m)111. 二叉树的最小深度
给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。
示例 1：
1
2
输入：root = [3,9,20,null,null,15,7]
输出：2
示例 2：
1
2
输入：root = [2,null,3,null,4,null,5,null,6]
输出：5
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def minDepth(self, root: TreeNode) -> int:
if not root: return 0
deque = [root]
step = 1
while deque:
for i in range(len(deque)): # 重要，要先把deque里的所有并列节点遍历完后，在遍历子节点，并找新节点，step+1
node = deque.pop(0)
if not node.left and not node.right:
return step
if node.left: deque.append(node.left) # 注意先判断左右子节点是否是None
if node.right: deque.append(node.right)
step += 1
return 0
总结：
for i in range(len(deque)):很重要，要先把deque里的所有并列节点遍历完后，在遍历子节点，并找新节点，step+1if node.left: deque.append(node.left)注意先判断左右子节点是否是None
2️⃣
✅(2.0h) 752. 打开转盘锁
难度中等211
你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。
锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。
列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。
字符串 target 代表可以解锁的数字，你需要给出最小的旋转次数，如果无论如何不能解锁，返回 -1。
示例 1:
1
2
3
4
5
6
输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:
1
2
3
4
输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:
1
2
3
4
输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。
示例 4:
1
2
输入: deadends = ["0000"], target = "8888"
输出：-1
提示：
- 死亡列表
deadends的长度范围为[1, 500]。 - 目标数字
target不会在deadends之中。 - 每个
deadends和target中的字符串的数字会在 10,000 个可能的情况'0000'到'9999'中产生。
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution:
def openLock(self, deadends: List[str], target: str) -> int:
if "0000" in deadends: return -1
deque = ["0000"]
step = 0
visited = set(["0000"]+ deadends) # list内类型变化方式
# add
def num_add(arr, idx):
if arr[idx] == '9':
newnum = '0'
else:
newnum = str(int(arr[idx])+1)
return arr[:idx] + newnum + arr[idx+1:]
def num_red(arr, idx):
if arr[idx] == '0':
newnum = '9'
else:
newnum = str(int(arr[idx])-1)
return arr[:idx] + newnum + arr[idx+1:]
while deque:
for num in range(len(deque)): # 重要，要先把deque里的所有并列节点遍历完后，在遍历子节点，并找新节点，step+1
node = deque.pop(0)
visited.add(node)
if node == target:
return step
next_node = []
for j in range(4):
next_node_add = num_add(node,j)
next_node_red = num_red(node,j)
next_node.append(next_node_add)
next_node.append(next_node_red)
next_node = [i for i in next_node if i not in visited] # 实现数组过滤
deque.extend(next_node)
visited.update(next_node) # set 传入可迭代元素的方式
# print("visited",visited)
# print("deque",deque)
step += 1
return -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 官解
class Solution(object):
def openLock(self, deadends, target):
def neighbors(node):
for i in xrange(4):
x = int(node[i])
for d in (-1, 1):
y = (x + d) % 10
yield node[:i] + str(y) + node[i+1:]
dead = set(deadends)
queue = collections.deque([('0000', 0)])
seen = {'0000'}
while queue:
node, depth = queue.popleft()
if node == target: return depth
if node in dead: continue
for nei in neighbors(node):
if nei not in seen:
seen.add(nei)
queue.append((nei, depth+1))
return -1
总结：
-
关于防止进位的写法：
1 2 3 4 5 6
def neighbors(node): for i in xrange(4): x = int(node[i]) for d in (-1, 1): y = (x + d) % 10 yield node[:i] + str(y) + node[i+1:]
🚩(90m)（困难） 773. 滑动谜题
在一个 2 x 3 的板上（board）有 5 块砖瓦，用数字 1~5 来表示, 以及一块空缺用 0 来表示.
一次移动定义为选择 0 与一个相邻的数字（上下左右）进行交换.
最终当板 board 的结果是 [[1,2,3],[4,5,0]] 谜板被解开。
给出一个谜板的初始状态，返回最少可以通过多少次移动解开谜板，如果不能解开谜板，则返回 -1 。
示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
输入：board = [[1,2,3],[4,0,5]]
输出：1
解释：交换 0 和 5 ，1 步完成
输入：board = [[1,2,3],[5,4,0]]
输出：-1
解释：没有办法完成谜板
输入：board = [[4,1,2],[5,0,3]]
输出：5
解释：
最少完成谜板的最少移动次数是 5 ，
一种移动路径:
尚未移动: [[4,1,2],[5,0,3]]
移动 1 次: [[4,1,2],[0,5,3]]
移动 2 次: [[0,1,2],[4,5,3]]
移动 3 次: [[1,0,2],[4,5,3]]
移动 4 次: [[1,2,0],[4,5,3]]
移动 5 次: [[1,2,3],[4,5,0]]
输入：board = [[3,2,4],[1,5,0]]
输出：14
✅(80m)（困难）127. 单词接龙
难度困难776
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：
- 序列中第一个单词是
beginWord。 - 序列中最后一个单词是
endWord。 - 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典
wordList中的单词。
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。
示例 1：
1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。
示例 2：
1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。
我们可以把每个单词都抽象为一个点，如果两个单词可以只改变一个字母进行转换，那么说明他们之间有一条双向边。因此我们只需要把满足转换条件的点相连，就形成了一张图。
基于该图，我们以 beginWord 为图的起点，以 endWord 为终点进行广度优先搜索，寻找 beginWord 到 endWord 的最短路径。
步骤：
- 先建图
- 再bfs
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
29
30
31
32
33
34
35
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
G = dict()
allword = wordList
allwordset = set(allword)
for word in allword+[beginWord]:
G[word] = []
for j in range(len(word)):
for k in range(26):
tmp = list(word)
tmp[j] = chr(ord('a') + k)
tmp = ''.join(tmp)
if tmp in allwordset:
G[word].append(tmp)
print(G)
q = [beginWord]
visited = {word:False for word in allword}
visited[beginWord] = True
step = 1
while q:
for _ in range(len(q)):
cur = q.pop(0)
print(cur)
if cur == endWord:
return step
if cur in G.keys():
for word in G[cur]:
if not visited[word]:
q.append(word)
visited[word] = True
# print(q)
step += 1
return 0
注意：
- 注意构建图的方式，每一个单词遍历然后从set中找的复杂度是O(26n)，否则是O(nn)，会超时
🚩（困难）126. 单词接龙 II
✅(30m) 547. 省份数量
难度中等568收藏分享切换为英文接收动态反馈
有 n 个城市，其中一些彼此相连，另一些没有相连。如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。
给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。
返回矩阵中 省份 的数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def findCircleNum(self, isConnected: List[List[int]]) -> int:
res = 0
visited = set()
for i in range(len(isConnected)):
if i in visited:
continue
queue = collections.deque([i])
while queue:
cur = queue.popleft()
# if cur in visited:
# continue
visited.add(cur)
for nei in range(len(isConnected)):
if isConnected[cur][nei] == 1 and nei not in visited:
queue.append(nei)
res += 1
return res
总结：
这道题不需要先建立G，而只需要用isConnected表示连接即可：
1
if isConnected[cur][nei] == 1
✅（20m）207. 课程表
难度中等855收藏分享切换为英文接收动态反馈
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
- 例如，先修课程对
[0, 1]表示：想要学习课程0，你需要先完成课程1。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
🚩(50m) 210. 课程表 II
难度中等423收藏分享切换为英文接收动态反馈
现在你总共有 n 门课需要选，记为 0 到 n-1。
在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [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
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
G = [[] for _ in range(numCourses)]
indegree = [0] * numCourses # 注意 要存储入度个数！入度为0时才可以选择
for pre in prerequisites:
G[pre[1]].append(pre[0])
indegree[pre[0]] += 1
print(G)
visited = set()
res = []
# 注意！！ 要先把所有入度为0的点加到queue里
queue = [i for i in range(numCourses) if indegree[i]==0 ]
while queue:
cur = queue.pop(0)
res.append(cur)
for nei in G[cur]:
# 注意 要存储入度个数！入度为0时才可以选择
indegree[nei] -= 1
if indegree[nei]==0:
queue.append(nei)
if len(res) != numCourses:
res = []
return res
注意：
一定要存储入度个数
