LeetCode刷题-跳水板
前言说明
算法学习，日常刷题记录。
题目连接
题目内容
你正在使用一堆木板建造跳水板，有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer，你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。
返回的长度需要从小到大排列。
示例1:
输入：
shorter = 1
longer = 2
k = 3
输出： [3,4,5,6]
解释：
可以使用3次shorter，得到结果3；使用2次shorter和1次longer，得到结果4。以此类推，得到最终结果。
提示:
0 < shorter <= longer
0 <= k <= 100000
分析过程
先找出最大值，最小值，再通过最小值逐个相加longer和shorter的差，得到中间的值。
注意k=0和longer==shorter的情况。
当k=0时，返回空数组。
当longer==shorter时，返回只有一个元素的数组，元素为longer或shorter。
从1遍历到k-1，长度数组nums中间有k-2个元素，构造其中shorter和longer的分布情况。
每个长度等于最小值加上n个longer-shorter的差，最小值时全部是shorter，每次把一个元素变为longer，最后把k-1个元素变为longer，刚好就得到除去最小值和最大值的所有长度，而且还是从小到大排列的。
这里不用再一次考虑最大值减去n个longer-shorter的差的情况，因为这里得到的长度和最小值加上n个longer-shorter的差是一样的，只是顺序刚好颠倒过来。
例如，输入shorter=1，longer=2，k=3。
那么最小值为1,1,1，最大值为2,2,2，如下：
1,1,1 => 3
2,2,2 => 6
从第一个元素起遍历到第三个元素，逐个把1变为2，那么就是：
2,1,1 => 4
2,2,1 => 5
如果是逐个把2变为1，那么就是：
1,2,2 => 5
1,1,2 => 4
得到的长度结果和逐个把1变为2是一样的，只是顺序相反了，所以不需要逐个把2变为1。
解答代码
class Solution {
public int[] divingBoard(int shorter, int longer, int k) {
if (k == 0) {
// 当k为0时，没有木板，没有可能的长度，返回空数组
return new int[]{};
}
if (shorter == longer) {
// 当shorter和longer相等时，只有一种可能的长度，shorter或longer乘以k就是可能的长度
return new int[]{shorter * k};
}
// 定义长度数组nums，数量是k+1
int[] nums = new int[k + 1];
// 注意：这里的长度数组nums，需要从小到大排列
// 长度数组nums的第一个长度是，全部木块都用shorter长度
nums[0] = shorter * k;
// 从1遍历到k-1，长度数组nums中间有k-2个元素，构造其中shorter和longer的分布情况
for (int i = 1; i <= k - 1; ++i) {
// 每个长度等于最小值加上n个longer-shorter的差，最小值时全部是shorter，每次把一个元素变为longer，最后把k-1个元素变为longer，刚好就得到除去最小值和最大值的所有长度，而且还是从小到大排列的，这里不用再一次考虑最大值减去n个longer-shorter的差的情况，因为这里得到的长度和最小值加上n个longer-shorter的差是一样的，只是顺序刚好颠倒过来
nums[i] = nums[0] + (longer - shorter) * i;
}
// 长度数组nums的最后一个长度是，全部木块都用longer长度
nums[k] = longer * k;
// 最后返回长度数组nums
return nums;
}
}
提交结果
执行用时1ms，时间击败100.00%的用户，内存消耗46.2MB，空间击败58.48%的用户。
运行结果
原文链接
原文链接：跳水板
