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;
}
|
评论