1167.Minimum-Cost-to-Connect-Sticks

1167. Minimum Cost to Connect Sticks

题目地址

https://leetcode.com/problems/minimum-cost-to-connect-sticks/

题目描述

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

代码

Approach 1: Heap

class Solution {
    public int connectSticks(int[] sticks) {
        PriorityQueue<Integer> pq = PriorityQueue<Integer>();

    for (int i = 0; i < n; i++) {
      pq.add(arr[i]);
    }

    int res = 0;

    while (pq.size() > 1) {
      int first = pq.poll();
      int second = pq.poll();

      res += first + second;
      pq.add(first + second);
    }

    return res;
    }
}

class MinHeap { 
    int[] harr; // Array of elements in heap 
    int heap_size; // Current number of elements in min heap 
    int capacity; // maximum possible size of min heap 

    // Constructor: Builds a heap from 
    // a given array a[] of given size 
    public MinHeap(int a[], int size) 
    { 
        heap_size = size; 
        capacity = size; 
        harr = a; 
        int i = (heap_size - 1) / 2; 
        while (i >= 0) { 
            MinHeapify(i); 
            i--; 
        } 
    } 

    // A recursive method to heapify a subtree 
    // with the root at given index 
    // This method assumes that the subtrees 
    // are already heapified 
    void MinHeapify(int i) 
    { 
        int l = left(i); 
        int r = right(i); 
        int smallest = i; 
        if (l < heap_size && harr[l] < harr[i]) 
            smallest = l; 
        if (r < heap_size && harr[r] < harr[smallest]) 
            smallest = r; 
        if (smallest != i) { 
            swap(i, smallest); 
            MinHeapify(smallest); 
        } 
    } 

    int parent(int i) { return (i - 1) / 2; } 

    // to get index of left child of node at index i 
    int left(int i) { return (2 * i + 1); } 

    // to get index of right child of node at index i 
    int right(int i) { return (2 * i + 2); } 

    // Method to remove minimum element (or root) from min heap 
    int extractMin() 
    { 
        if (heap_size <= 0) 
            return Integer.MAX_VALUE; 
        if (heap_size == 1) { 
            heap_size--; 
            return harr[0]; 
        } 

        // Store the minimum value, and remove it from heap 
        int root = harr[0]; 
        harr[0] = harr[heap_size - 1]; 
        heap_size--; 
        MinHeapify(0); 

        return root; 
    } 

    // Inserts a new key 'k' 
    void insertKey(int k) 
    { 
        if (heap_size == capacity) { 
            System.out.println("Overflow: Could not insertKey"); 
            return; 
        } 

        // First insert the new key at the end 
        heap_size++; 
        int i = heap_size - 1; 
        harr[i] = k; 

        // Fix the min heap property if it is violated 
        while (i != 0 && harr[parent(i)] > harr[i]) { 
            swap(i, parent(i)); 
            i = parent(i); 
        } 
    } 

    // A utility function to check 
    // if size of heap is 1 or not 
    boolean isSizeOne() 
    { 
        return (heap_size == 1); 
    } 

    // A utility function to swap two elements 
    void swap(int x, int y) 
    { 
        int temp = harr[x]; 
        harr[x] = harr[y]; 
        harr[y] = temp; 
    } 

    // The main function that returns the 
    // minimum cost to connect n ropes of 
    // lengths stored in len[0..n-1] 
    static int minCost(int len[], int n) 
    { 
        int cost = 0; // Initialize result 

        // Create a min heap of capacity equal 
        // to n and put all ropes in it 
        MinHeap minHeap = new MinHeap(len, n); 

        // Iterate while size of heap doesn't become 1 
        while (!minHeap.isSizeOne()) { 
            // Extract two minimum length ropes from min heap 
            int min = minHeap.extractMin(); 
            int sec_min = minHeap.extractMin(); 

            cost += (min + sec_min); // Update total cost 

            // Insert a new rope in min heap with length equal to sum 
            // of two extracted minimum lengths 
            minHeap.insertKey(min + sec_min); 
        } 

        // Finally return total minimum 
        // cost for connecting all ropes 
        return cost; 
    } 
};