0%

leetcode: 图

一、最小生成树

给你一个points 数组,表示 2D 平面上的一些点,其中 points[i] = [xi, yi] 。

连接点 [xi, yi] 和点 [xj, yj] 的费用为它们之间的 曼哈顿距离 :|xi - xj| + |yi - yj| ,其中 |val| 表示 val 的绝对值。

请你返回将所有点连接的最小总费用。只有任意两点之间 有且仅有 一条简单路径时,才认为所有点都已连接。

Prim:从点的视角出发,优点就是不用一次计算所有的边的权重。某个节点出发,把它放到队列里面。

然后循环以下操作直到所有节点都已经访问:从队列中弹出距离最小的节点,如果还没访问就设置为访问,加入总代价。然后计算当前节点和所有没访问的节点之间的权重,放到优先级队列里面。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from queue import PriorityQueue


class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
calcu_distance = lambda x, y: abs(points[x][0] - points[y][0]) + abs(points[x][1] - points[y][1])
n = len(points)
pq = PriorityQueue() # 利用优先级队列以logN时间开销存储
un_visit = set([i for i in range(n)])
res = 0
cur = (0, 0) # distance, node index
pq.put(cur)
while un_visit:
dist, cur = pq.get()
# print('{}'.format(un_visit))
if cur not in un_visit:
continue
un_visit.remove(cur)
res += dist
for each in un_visit:
dist = calcu_distance(cur, each)
pq.put((dist, each))
# print('{}'.format(list(pq.queue)))
return res

kruskal算法 + 并查集实现:从边的视角出发。初始化并查集。

1.计算出所有边的权重并排序。

2.在边的集合中按从小到大循环:

如果加入当前边会形成环(也就是两个节点已经有通路了,并查集),那么就跳过。

否则就加入当前边(加入总代价,并连通两个节点)。

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
from collections import defaultdict


class Solution:
def minCostConnectPoints(self, points: List[List[int]]) -> int:
n = len(points)
uf = {i: i for i in range(n)}

def find(x):
while x != uf[x]:
x = uf[x]
return x

def connect(p, q):
return find(p) == find(q)

def union(p, q):
if not connect(p, q):
uf[find(p)] = find(q)

edges = defaultdict(int)
for i in range(n):
for j in range(i + 1, n):
edges[(i, j)] = abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])
edges = sorted(edges.items(), key=lambda item:item[1]) # 排序后的边
# print(edges)
res = 0
total = 0

for i in range(len(edges)):
(x, y), dist = edges[i]
# print('x: {}, y: {}'.format(find(x), find(y)))
if find(x) != find(y): # 如果还没有连通
total += 1
res += dist
# print('{}, {}, {}'.format((x, y), res, total))
if total == n - 1: # 所有节点都已经连通
return res
union(x, y)
return res

二、判断二分图

给定一个无向图graph,当这个图为二分图时返回true。

如果我们能将一个图的节点集合分割成两个独立的子集A和B,并使图中的每一条边的两个节点一个来自A集合,一个来自B集合,我们就将这个图称为二分图。

染色,对于每个边连接的节点,他们一定属于A和B这两个不同集合,BFS或者DFS搜索,如果出现颜色矛盾说明不能构成二分图。

对于不连通的子图,可以作为两个图看待,这个子图里面随机从一个点开始进行染色就行。

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
43
44
45
46
47
48
49
50
51
52
53
54
from collections import defaultdict
from queue import Queue
from typing import List
"""BFS、并查集"""


class Solution:
def isBipartite(self, graph: List[List[int]]) -> bool:
n = len(graph)
parent = [i for i in range(n)]

def find(node):
while parent[node] != node:
node = parent[node]
return node

def union(node1, node2):
if find(node1) != find(node2):
parent[find(node1)] = find(node2)

for i, each in enumerate(graph):
for j in each:
union(i, j)
# 所有子图中,每个子图找一个随机节点
roots = set()
for i in range(n):
cur = find(i)
if cur not in roots:
roots.add(cur)
visited = defaultdict(bool) # 要把每个节点都遍历
undo, green, red = 0, 1, -1
color = defaultdict(int) # 0.未着色,1.蓝色,-1.红色
cur_color = 1
q = Queue()
# print(roots)
for each in roots:
q.put(each)
visited[each] = True
color[each] = red

