当前位置:   article > 正文

Leetcode每日一题:1631. 最小体力消耗路径_力扣1631

力扣1631

问题描述

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ,其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ,且你希望去最右下角的格子 (rows-1, columns-1) (注意下标从 0 开始编号)。你每次可以往 上,下,左,右 四个方向之一移动,你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值

来源:力扣(LeetCode
链接:https://leetcode-cn.com/problems/path-with-minimum-effort
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

在这里插入图片描述
输入:heights = [[1,2,2],[3,8,2],[5,3,5]]
输出:2
解释:路径 [1,3,5,3,5]连续格子的差值绝对值最大为 2 。 这条路径比路径 [1,2,2,2,5] 更优,因为另一条路径差值最大值为 3 。

在这里插入图片描述
输入:heights = [[1,2,3],[3,8,4],[5,3,5]]
输出:1
解释:路径 [1,2,3,4,5]的相邻格子差值绝对值最大为 1 ,比路径 [1,3,5,3,5] 更优。

在这里插入图片描述
输入:heights =
[[1,2,1,1,1],[1,2,1,2,1],[1,2,1,2,1],[1,2,1,2,1],[1,1,1,2,1]] 输出:0
解释:上图所示路径不需要消耗任何体力

思路分析及代码实现

这道题是考察图的问题
把每个格子都当作图的一个节点,相邻格子之间的差的绝对值当作边的权重,这样就可以把输入的矩阵转化成图的形式。
在这里插入图片描述

其中紫色表示的即为该图体力消耗最小的路径,消耗体力值为该路径的最大权重2
对于这道题我们可以采用并查集的做法,所以这道题就是求从最左上角的点到最右下角的点的连通性问题

首先,我们可以先把 图中所有的边都去掉,变成这个样子
在这里插入图片描述
然后添加权重最小的边0,发现添加完0边之后,没有连通起来,因此0不是最小体力消耗值,继续走
在这里插入图片描述
然后添加权重为1的边,发现还是没有连通起来,因此1也不是最小体力消耗值,然后添加权重为2的边,发现最左上角与最右下角连通起来了,因此2是最小体力消耗
在这里插入图片描述
在这道题中,并查集的作用就是判断最左上角的点和最右下角的点是否连通,同时在添加一条边时,如果该边的两个节点未连通,则将两个节点连通起来

  1. 并查集模板
  2. 获得行列长度,将二维数组转换成一维数组(这个地方,建议没看懂的可以画一下图把每个点用 i * n + j 的形式表示一下)
  3. 定义一个eages列表,用于存储(权重,边的第一个顶点,边的第二个顶点)
  4. 用sort将eages按权重排一下序,默认按照第一个元素排,所以把权重放在第一个上
  5. 遍历边,将节点连通,每连接一次,判断最左上角点和最右下角点是否连通,如果连通返回此时边的的权重,如果遍历到最后仍未连通,则返回0
class DSU:
    def __init__(self, n):
        self.father = [i for i in range(n)]

    def find(self, x):
        if x != self.father[x]:
            self.father[x] = self.find(self.father[x])
        return self.father[x]
    
    def is_connect(self, x, y):
        return self.find(x) == self.find(y)

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x != root_y:
            self.father[root_x] = root_y
        

class Solution:
    def minimumEffortPath(self, heights: List[List[int]]) -> int:
        m = len(heights)
        n = len(heights[0])
        dsu = DSU(m * n)
        eages = []
        for i in range(m):
            for j in range(n):
                pos = i * n + j
                if i < m - 1:
                    eages.append([abs(heights[i+1][j] - heights[i][j]), pos, pos + n])
                if j < n - 1:
                    eages.append([abs(heights[i][j+1] - heights[i][j]), pos, pos + 1])

        eages.sort()
        for eage in eages:
            dsu.union(eage[1], eage[2])
            if dsu.is_connect(0, m*n-1):
                return eage[0]
        return 0
  • 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
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/羊村懒王/article/detail/695524
推荐阅读
相关标签
  

闽ICP备14008679号