Amazon components assembly

Posted on | Edited on | Views: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/*
第一题：零件组装题。题目意思就是有一堆零件，每个零件的尺寸和组装需要的时间是一样的。输入各个零件的尺寸的list，要求输出最短的总的 accumulated 组装时间。这么说估计也很难描述清楚，直接上例子：
比如输入的list是 {8， 4， 6， 12}。
1. 先选 4 和 6组装到一起，形成 size 为 10 的新零件。目前为止耗时为10。零件的 list 变为 {8， 10， 12}
2. 再选 8 和 10 组装到一起，形成 size 为 18 的新零件。目前为止耗时为 10 + 18 = 28。零件的 list 变为 {12， 18}
3. 最后 把 12 和 18 组装到一起，形成 size 为 30 的新零件。目前为止耗时为 10 + 18 + 30 = 58。
最后输出 58 就可以了。

解题思路：把所有零件先放到 min-heap (PriorityQueue for Java)中。然后每次 poll 两个最小的，加起来形成新零件，然后放回到min-heap中。如此循环直至 min-heap 中只有一个零件为止。在循环过程中记录总的累积时间就行了。这个题一定要秒掉，为后面的第二题赢得时间。
*/
import java.util.PriorityQueue;

class Solution {
    static int minAssembleTime(int[] a){
        if(a.length==1) return a[0];
        PriorityQueue<Integer> q=new PriorityQueue<>();
        for (int i:a ) q.offer(i);
        int res=0;
        while(q.size()>1){
            int m=q.poll();
            int n=q.poll();
            res+=m+n;
            q.offer(m+n);
        }
        return res;
    }
}

public class MyClass {
    public static void main(String[] args) {
        int[] a={8,4,6,12};
        System.out.println(Solution.minAssembleTime(a));
    }
}
0%