while not q.empty():
cur = q.get()
cur_color = color[cur]
wanted_color = red if cur_color == green else green
for nei in graph[cur]:
if color[nei] == undo:
color[nei] = wanted_color
elif color[nei] != wanted_color:
return False
color[nei] = wanted_color
if not visited[nei]:
visited[nei] = True
q.put(nei)
return True

三、图连通

有 n 座城市,编号从 1 到 n 。编号为 x 和 y 的两座城市直接连通的前提是: x 和 y 的公因数中,至少有一个 严格大于 某个阈值 threshold 。更正式地说,如果存在整数 z ,且满足以下所有条件,则编号 x 和 y 的城市之间有一条道路:

x % z == 0
y % z == 0
z > threshold
给你两个整数 n 和 threshold ,以及一个待查询数组,请你判断每个查询 queries[i] = [ai, bi] 指向的城市 ai 和 bi 是否连通(即,它们之间是否存在一条路径)。

返回数组 answer ,其中answer.length == queries.length 。如果第 i 个查询中指向的城市 ai 和 bi 连通,则 answer[i] 为 true ;如果不连通,则 answer[i] 为 false 。

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
class UF:
def __init__(self, n):
self.uf = [-1 for i in range(n)]
self.count_= n

def union(self, x, y):
ux, uy = self.find(x), self.find(y)
if ux == uy:
return
# 规模小的优先合并
if self.uf[ux] < self.uf[uy]:
self.uf[ux] += self.uf[uy]
self.uf[uy] = ux
else:
self.uf[uy] += self.uf[ux]
self.uf[ux] = uy
self.count_ -= 1

def find(self, x):
r = x
while self.uf[x] >= 0:
x = self.uf[x]
# 路径压缩
while r != x:
self.uf[r],r = x,self.uf[r]
return x


class Solution:
def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:
uf = UF(n + 1)
# 通过连接大于阈值的因子与所有可能的节点来判断连通,时间复杂度O(n·logn)
for i in range(threshold + 1, n + 1):
for j in range(2 * i, n + 1, i):
uf.union(i, j)

ans = []
for a, b in queries:
ans.append(True if uf.find(a) == uf.find(b) else False)
return ans

四、最长连续序列

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。

进阶:你可以设计并实现时间复杂度为 O(n) 的解决方案吗?

转换为图连通问题,用并查集处理相邻数字代表的节点,时间复杂度O(n)。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class UnionFind:
def __init__(self, n):
self.uf = [-1] * n
self.count_ = n

def find(self, x):
r = x
while self.uf[x] >= 0:
x = self.uf[x]
# x为根节点
# 路径压缩,摊平
while r != x:
self.uf[r], r = x, self.uf[r]
return x

def union(self, x, y):
ux, uy = self.find(x), self.find(y)
if ux == uy:
return
# 按秩合并,把规模大的合并到规模小的群里,群的元素数量是-uf[root]
if self.uf[ux] < self.uf[uy]:
self.uf[ux] += self.uf[uy]
self.uf[uy] = ux
else:
self.uf[uy] += self.uf[ux]
self.uf[ux] = uy
self.count_ -= 1

def count(self): # 连通子图的数量
return self.count_


class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
uf = UnionFind(len(nums))
value2idx = {}
# O(n)
for i, a in enumerate(nums):
if a not in value2idx:
value2idx[a] = i

visited = set()

# O(n)
for i, a in enumerate(nums):
if a in visited: # 排除已经处理的中间值
continue
visited.add(a)
if a + 1 in value2idx and a + 1 not in visited:
uf.union(i, value2idx[a + 1])
if a - 1 in value2idx and a - 1 not in visited:
uf.union(i, value2idx[a - 1])

max_ = 0
for i in range(len(nums)):
max_ = max(max_, -uf.uf[uf.find(i)])
return max_

五、二分图最大匹配

你有一块棋盘,棋盘上有一些格子已经坏掉了。你还有无穷块大小为1 * 2的多米诺骨牌,你想把这些骨牌不重叠地覆盖在完好的格子上,请找出你最多能在棋盘上放多少块骨牌?这些骨牌可以横着或者竖着放。

