[面试题 16.11][简单] 跳水板

题目描述

面试题 16.11. 跳水板

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

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

示例：

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

提示：

• 0 < shorter <= longer

• 0 <= k <= 100000

解题思路

公式

如果有$i$块shorter木板, 就有$k-i$块longer木板, 所以总长度可以用公式表示.

class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        return ([shorter * (k - i) + longer * (i) for i in range(k + 1)] if shorter != longer else [shorter * k])  if k > 0 else []

递归

本题真正想考察的方案. 但该方案会超时. - -

class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        if k == 0:
            return []
        if shorter == longer:
            return [shorter * k]

        res = []
        seen = set()
        def func(remains, current, count_s, count_l):
            if remains == 0:
                res.append(current)
                return
            if (count_s + 1, count_l) not in seen:  # 注意剪枝
                seen.add((count_s + 1, count_l))
                func(remains - 1, current + shorter, count_s + 1, count_l)
            if (count_s, count_l + 1) not in seen:
                seen.add((count_s, count_l + 1))
                func(remains - 1, current + longer, count_s, count_l + 1)
        func(k, 0, 0, 0)
        return res