程序员面试金典 - 面试题 16.11. 跳水板

题目难度: 简单

原题链接

今天继续更新程序员面试金典系列, 大家在公众号 算法精选 里回复 面试金典 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

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

示例 1

• 输入：
  • shorter = 1
  • longer = 2
  • k = 3
• 输出：
  • [3,4,5,6]
• 解释：
  • 可以使用 3 次 shorter，得到结果 3；
  • 使用 2 次 shorter 和 1 次 longer，得到结果 4 。
  • 以此类推，得到最终结果。

提示：

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

题目思考

1. 所有可能的长度有哪些组合?
2. 如何不借助排序实现从小到大返回长度?

解决方案

思路

• 分析题目, 要想恰好使用 k 块木板, 假设长木板用了 x 个, 那么短木板肯定使用了 k-x 个
• 我们可以从 0 到 k 遍历 x (包括 0 和 k), 每次长木板多用一个, 而短木板少用一个, 这样得出的总和一定是从小到大的
• 特别注意, 如果 k=0 的话直接返回空数组, 不能进入上述循环, 否则会错误返回一个长度为 0 的值
• 另外如果短木板和长木板长度相同, 则不管使用多少个短木板, 最终总和都相同, 也需要特殊处理这种情况
• 下面代码就对应了上面的整个过程, 且每一步有详细的注释, 方便大家理解

复杂度

• 时间复杂度 O(K): 只遍历了 K 个值
• 空间复杂度 O(1): 只使用了几个常数空间的变量

代码

class Solution:
    def divingBoard(self, shorter: int, longer: int, k: int) -> List[int]:
        # 贪心+枚举
        # 最小长度是使用k个shorter, 最大是使用k个longer
        if k == 0:
            # 注意k=0的时候直接返回空
            return []
        if shorter == longer:
            # 注意shorter和longer相等时直接返回唯一一种情况
            return [shorter * k]
        res = []
        for x in range(k + 1):
            # 注意这里的x取值范围是闭区间[0,k], 因为短的或长的都可以只使用0个
            res.append(longer * x + shorter * (k - x))
        return res

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