Cracking Coding Interview - 16.11 Diving Board

Diving Board: You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.

Hints: #690, #700, #715, #722, #740, #747

Diving Board：跳水台。

解法

看上去有点像走楼梯，你可以一次走1步，也可以一次走2步，让你求有几种走法。

实际上这个问题步一样，你有两种木板，一个长一个短点，要求你使用K块木板连在一起，让你求所有可能的达到的长度。

所以这个问题有点像组合问题，我们把S(x)代表x个短木板达到的长度，L(x)代表x个长木板所达到的长度。那么所有可能的长度有：

1
2
3
4
5
6
7


S(0) + L(k)
S(1) + L(k - 1)
S(2) + L(k - 2)
...
S(k - 2) + L(2)
S(k - 1) + L(1)
S(k) + L(0)

不过问题似乎没有这么简单，比如，当 L(1) = S(2) 时，即一块长木板等于2块短木板，那么有可能存在两种方案总长度一样吗？来证明一下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


l = 长木板长度, s = 短木板长度, d = 短木板块数, k = 总块数, sum = 总长度
可得公式
sum = d * s + (k - d) * l
如果 l = n * s
sum = d * s + (k - d) * n * s

如果存在d1和d2，能够使得sum相等，那就意味着

d1 * s + (k - d1) * n * s = d2 * s + (k - d2) * n * s
(d1 + k * n - d1 * n) * s = (d2 + k * n - d2 * n) * s
              d1 - d1 * n = d2 - d2 * n

如果要是上列等式成立，d1必须等于d2

不过要注意的是，如果 l = s，那么得到的结果总是相同的。这样上面的公式就变成了：
sum = d * s + (k - d) * s
    = k * s

我们可以用一个Set来消除重复结果：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


private static final SHORT = 2;
private static final LONG = 4;

public void divingBoard(int shortLen, int longLen, int k) {
  Set<Integer> possibleLength = new HashSet<>();  
  for (int i = 0; i <= k; i++) {
    possibleLength.put(i * shortLen + (k - i) * longLen);
  }
  return possibleLength;
}

Cracking Coding Interview - 16.11 Diving Board

解法

版权

评论

Cracking Coding Interview - 16.11 Diving Board

解法

版权

相关文章

评论