面试题16.11。跳水板题目来源：LeetCodehttps://leetcode-cn.com/problems/diving-board-lcci题目你正在用一堆木板搭建一个跳水板。木板有两种类型，较短的木板长度较短，较长的木板长度较长。您必须正好使用k个木板。编写一个生成所有可能长度的跳水板的方法。返回的长度需要从小到大排列。例子：输入：shorter=1longer=2k=3输出：{3,4,5,6}提示：0短，k>0，会得出什么样的结论。这里先给出结论，再证明。结论：所有长度的跳水板都有k+1个结果，长度为：shorter*k+(longer-shorter)*x，其中0<=x<=k。现在证明如何得出这样的结论：首先假设有k-x块较短的木板和x块较长的木板。那么跳水板的长度为：观察上面的公式，我们知道更短，更长，k都是常量。只有x是可变的。因为longer>shorter，那么longer-shorter一定大于0，那么上式可以看成是一个单调递增的一元线性函数。因为x的值落在[0,k]之间（左闭右闭），那么f(x)就有k+1个结果（x从0到k取）。然后结合开头说的两个特例，三者结合就是本题的解法。根据结论，可能的跳板组合如下：具体实现代码如下。代码实现类解决方案：defdivingBoard(self,shorter:int,longer:int,k:int)->List[int]:#首先处理特殊情况ifk==0:return[]ifshorter==longer:return[shorter*k]#一般longer>shorter,k>0#先生成一个长度为k+1的数组ans=[0]*(k+1)forxinrange(k+1):#代入公式ans[x]=shorter*(k-x)+longer*xreturnans结果总结这道题可以看做数学证明题，先处理特殊情况：当k=0时，表示跳水board无法构建，则返回一个空列表[]；当shorter=longer且boards相等时，则只有一个结果，return[shorter*k]。排除特殊情况后，用一般情况来证明跳板的可能结果。假设有k-x个较短的板和x个较长的板（其中0<=x<=k）；那么跳水板的长度：f(x)=shorter*(k-x)+longer*x，将公式转置，可以得到：f(x)=shorter*k+(longer-shorter)*x；这里，可以看到shorter、longer、k都是常量，只有x的值发生变化，而longer>shorter，那么从上面的公式可以看出是一个单调递增的一元线性函数，而x的值落在[0,k]之间，所以f(x)的结果有k+1种可能。文章原创，欢迎关注和点赞。微信公众号《书所集录》同步更新，欢迎关注交流。
