Lintcode 1872 · Minimum Cost to Connect Sticks [Python]

本文主要是介绍Lintcode 1872 · Minimum Cost to Connect Sticks [Python]，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目在下方。读题目，有点儿费解，但是基本思路就是每次选择最小的棍子和第二小的棍子，加起来，丢回棍子堆里，然后继续重复，直到只剩下一个整的棍子。很容易想到用堆。

import heapq
class Solution:
    """
    @param sticks: the length of sticks
    @return: Minimum Cost to Connect Sticks
    """
    def MinimumCost(self, sticks):
        # write your code here
        heap = []
        for idx, stk in enumerate(sticks):
            heapq.heappush(heap, stk)
        res = 0
        while len(heap) != 1:
            x = heapq.heappop(heap)
            y = heapq.heappop(heap)
            res += x
            res += y
            newstk = x + y
            heapq.heappush(heap, newstk)
        #res += heap[0]
        return res

1872 · Minimum Cost to Connect Sticks
Algorithms
Medium
Accepted Rate
71%

DescriptionSolutionNotesDiscussLeaderboard
Description
In order to decorate your new house, you need to process some sticks with positive integer length.
You can connect any two sticks of lengths X and Y into one stick by paying a cost of X + Y. Due to the construction needs, you must connect all the bars into one.
Return the minimum cost of connecting all the given sticks into one stick in this way.
Please note that you can choose any order of sticks connection

1 \leq sticks.length \leq 10^41≤sticks.length≤10
4

1 \leq sticks[i] \leq 10^41≤sticks[i]≤10
4

Example
Example 1:

Input:
[2,4,3]
Output:
14
Explanation:
First connect 2 and 3 to 5 and cost 5; then connect 5 and 4 to 9; total cost is 14
Example 2:

Input:
[1,8,3,5]
Output:
30
Tags
Heap
Greedy

这篇关于Lintcode 1872 · Minimum Cost to Connect Sticks [Python]的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！