Leetcode有向图无向图，一题多解，并查优先队列都给我冲

阳光穿透心脏的1/2处 2022-10-25 14:04 20阅读 0赞

[778. 水位上升的泳池中游泳][778.]

# 并查集 #

解题思路：

由于题目要我们找的是最少等待时间，可以模拟下雨的过程，把网格抽象成一个无权图，每经过一个时刻，就考虑此时和雨水高度相等的单元格，考虑这个单元格的上、下、左、右、四个方向，并且高度更低的单元格，把它们在并查集中进行合并。

前提知识：无向图,连通量

![动图演示][02fb09549466f6901432d8738ad0ab6d.gif]

class Solution(object):
        def swimInWater(self, grid):
            """
            :type grid: List[List[int]]
            :rtype: int
            """
            N = len(grid)
            nodes = [None] * (N * N)
            for i in range(N):
                for j in range(N):
                    nodes[grid[i][j]] = (i, j)
            dsu = DSU(N * N)
            dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]
            for i, node in enumerate(nodes):
                x, y = node[0], node[1]
                for dir in dirs:
                    newx = x + dir[0]
                    newy = y + dir[1]
                    if newx >= 0 and newx < N and newy >= 0 and newy < N and grid[newx][newy] < i:
                        dsu.unite(x * N + y , newx * N + newy)
                if dsu.connected(0, N * N - 1):
                    return i
            return 0
    
    class DSU:
        def __init__(self, n: int):
            self.parent = list(range(n))
            self.size = [1] * n
            self.n = n
            # 当前连通分量数目
            self.setCount = n
        
        def findset(self, x: int) -> int:
            if self.parent[x] == x:
                return x
            self.parent[x] = self.findset(self.parent[x])
            return self.parent[x]
        
        def unite(self, x: int, y: int) -> bool:
            x, y = self.findset(x), self.findset(y)
            if x == y:
                return False
            if self.size[x] < self.size[y]:
                x, y = y, x
            self.parent[y] = x
            self.size[x] += self.size[y]
            self.setCount -= 1
            return True
        
        def connected(self, x: int, y: int) -> bool:
            x, y = self.findset(x), self.findset(y)
            return x == y

# 优先队列 #

## 解题思路: ##

> **所有的能走的点中我们永远只走水位最低的点**，每到一个点，我们再记录所有的周围能走的点，并再次选择所有能走的点中水位最低的点。

# #

## ![20210201150408731.gif][] ##

## [heapq][] --- 堆队列算法 ##

这个API与教材的堆算法实现有所不同，具体区别有两方面：（a）我们使用了从零开始的索引。这使得节点和其孩子节点索引之间的关系不太直观但更加适合，因为 Python 使用从零开始的索引。 （b）我们的 pop 方法返回最小的项而不是最大的项（这在教材中称为“最小堆”；而“最大堆”在教材中更为常见，因为它更适用于原地排序）。

### `heapq.``heappush`(*heap*, *item*) ###

将 *item* 的值加入 *heap* 中，保持堆的不变性。

### `heapq.``heappop`(*heap*) ###

弹出并返回 *heap* 的最小的元素，保持堆的不变性。如果堆为空，抛出 [`IndexError`][IndexError] 。使用 `heap[0]` ，可以只访问最小的元素而不弹出它。

`heapq.``heappushpop`(*heap*, *item*)

将 *item* 放入堆中，然后弹出并返回 *heap* 的最小元素。该组合操作比先调用  [`heappush()`][heappush] 再调用 [`heappop()`][heappop] 运行起来更有效率。

