本文主要是介绍Leetcode每日一题: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是最小体力消耗
在这道题中,并查集的作用就是判断最左上角的点和最右下角的点是否连通,同时在添加一条边时,如果该边的两个节点未连通,则将两个节点连通起来
- 并查集模板
- 获得行列长度,将二维数组转换成一维数组(这个地方,建议没看懂的可以画一下图把每个点用 i * n + j 的形式表示一下)
- 定义一个eages列表,用于存储(权重,边的第一个顶点,边的第二个顶点)
- 用sort将eages按权重排一下序,默认按照第一个元素排,所以把权重放在第一个上
- 遍历边,将节点连通,每连接一次,判断最左上角点和最右下角点是否连通,如果连通返回此时边的的权重,如果遍历到最后仍未连通,则返回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_yclass 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 + jif 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
这篇关于Leetcode每日一题:1631. 最小体力消耗路径的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!