leetcode怎么計(jì)算最小體力消耗路徑

本篇內(nèi)容主要講解“l(fā)eetcode怎么計(jì)算最小體力消耗路徑”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“l(fā)eetcode怎么計(jì)算最小體力消耗路徑”吧!

一、題目內(nèi)容

你準(zhǔn)備參加一場遠(yuǎn)足活動(dòng)。給你一個(gè)二維 rows x columns 的地圖 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一開始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下標(biāo)從 0 開始編號）。你每次可以往 上，下，左，右 四個(gè)方向之一移動(dòng)，你想要找到耗費(fèi) 體力 最小的一條路徑。

一條路徑耗費(fèi)的 體力值 是路徑上相鄰格子之間 高度差絕對值 的 最大值 決定的。

請你返回從左上角走到右下角的最小 體力消耗值 。

示例 1：

輸入：heights = [[1,2,2],[3,8,2],[5,3,5]]
輸出：2
解釋：路徑 [1,3,5,3,5] 連續(xù)格子的差值絕對值最大為 2 。
這條路徑比路徑 [1,2,2,2,5] 更優(yōu)，因?yàn)榱硪粭l路徑差值最大值為 3 。

示例 2：

輸入：heights = [[1,2,3],[3,8,4],[5,3,5]]
輸出：1
解釋：路徑 [1,2,3,4,5] 的相鄰格子差值絕對值最大為 1 ，比路徑 [1,3,5,3,5] 更優(yōu)。

示例 3：

輸入：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
解釋：上圖所示路徑不需要消耗任何體力。
 

提示：

rows == heights.length
columns == heights[i].length
1 <= rows, columns <= 100
1 <= heights[i][j] <= 10^6

二、解題思路

并查集，存儲(chǔ)x到y(tǒng)的距離，然后按照距離從小到大排序，之后從小到大遍歷每個(gè)距離，每次存儲(chǔ)當(dāng)前距離和記錄的距離最大值中二者大的一方，最后返回最大的距離。

三、代碼

class Solution:
    def minimumEffortPath(self, heights: list) -> int:
        f = list(range(len(heights) * len(heights[0])))

        def find(x):
            if x != f[x]:
                f[x] = find(f[x])
            return f[x]

        def union(x, y):
            fx = find(x)
            fy = find(y)
            f[fx] = fy

        # 存儲(chǔ)x到y(tǒng)的邊[x, y, distance]
        x_to_y_list = []
        for x in range(len(heights)):
            for y in range(len(heights[0])):
                next_x = x + 1
                next_y = y
                if 0 <= next_x < len(heights) and 0 <= next_y < len(heights[0]):
                    distance = abs(heights[x][y] - heights[next_x][next_y])
                    x_to_y_list.append([x * len(heights[0]) + y,
                                        next_x * len(heights[0]) + next_y,
                                        distance])

                next_x = x
                next_y = y + 1
                if 0 <= next_x < len(heights) and 0 <= next_y < len(heights[0]):
                    distance = abs(heights[x][y] - heights[next_x][next_y])
                    x_to_y_list.append([x * len(heights[0]) + y,
                                        next_x * len(heights[0]) + next_y,
                                        distance])
        # 將x到y(tǒng)的邊按照distance從小到大排序
        sorted_x_to_y_list = sorted(x_to_y_list, key=lambda x: x[-1])

        res = 0
        for x_to_y_and_distance in sorted_x_to_y_list:
            # 左上與右下連通，直接返回
            if find(0) == find(len(heights) * len(heights[0]) - 1):
                return res
            else:
                x, y, distance = x_to_y_and_distance
                # x和y不連通， 則連通x和y
                if find(x) != find(y):
                    union(x, y)
                    # 判斷當(dāng)前距離和最大值，取大者
                    res = max(res, distance)
        return res


if __name__ == '__main__':
    s = Solution()
    heights = [[1, 2, 2],
               [3, 8, 2],
               [5, 3, 5]]
    ans = s.minimumEffortPath(heights)
    print(ans)

到此，相信大家對“l(fā)eetcode怎么計(jì)算最小體力消耗路徑”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！