跳水板
难度:
标签:
题目描述
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.
return all lengths in non-decreasing order.
Example:
Input:
shorter = 1
longer = 2
k = 3
Output: {3,4,5,6}
Note:
- 0 < shorter <= longer
- 0 <= k <= 100000
代码结果
运行时间: 28 ms, 内存: 20.5 MB
/*
* 题目思路：
* 使用Java Stream API生成跳水板所有可能的长度。
* 使用IntStream.rangeClosed(0, k)生成0到k的整数流。
* 对每个整数i，计算shorter和longer的组合长度，转换为IntStream并排序。
*/
import java.util.stream.IntStream;
public class DivingBoardStream {
public int[] divingBoard(int shorter, int longer, int k) {
if (k == 0) return new int[0];
if (shorter == longer) return new int[]{shorter * k};
return IntStream.rangeClosed(0, k)
.map(i -> shorter * (k - i) + longer * i)
.sorted()
.toArray();
}
}
解释
方法:
题解的思路是首先考虑边界情况，即如果k等于0，则没有木板可以使用，返回空列表。如果短木板和长木板的长度相同，则无论如何组合，最终的跳水板长度都是相同的，直接返回长度为k乘以短木板长度的列表。如果短木板和长木板长度不同，则可以通过改变使用短木板和长木板的数量来获取不同长度的跳水板。最短的跳水板长度是全部使用短木板，最长的跳水板长度是全部使用长木板，中间的长度可以通过逐渐替换短木板为长木板来实现，每次替换增加的长度是长木板和短木板长度之差。因此，可以使用range函数生成从最短长度到最长长度，步长为长短木板长度之差的序列。
时间复杂度:
O(k)
空间复杂度:
O(k)
代码细节讲解
🦆
为什么解题思路中考虑当`shorter`等于`longer`时，直接返回长度为k乘以`shorter`的列表，而不是其他任何可能的长度?
▷🦆
在题解的实现中，为何选择使用range函数从最短长度到最长长度，而不是逐个计算每种可能的组合长度?
▷🦆
在题解算法中，输出长度序列的步长为`longer - shorter`，这种步长设置是否适用于所有的输入情况，包括当`shorter`和`longer`非常接近时？
▷