Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1167.html
1167. Minimum Cost to Connect Sticks
Level
Medium
Description
You have some sticks
with positive integer lengths.
You can 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 <= sticks.length <= 10^4
1 <= sticks[i] <= 10^4
Solution
Use the greedy approach. Use a priority queue to store all elements in sticks
, where the minimum element is polled from the priority queue each time. While the priority queue contains at least 2 elements, poll 2 elements, calculate the sum, add the sum to the cost, and offer the sum to the priority queue. Repeat the process until the priority queue only contains 1 element. Then return the cost.
-
class Solution { public int connectSticks(int[] sticks) { PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(); for (int stick : sticks) priorityQueue.offer(stick); int cost = 0; while (priorityQueue.size() > 1) { int stick1 = priorityQueue.poll(); int stick2 = priorityQueue.poll(); int sum = stick1 + stick2; cost += sum; priorityQueue.offer(sum); } return cost; } }
-
// OJ: https://leetcode.com/problems/minimum-cost-to-connect-sticks/ // Time: O(NlogN) // Space: O(N) class Solution { public: int connectSticks(vector<int>& A) { priority_queue<int, vector<int>, greater<>> pq; for (int n : A) pq.push(n); int ans = 0; while (pq.size() > 1) { int a = pq.top(); pq.pop(); int b = pq.top(); pq.pop(); pq.push(a + b); ans += a + b; } return ans; } };
-
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
-
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 }
-
function connectSticks(sticks: number[]): number { const pq = new Heap(sticks); let ans = 0; while (pq.size() > 1) { const x = pq.pop(); const y = pq.pop(); ans += x + y; pq.push(x + y); } return ans; } type Compare<T> = (lhs: T, rhs: T) => number; class Heap<T = number> { data: Array<T | null>; lt: (i: number, j: number) => boolean; constructor(); constructor(data: T[]); constructor(compare: Compare<T>); constructor(data: T[], compare: Compare<T>); constructor(data: T[] | Compare<T>, compare?: (lhs: T, rhs: T) => number); constructor( data: T[] | Compare<T> = [], compare: Compare<T> = (lhs: T, rhs: T) => lhs < rhs ? -1 : lhs > rhs ? 1 : 0, ) { if (typeof data === 'function') { compare = data; data = []; } this.data = [null, ...data]; this.lt = (i, j) => compare(this.data[i]!, this.data[j]!) < 0; for (let i = this.size(); i > 0; i--) this.heapify(i); } size(): number { return this.data.length - 1; } push(v: T): void { this.data.push(v); let i = this.size(); while (i >> 1 !== 0 && this.lt(i, i >> 1)) this.swap(i, (i >>= 1)); } pop(): T { this.swap(1, this.size()); const top = this.data.pop(); this.heapify(1); return top!; } top(): T { return this.data[1]!; } heapify(i: number): void { while (true) { let min = i; const [l, r, n] = [i * 2, i * 2 + 1, this.data.length]; if (l < n && this.lt(l, min)) min = l; if (r < n && this.lt(r, min)) min = r; if (min !== i) { this.swap(i, min); i = min; } else break; } } clear(): void { this.data = [null]; } private swap(i: number, j: number): void { const d = this.data; [d[i], d[j]] = [d[j], d[i]]; } }