因为是1×2的棋子,所以一个棋子必须在横向或者纵向占两个格子,把棋盘相邻的格子看作点,并连接起来,则问题转换为一个二分图上的最大匹配问题。

这一题也可以用轮廓线DP来做(如代码),不过速度要慢很多。

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class Solution:
def domino(self, n: int, m: int, broken: List[List[int]]) -> int:
"""匈牙利算法,二分图最大匹配"""
edges = defaultdict(set)
broken = set([i * m + j for i, j in broken])

def neighbor(x, y):
if x > 0:
yield (x - 1) * m + y
if y > 0:
yield x * m + y - 1
if x + 1 < n:
yield (x + 1) * m + y
if y + 1 < m:
yield x * m + y + 1

# 建一个二分图, O(m * n)
left_nodes = []
for i in range(n):
for j in range(m):
point = i * m + j
if point in broken:
continue
if (i + j) % 2 == 0:
left_nodes.append(point)
for each in neighbor(i, j):
if each not in broken:
edges[point].add(each)

# 匈牙利算法求最大匹配数量,O(|V| * |E|) = O(m * n * m * n)
match_l = defaultdict(lambda: None)
match_r = defaultdict(lambda: None)

def dfs(p, visited):
nonlocal match_l, match_r
visited.add(p)
for neighbor_p in edges[p]:
# 直接找到了一个连接非匹配点的非匹配边
if match_r[neighbor_p] is None:
match_l[p] = neighbor_p
match_r[neighbor_p] = p
return True

for neighbor_p in edges[p]:
nxt = match_r[neighbor_p]
if nxt in visited: # 增广路不要涉及重复节点
continue
# 递归寻找下一组 左 -> 右,如果右边是非匹配节点,那么递归的逆转增广路选择
if dfs(nxt, visited):
match_l[p] = neighbor_p
match_r[neighbor_p] = p
return True
return False

res = 0
for node in left_nodes:
if dfs(node, set()):
res += 1
return res

def domino_dp(self, n: int, m: int, broken: List[List[int]]) -> int:
"""插头DP"""
valid = defaultdict(bool)
NO, HENG, SHU = 0, 1, 2
# 记录坏掉的地板,这里不能放东西
for x, y in broken:
valid[x * m + y] = True
# 最后增加一行坏掉的地板,表示最后一行只能横着放
for i in (m * n, (m + 1) * n):
valid[i] = True
# 0代表不放,1代表横着放,2代表竖着放,用m位三进制表示轮廓线的状态
# [3 ^ m, 3]
states_transition = [[None] * 3 for _ in range(3 ** m)]
elements = {}
first = lambda s: s // (3 ** (m - 1)) # 轮廓线第一个元素的状态,在当前元素上方
second = lambda s: s % (3 ** (m - 1)) // (3 ** (m - 2))
last = lambda x: x % 3 # 轮廓线最后一个元素的状态,在当前元素左边(如果x > 0)
row = lambda p: p // m
col = lambda p: p % m
# 预先计算轮廓线状态转移
for i in range(3 ** m):
f, l = first(i), last(i)
sec = second(i)
elements[i] = (f, sec, l)
remain = i % (3 ** (m - 1))
states_transition[i] = [
remain * 3 + NO,
remain * 3 + HENG,
remain * 3 + SHU
]


@lru_cache(None)
def dfs(pos, state):
x, y = row(pos), col(pos)
# 终止条件
if pos == m * n:
return 0
first, second, last = elements[state]
# 当前位置不能放置
new_state = states_transition[state][NO]
ans = dfs(pos + 1, new_state)
if first == SHU or (y > 0 and last == HENG) or valid[pos]:
...
else:
# 可以横着放
if y + 1 < m and not valid[pos + 1] and second != SHU:
new_state = states_transition[state][HENG]
ans = max(ans, 1 + dfs(pos + 1, new_state))
# 可以竖着放
if x + 1 < n and not valid[pos + m]:
new_state = states_transition[state][SHU]
ans = max(ans, 1 + dfs(pos + 1, new_state))
return ans

return dfs(0, 0)