Leetcode 1167:连接棒材的最低费用(超详细的解法!!!)
in leetcode with 0 comment

Leetcode 1167:连接棒材的最低费用(超详细的解法!!!)

in leetcode with 0 comment

为了装修新房,你需要加工一些长度为正整数的棒材 sticks

如果要将长度分别为 XY 的两根棒材连接在一起,你需要支付 X + Y 的费用。 由于施工需要,你必须将所有棒材连接成一根。

返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。

示例 1:

输入:sticks = [2,4,3]
输出:14
解释:先将 2 和 3 连接成 5,花费 5;再将 5 和 4 连接成 9;总花费为 14。

示例 2:

输入:sticks = [1,8,3,5]
输出:30

提示:

解题思路

这个问题首先可以想到通过最小堆来做。将输入的数组建立一个最小堆,然后每次从堆中弹出两个最小的元素ab,我们结果添加a+b,然后再将a+b添加到最小堆中,接着弹出最小的两个元素,以此类推,直到最后堆的大小小于2为止。

import heapq
class Solution:
    def connectSticks(self, sticks: List[int]) -> int:
        heapq.heapify(sticks)
        res = 0
        while len(sticks) > 1:
            a, b = heapq.heappop(sticks), heapq.heappop(sticks)
            res += a + b
            heapq.heappush(sticks, a + b)
        return res

这是实际上是利用了贪心的思想,我们每次都要消耗最小值。

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题,希望大家指出!!!

「如果我的文章对你有很大帮助,那么不妨~!」

coordinate

谢谢老板O(∩_∩)O~

使用微信扫描二维码完成支付

Responses