用乐高玩具制作玩具

Question

我最近尝试了一个编码问题，但我的解决方案在面试中没有得到很好的接受(稍微修改一下，以降低谷歌的能力)。

假设一个孩子有几块乐高积木，并想用它们造一个玩具。每个块都有一个大小，当两个块组合在一起时，就会创建一个新的块，其大小是附加块的总和。合并两个块所需的时间等于单个块的大小，找出合并所有乐高的时间最少的组合顺序。

下面是一个示例：

给出以下几个模块：5, 2, 8，孩子可以用以下方法组合它们:5+8= 13 ->儿童花费13单位时间13 +2= 15 ->孩子花费15单位时间--总花费时间: 13 + 15 = 28另一个组合是:2+5=7 7+8= 15总时间: 22

我提出了以下算法，以找到组合所有块所需的最短时间：

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class AssemblyTime {

  int shortestAssemblyTime(List<Integer> lego) {
    Collections.sort(lego);

    int counter = lego.size() - 1;
    int sum = lego.get(0) * (lego.size() - 1);

    for (int i = 1; i < lego.size(); i++) {
      sum += lego.get(i) * counter;
      counter--;
    }

    return sum;
  }


  public static void main(String[] args) {
    int i = new AssemblyTime().shortestAssemblyTime(Arrays.asList(5, 2, 8, 4));
    assert i == 36;
  }
}

测试用例对我是不可用的，但是我的解决方案在10个中的6个(它通过了其他4个)上超时了。

我的算法的思想如下。给定代码中的测试用例，流程如下所示：

2 + 4
2 + 4 + 5
2 + 4 + 5 + 8

因此，最后一个元素被添加一次，last-1被添加两次，直到索引0和1处的元素，这两个元素都被添加了list.length - 1时间。

如何提高该算法的性能？我还可以使用其他数据结构吗？

Answer 1

这里有一个比性能更基本的问题:您的解决方案实际上是不正确的。考虑4个乐高部件，它们都是1码大小的。

1+1=2

2+1=3

3+1=4

2+3+4 = 9的总成本。但是，我们可以通过以下方式更有效地进行组合

1+1=2

1+1=2

2+2=4

8的总成本。一般来说，这个问题是要求您重新发现著名的赫夫曼编码。如果您认为您的大小w块是频率为w的代码字，则解决方案是要求您为这些代码字找到最佳前缀代码的成本。

通过在每一步选取两个最小尺寸的块并将它们组合，得到了最优组合。我们需要一个数据结构，可以有效地找到和删除最小的元素，还需要插入新的元素(我们需要在每一步重新插入组合块)。这可以通过一个最小优先级队列有效地完成。

严格地说，在一个实际的面试中，你可能会被要求证明为什么上述算法提供了最有效的组合。有关这一点，请参阅关于Huffman代码的资源。

Answer 2

你的内环包含一个加法，乘法，减法和两个作业。乘法是不必要的，因为你可以做两个加法和两个作业：

int totalTimeSpent = 0;
int sumOfPair = lego.get(0);
for (int i = 1; i < lego.size(); i++) {
    sumOfPair += lego.get(i);
    totalTimeSpent += sumOfPair;
}

关于数据结构:您是否被迫使用列表？一个带有Arrays.sort(int[])的int数组会更高效。

Answer 3

您可以使用反向顺序并按数组索引+1乘以(除最后一个元素外)：

2 + 4
2 + 4 + 5
2 + 4 + 5 + 8

可转化为：

element    index  result
    8   *   1      8
    5   *   2      10  
    4   *   3      12
    2   *   3      6  
                   36

它允许您移除反向计数器。此外，您还可以使用Array，它消耗更少的内存。

以下是我的实现：

class AssemblyTime {

    int shortestAssemblyTime(Integer... lego) {
      Arrays.sort(lego, Collections.reverseOrder());
      int sumOfLastElement = lego[lego.length - 1] * (lego.length - 1);
      return IntStream.range(1, lego.length)
              .map(i -> lego[i] * (i + 1))
              .sum() + sumOfLastElement;
    }

    public static void main(String[] args) {
        int i = new AssemblyTime().shortestAssemblyTime(5, 2, 8, 4);
        assert i == 36;
    }
}