class Solution:
        def swimInWater(self, grid: List[List[int]]) -> int:
            res = 0
            n = len(grid)
            heap = [(grid[0][0],0,0)]
            visited = set([(0,0)])
            
            while heap:
                height,x,y = heapq.heappop(heap)
                res = max(res,height)
                if x == n-1 and y == n-1:
                    return res
                
                for dx,dy in [(0,1),(0,-1),(1,0),(-1,0)]:
                    new_x,new_y = x + dx,y + dy
                    if 0 <= new_x < n and 0 <= new_y < n and (new_x,new_y) not in visited:
                        visited.add((new_x,new_y))
                        heapq.heappush(heap,(grid[new_x][new_y],new_x,new_y))
            
            return -1

[1631. 最小体力消耗路径][778.]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 3][]

## 解题思路： ##

具体来说，我们可以先把图中的所有边都去掉，然后按照边的权重大小，把边再逐个的添加上。当我们添加到某一条边时，最左上角的节点和最右下角的节点连通了，那么该边的权重就是我们要求的最小体力消耗值。

代码

1.  首先需要一个并查集的数据结构 DSU，这里直接使用模板。
2.  然后我们需要生成所有的边，并保存到 edges 中。edges\[i\] 是个 \[边的权重，边的第一个顶点，边的第二个顶点\] 三元组。把边的权重放在第一位的原因是，我们需要对边的权重排序，在 Python 中调用sort()函数，默认会根据第一个元素排。
3.  按照权重对所有的边进行排序sort()。
4.  遍历所有边，连通这个边的两个节点。并且判断，如果最左上角和最右下角两个节点是否连通了。如果已经连通，则此时的边的权重就是我们要求的最小体力消耗值。

class Solution(object):
        def minimumEffortPath(self, heights):
            """
            :type heights: List[List[int]]
            :rtype: int
            """
            M = len(heights)
            N = len(heights[0])
            dsu = UnionFind(M*N)
            edges = []
            for i in range(M):
                for j in range(N):
                    pos = i * N + j
                    if i < M - 1:
                        edges.append([abs(heights[i + 1][j] - heights[i][j]), pos, pos + N])
                    if j < N - 1:
                        edges.append([abs(heights[i][j + 1] - heights[i][j]), pos, pos + 1])
            edges.sort()
            for edge in edges:
                dsu.unite(edge[1], edge[2])
                if dsu.connected(0, M * N - 1):
                    return edge[0]
            return 0
            
            
    class UnionFind:
        def __init__(self, n: int):
            self.parent = list(range(n))
            self.size = [1] * n
            self.n = n
            # 当前连通分量数目
            self.setCount = n
        
        def findset(self, x: int) -> int:
            if self.parent[x] == x:
                return x
            self.parent[x] = self.findset(self.parent[x])
            return self.parent[x]
        
        def unite(self, x: int, y: int) -> bool:
            x, y = self.findset(x), self.findset(y)
            if x == y:
                return False
            if self.size[x] < self.size[y]:
                x, y = y, x
            self.parent[y] = x
            self.size[x] += self.size[y]
            self.setCount -= 1
            return True
        
        def connected(self, x: int, y: int) -> bool:
            x, y = self.findset(x), self.findset(y)
            return x == y

# #

[778.]: https://leetcode-cn.com/problems/path-with-minimum-effort/
[02fb09549466f6901432d8738ad0ab6d.gif]: /images/20221024/08212bb995cd41c29a3e5e6cb6fdc760.png
[20210201150408731.gif]: /images/20221024/1edcb1a5baf64b57aa53c73522242f87.png
[heapq]: https://docs.python.org/zh-cn/3/library/heapq.html
[IndexError]: https://docs.python.org/zh-cn/3/library/exceptions.html#IndexError
[heappush]: https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappush
[heappop]: https://docs.python.org/zh-cn/3/library/heapq.html#heapq.heappop
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20221024/e298e1532310421b92b60dd65aa8d77a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 1]: /images/20221024/ed9d6b2eb51542e8a7a2d8514deea04c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 2]: /images/20221024/2d23a20683db4bbe94e74ac7343c8fd5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70 3]: /images/20221024/c86c084385f84c6b9f2fe3e6737fb7ec.png