new Cairo()

Happy reading and coding.

0%

leetcode: 图

发表于 分类于 阅读次数：
本文字数： 7.8k 阅读时长 ≈ 7 分钟

一、最小生成树

给你一个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)