为了装修新房，你需要加工一些长度为正整数的棒材 sticks 。

如果要将长度分别为 X 和 Y 的两根棒材连接在一起，你需要支付 X + Y 的费用。 由于施工需要，你必须将所有棒材连接成一根。

返回你把所有棒材 sticks 连成一根所需要的最低费用。注意你可以任意选择棒材连接的顺序。

• ​​1≤sticks.length≤10^4
• ​​1≤sticks[i]≤10^4

样例 1:

输入：  [2,4,3] 输出：14 解释：先将 2 和 3 连接成 5，花费 5 ；再将 5 和 4 连接成 9 ；总花费为 14 

样例 2:

输入：  [1,8,3,5] 输出：30 

[题解]

根据题意，考虑贪心，我们每次将所有棒材的最短的两根合并，将合并后的棒材放入棒材堆，重复合并最短的，直到棒材只剩下一根。

// minheap 暴力 // 直接将所有值压入 minheap，每次取前两个值相加成 merge，同时将 merge 压入 minheap public class Solution {     /**      * @param sticks: the length of sticks      * @return: Minimum Cost to Connect Sticks      */     public int MinimumCost(List<Integer> sticks) {         if (sticks.size() < 2) {             return 0;         }         PriorityQueue<Integer> minHeap = new PriorityQueue<>();         for (int num : sticks) {             minHeap.add(num);         }         int res = 0;         while (minHeap.size() > 1) {             int merge = minHeap.poll() + minHeap.poll();             res += merge;             minHeap.add(merge);         }         return res;     } } // 排序，双队列 // 先将数组排序，然后开始合并，合并后的值放入 q2 末尾，能够保证 q2 中被押入的值是 // 一定大于前面的值的，每次合并我们考虑 q1,q2 非空以及比较 q1[0]和 q2[0]的大小 public class Solution {     /**      * @param sticks: the length of sticks      * @return: Minimum Cost to Connect Sticks      */     public int MinimumCost(List<Integer> sticks) {         Collections.sort(sticks);         Queue<Integer> q1 = new LinkedList<Integer>();         Queue<Integer> q2 = new LinkedList<Integer>();         for (int i : sticks) {             q1.add(i);         }         int res = 0,merge;         while(q1.size() + q2.size() > 1){             if(q2.isEmpty()){                 merge = q1.poll();                 merge += q1.poll();                 q2.add(merge);                 res += merge;             }             else if (q1.isEmpty()){                 merge = q2.poll();                 merge += q2.poll();                 q2.add(merge);                 res += merge;             }             else {                 if(q1.peek() > q2.peek()){                     merge = q2.poll();                 }                 else {                     merge = q1.poll();                 }                  if (q1.isEmpty()){                     merge += q2.poll();                     q2.add(merge);                     res += merge;                 }                 else if(q2.isEmpty()){                     merge += q1.poll();                     q2.add(merge);                     res += merge;                 }                 else {                     if(q1.peek() > q2.peek()){                         merge += q2.poll();                         q2.add(merge);                         res += merge;                     }                     else {                         merge += q1.poll();                         q2.add(merge);                         res += merge;                     }                    }             }         }         return res;     } } 

《面试软技能指导 2020 版 – BQ / Resume / Project》

试听内容：

• 除了刷题，还有哪些技能是拿到 offer 不可或缺的要素

• 如何提升面试软实力：简历, 行为面试，沟通能力

• 现场模拟面试 – Dealing With Ambiguity

免费试听时间：

北京时间 7 月 27 日 周一 09：30

戳我即可免费报名噢

大佬有話說 (0)