题目地址:https://leetcode-cn.com/problems/minimum-cost-to-connect-sticks/

题目描述

Youhave some sticks with positive integer lengths.

Youcan connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. You perform this action until there is one stick remaining.

Return the minimum cost of connecting all the given sticks into one stick in this way.

Example 1:

Input: sticks = [2,4,3]
Output: 14

Example 2:

Input: sticks = [1,8,3,5]
Output: 30

Constraints:

1、 1<=sticks.length<=10^4
2、 1<=sticks[i]<=10^4

题目大意

为了装修新房,你需要加工一些长度为正整数的棒材 sticks。 如果要将长度分别为 X 和 Y 的两根棒材连接在一起,你需要支付 X + Y 的费用。 由于施工需要,你必须将所有棒材连接成一根。 返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。

解题方法

小根堆

这个题是遇到过的微软面试题。

其实题目是让我们生成一个哈弗曼树,做法是使用小根堆,每次选用最小的两根棒材,拼接到一块,然后放入小根堆中。重复这个操作,直至小根堆中只有一个棒材为止。

C++代码如下:

class Solution {
public:
    int connectSticks(vector<int>& sticks) {
        priority_queue<int, vector<int>, greater<int>> que;
        for (int stick : sticks) {
            que.push(stick);
        }
        int res = 0;
        while (!que.empty()) {
            int first = que.top(); que.pop();
            if (!que.empty()) {
                int second = que.top(); que.pop();
                int sum = first + second;
                res += sum;
                que.push(sum);
            }
        }
        return res;
    }
};

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

2022

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发