Сложность: medium
У вас есть несколько палочек с положительными целыми длинами. Эти длины даны в виде массива 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.
👨💻 Алгоритм:
1⃣Всегда выбирайте две самые маленькие палочки для соединения и продолжайте делать это, пока не останется только одна палочка. Рассмотрим 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).
2⃣Итоговая стоимость может быть переписана следующим образом: стоимость=(3a1 + 3a2 + 2a3 + a4). Как видим, палочки, которые соединяются первыми, включаются в итоговую стоимость больше, чем те, которые выбираются позже. Следовательно, оптимально сначала выбирать меньшие палочки, чтобы получить наименьшую стоимость.
3⃣Для выполнения следующих задач будет оптимальна структура данных min heap (которая обычно реализуется как PriorityQueue в большинстве языков): получить две самые маленькие палочки (stick1 и stick2) из массива; добавить одну палочку (stick1 + stick2) обратно в массив. Эта структура данных дает сложность O(logN) для обеих операций.
😎 Решение
class Solution {
func connectSticks(_ sticks: [Int]) -> Int {
var totalCost = 0
var pq = PriorityQueue(sticks)
while pq.count > 1 {
let cost = pq.dequeue()! + pq.dequeue()!
totalCost += cost
pq.enqueue(cost)
}
return totalCost
}
}
struct PriorityQueue<T: Comparable> {
private var heap: [T]
init(_ elements: [T] = []) {
self.heap = elements
heapify()
}
var count: Int { heap.count }
mutating func enqueue(_ element: T) {
heap.append(element)
siftUp(heap.count - 1)
}
mutating func dequeue() -> T? {
guard !heap.isEmpty else { return nil }
if heap.count == 1 { return heap.removeFirst() }
heap.swapAt(0, heap.count - 1)
let removed = heap.removeLast()
siftDown(0)
return removed
}
private mutating func heapify() {
for index in (0..<(heap.count / 2)).reversed() {
siftDown(index)
}
}
private mutating func siftUp(_ index: Int) {
var childIndex = index
let child = heap[childIndex]
var parentIndex = (childIndex - 1) / 2
while childIndex > 0 && child < heap[parentIndex] {
heap[childIndex] = heap[parentIndex]
childIndex = parentIndex
parentIndex = (childIndex - 1) / 2
}
heap[childIndex] = child
}
private mutating func siftDown(_ index: Int) {
var parentIndex = index
while true {
let leftChildIndex = 2 * parentIndex + 1
let rightChildIndex = 2 * parentIndex + 2
var optionalParentIndex = parentIndex
if leftChildIndex < heap.count && heap[leftChildIndex] < heap[optionalParentIndex] {
optionalParentIndex = leftChildIndex
}
if rightChildIndex < heap.count && heap[rightChildIndex] < heap[optionalParentIndex] {
optionalParentIndex = rightChildIndex
}
if optionalParentIndex == parentIndex { return }
heap.swapAt(parentIndex, optionalParentIndex)
parentIndex = optionalParentIndex
}
}
}Ставь 👍 и забирай 📚 Базу знаний