题目描述
用两种尺寸的木板建造跳水板,尺寸分别为longer和shorter,一共使用k块,求可以得到的所有跳水板长度,并由小到大排序。如:shorter=1,longer=2,k=3,最后结果为[3,4,5,6]。
2
题解
思路:数学计算
一共使用k块木板,所以如果longer使用了i块,那么shorter就使用k-i块,基于这样的基本思路可知,本题可以在线性时间内完成,并且用的shorter块数越多,整体跳水板长度越短,因此在计算时shorter个使用个数从k开始逐次递减,可避免之后的排序操作。除上述基本情况外还要考虑两种特殊情况,一是当k=0,则返回空,二是当shorter=longer,则返回的结果为shorter*k(longer*k)。
class Solution:
def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
s=[]
if k==0:
return s
for i in range(0,k+1):
s.append(longer*i+shorter*(-i+k))
s = list(set(s))
s.sort()
return s