【Description】
你正在使用一堆木板建造跳水板。有兩種類型的木板蜀漆,其中長度較短的木板長度為shorter虾攻,長度較長的木板長度為longer。你必須正好使用k塊木板框都。編寫一個(gè)方法搬素,生成跳水板所有可能的長度。
返回的長度需要從小到大排列魏保。
示例:
輸入:
shorter = 1
longer = 2
k = 3
輸出: {3,4,5,6}
提示:
0 < shorter <= longer
0 <= k <= 100000
【Idea】
這個(gè)題主要留意兩點(diǎn):
一個(gè)是返回長度需要順序排列熬尺,一個(gè)是邊界問題, k=0或者shorter=longer的情況
原本想的很復(fù)雜谓罗,用動(dòng)規(guī)思路做了一下粱哼, 寫了個(gè)循環(huán),每次循環(huán)里的set放當(dāng)前的解長度list檩咱。跑完才注意到需要排序揭措,嗨呀
圍繞有序來想切入點(diǎn)就明朗很多胯舷。最短的長度是全員shorter,其次是 shorter(k-1)+longer1,再其次是shorter(k-2)+longer2, 類推得:shorter(k-i)+longeri
最后一項(xiàng)是longer*k绊含, 所以i∈[0, k]
【Solution】
class Solution:
def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
if k == 0:
return []
elif shorter == longer:
return [shorter*k]
return [shorter*k+i*(longer-shorter) for i in range(k+1)]