1167. Minimum Cost to Connect Sticks

leetcode medium

#array#csharp#heap#leetcode#medium#queue

Task

У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива sticks, где sticks[i] — длина i-й палочки.

Вы можете соединить любые две палочки длиной x и y в одну палочку, заплатив стоимость x + y. Вы должны соединить все палочки, пока не останется только одна палочка.

Верните минимальную стоимость соединения всех данных палочек в одну палочку таким образом.

Пример:

Input: sticks = [5]

Output: 0

Explanation: There is only one stick, so you don't need to do anything. The total cost is 0.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int ConnectSticks(int[] sticks) {
        int totalCost = 0;
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        
        foreach (int stick in sticks) {
            pq.Enqueue(stick, stick);
        }
        
        while (pq.Count > 1) {
            int stick1 = pq.Dequeue();
            int stick2 = pq.Dequeue();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.Enqueue(cost, cost);
        }
        
        return totalCost;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ConnectSticks(vector<int>& sticks) {
        int totalCost = 0;
        PriorityQueue<int, int> pq = new PriorityQueue<int, int>();
        
        foreach (int stick in sticks) {
            pq.Enqueue(stick, stick);
        }
        
        while (pq.size() > 1) {
            int stick1 = pq.Dequeue();
            int stick2 = pq.Dequeue();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.Enqueue(cost, cost);
        }
        
        return totalCost;
    }
}

Java solution

matched/original

import java.util.PriorityQueue;

class Solution {
    public int connectSticks(int[] sticks) {
        int totalCost = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        
        for (int stick : sticks) {
            pq.add(stick);
        }
        
        while (pq.size() > 1) {
            int stick1 = pq.poll();
            int stick2 = pq.poll();
            int cost = stick1 + stick2;
            totalCost += cost;
            pq.add(cost);
        }
        
        return totalCost;
    }
}

JavaScript solution

matched/original

var connectSticks = function(sticks) {
    const pq = new MinPriorityQueue();
    
    for (const stick of sticks) {
        pq.enqueue(stick);
    }
    
    let totalCost = 0;
    
    while (pq.size() > 1) {
        const stick1 = pq.dequeue().element;
        const stick2 = pq.dequeue().element;
        const cost = stick1 + stick2;
        totalCost += cost;
        pq.enqueue(cost);
    }
    
    return totalCost;
};

Go solution

matched/original

import (
    "container/heap"
)

type MinHeap []int

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) {
    *h = append(*h, x.(int))
}
func (h *MinHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

func connectSticks(sticks []int) int {
    pq := &MinHeap{}
    heap.Init(pq)
    for _, stick := range sticks {
        heap.Push(pq, stick)
    }

    totalCost := 0
    for pq.Len() > 1 {
        stick1 := heap.Pop(pq).(int)
        stick2 := heap.Pop(pq).(int)
        cost := stick1 + stick2
        totalCost += cost
        heap.Push(pq, cost)
    }

    return totalCost
}

Explanation

Algorithm

Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 4 палочки следующих длин: sticks=[a1, a2, a3, a4]. Попробуем соединить их слева направо. После первого соединения у нас будет: sticks=[(a1 + a2), a3, a4], стоимость=(a1 + a2). После второго соединения у нас будет: sticks=[(a1 + a2 + a3), a4], стоимость=(a1 + a2)+(a1 + a2 + a3). И, наконец, последняя палочка будет выглядеть так: sticks=[(a1 + a2 + a3 + a4)], стоимость=(a1 + a2)+(a1 + a2 + a3)+(a1 + a2 + a3 + a4).

Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость.

Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций.

😎