LeetCode/面试题16.11.跳水版

面试题 16.11. 跳水板

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为shorter，长度较长的木板长度为longer。你必须正好使用k块木板。编写一个方法，生成跳水板所有可能的长度。

返回的长度需要从小到大排列。

示例：

输入：
shorter = 1
longer = 2
k = 3
输出： {3,4,5,6}

提示：

• 0 < shorter <= longer
• 0 <= k <= 100000

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题思想比较简单，就是三种情况：

1. k为0的时候，此时长度的可能为0，直接返回0
2. shorter 等于longer时，这时只有一种可能性，就是k块shorter或者longer拼接而成的长度
3. 普通情况，有shorter有longer且两者不相等，这里一共有k+1种情况，所以将shorter和longer的组合填入result数组即可

这里有两点问题需要说明：

1. 为什么一共有k+1种可能？

假设这种情况，有shorter和longer两种板子，一共有k块板子，那么在长度组合中，longer的个数应该是从0块递增到k块，即0,1,2,….k，总共k+1块

1. 实现代码中result[i] = (k - i) * shorter + i * longer;如果写成result[i] = i * shorter + (k - i) * longer;就会报错？具体错误如下：

   

该问题确切的说不是问题，只是因为 result 数组顺序是逆序，所以造成 LeetCode 判断结果为错误，我们可以打印出result[i] = i * shorter + (k - i) * longer;最后一个值和result[i] = (k - i) * shorter + i * longer;值作比较来证明，结果是一样的

具体代码如下：

class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        //若一共需要0块模板，则直接返回空
        if (k == 0)
            return new int[0];

        //题目说了0 < shorter <= longer，所以shorter == longer这种情况存在
        //这种情况下直接返回k个shorter或者longer拼接的长度即可
        if (shorter == longer) {
            int[] result = new int[1];
            result[0] = shorter * k;
            return result;
        }

        //这里用k块模板拼接一共有k+1种可能
        int[] result = new int[k + 1];
        for (int i = 0; i < k + 1; i++) {
            result[i] = (k - i) * shorter + i * longer;
        }
        return result;
    }
}