代码拉取完成，页面将自动刷新
同步操作将从 doocs/leetcode 强制同步，此操作会覆盖自 Fork 仓库以来所做的任何修改，且无法恢复！！！
确定后同步将在后台操作，完成时将刷新页面，请耐心等待。
你有一些长度为正整数的棍子。这些长度以数组 sticks 的形式给出， sticks[i] 是 第i个 木棍的长度。
你可以通过支付 x + y 的成本将任意两个长度为 x 和 y 的棍子连接成一个棍子。你必须连接所有的棍子，直到剩下一个棍子。
返回以这种方式将所有给定的棍子连接成一个棍子的 最小成本 。
示例 1：
输入：sticks = [2,4,3] 输出：14 解释：从 sticks = [2,4,3] 开始。 1. 连接 2 和 3 ，费用为 2 + 3 = 5 。现在 sticks = [5,4] 2. 连接 5 和 4 ，费用为 5 + 4 = 9 。现在 sticks = [9] 所有木棍已经连成一根，总费用 5 + 9 = 14
示例 2：
输入：sticks = [1,8,3,5] 输出：30 解释：从 sticks = [1,8,3,5] 开始。 1. 连接 1 和 3 ，费用为 1 + 3 = 4 。现在 sticks = [4,8,5] 2. 连接 4 和 5 ，费用为 4 + 5 = 9 。现在 sticks = [9,8] 3. 连接 9 和 8 ，费用为 9 + 8 = 17 。现在 sticks = [17] 所有木棍已经连成一根，总费用 4 + 9 + 17 = 30
示例 3：
输入：sticks = [5] 输出：0 解释：只有一根木棍，不必再连接。总费用 0
提示：
1 <= sticks.length <= 1041 <= sticks[i] <= 104优先队列。
class Solution:
def connectSticks(self, sticks: List[int]) -> int:
h = []
for s in sticks:
heappush(h, s)
res = 0
while len(h) > 1:
val = heappop(h) + heappop(h)
res += val
heappush(h, val)
return res
class Solution {
public int connectSticks(int[] sticks) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int s : sticks) {
pq.offer(s);
}
int res = 0;
while (pq.size() > 1) {
int val = pq.poll() + pq.poll();
res += val;
pq.offer(val);
}
return res;
}
}
class Solution {
public:
int connectSticks(vector<int>& sticks) {
priority_queue<int, vector<int>, greater<int>> pq;
for (int x : sticks) pq.push(x);
int res = 0;
while (pq.size() > 1) {
int val = pq.top();
pq.pop();
val += pq.top();
pq.pop();
res += val;
pq.push(val);
}
return res;
}
};
func connectSticks(sticks []int) int {
h := IntHeap(sticks)
heap.Init(&h)
res := 0
for h.Len() > 1 {
val := heap.Pop(&h).(int)
val += heap.Pop(&h).(int)
res += val
heap.Push(&h, val)
}
return res
}
type IntHeap []int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
*h = append(*h, x.(int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手
