LeetCode 面试题 16.11. 跳水板
题目描述
题意分析
必须恰好使用
k块木板，每块长度只能是shorter或longer，返回所有不同的总长度并按升序排列。木板的排列顺序不影响长度，因此不必逐块枚举选择，只需统计长木板用了多少块。
k == 0时没有跳水板，返回空数组；两种木板等长且k > 0时，无论如何选择都只有一个总长度。
解法：枚举长木板数量
核心思路
[!blue]
设长木板使用
\[L_i=longer\times i+shorter\times(k-i)\]i块，那么短木板必然使用k - i块，总长度为：每个合法搭法都对应某个
i，反过来0 <= i <= k的每个数量也都能实际搭出，因此枚举这些数量既不会漏解，也不需要区分木板排列。将一块短木板换成长木板，长度恰好增加
longer - shorter。当两种长度不同时，这个差为正，按i = 0..k得到的k + 1个答案天然严格递增，不需要去重或排序；等长时增量为 0，单独返回一次即可。
解题步骤
- 若
k == 0，直接返回空数组。- 若
shorter == longer，返回唯一长度shorter * k。- 否则枚举长木板数量
i = 0..k，把longer * i + shorter * (k - i)写入答案。
代码实现
// i 表示长木板数量；i 从 0 到 k 时答案自然升序。
class Solution {
public int[] divingBoard(int shorter, int longer, int k) {
if (k == 0) {
return new int[0];
}
if (longer == shorter) {
return new int[] {
longer * k
};
}
int[] answer = new int[k + 1];
for (int i = 0; i < k + 1; ++i) {
answer[i] = longer * i + shorter * (k - i);
}
return answer;
}
}
// i 表示长木板数量；i 从 0 到 k 时答案自然升序。
func divingBoard(shorter int, longer int, k int) []int {
if k == 0 {
return []int{}
}
if longer == shorter {
return []int{
longer * k,
}
}
answer := make([]int, k+1)
for i := 0; i <= k; i++ {
answer[i] = longer*i + shorter*(k-i)
}
return answer
}
复杂度分析
- 时间复杂度：$O(k)$；两种木板等长或
k == 0时为 $O(1)$。由于最多有 $k+1$ 个不同答案，线性时间也是输出下界。- 空间复杂度：除返回数组外为 $O(1)$；返回结果占 $O(k)$。
关键点总结
[!green]
- “恰好使用
k块”把选择压缩成一个变量：长木板数量确定后，短木板数量也随之确定。- 不同排列不是不同答案，组合计数能直接消除指数级重复。
- 在
longer > shorter的前提下，枚举顺序就是答案升序，无需排序。
易错点总结
[!yellow]
- 对每块木板回溯二选一：会枚举大量长度相同的排列，时间从线性增加为指数级。
k == 0返回[0]：题意要求没有木板时返回空数组，不是长度为零的方案。- 忽略两种木板等长：所有枚举结果都会重复，应只返回唯一长度。
- 循环只到
i < k：会漏掉全部使用长木板的最大长度，枚举范围必须包含 $k$。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！