Leetcode-面试题 16.11. 跳水板

题目描述

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

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

示例：

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

提示：

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

方法：数学

• 首先考虑两种边界情况
  • 如果K = 0 ,那么不能创建任何水板，因此返回空数组。
  • 如果 shorter 和 longer相等，则建造的跳水板的长度是唯一的，都等于 shorter∗k，因此返回长度为 1 的数组，数组中的元素为 shorter*k。

• 然后考虑一般情况，即 shorter < longer 且 k > 0 ，由于短木板和长木板一共使用 k 块 ，所以一共有K + 1中组合，也就是 k + 1种长度
  • 先说结论，假设使用了 i 块 长木板，那么使用了短木板就是 (k - i )块。表达式如下
  • 对于i 属于[0,k] length[i] = shorter * (k - i) + longer * i
  • 为什么每种组合下建造的跳水板长度都是不一样的？证明如下：
    • 第一种情况，有i 块 长木板，那么长度是shorter * (k - i) + longer * i
    • 第二种情况，有 j 块长木板，那么长度是shorter * (k - j) + longer * j
    • 两式相减，得：
    • 
    • 其中(longer > shorter ) 并且 （i < j ），所以乘积小于0，所以任何两种组合下的跳水板长度都是不一样的，使用的长木板越多，跳水板的长度越大。

class Solution {
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0){
            return new int[0];
        }

        // 长木板和短木板长度相等
        if (shorter == longer){
            return new int[]{shorter * k};
        }


        // 一共有 k + 1种不同长度
        // 假设有i块长板子,短板子就是k - i块
        int[] lengths = new int[k + 1];
        for (int i = 0; i <= k; i++) {
            lengths[i] = shorter*(k - i) + longer * i;
        }

        return lengths;
    }
}

复杂度分析

• 时间复杂度：O(k)，其中 k 是木板数量。短木板和长木板一共使用 k块，一共有k+1 种组合，对于每种组合都要计算跳水板的长度。

• 空间复杂度：O(1)。除了返回值以外，额外使用的空间复杂度为常数。

打赏