当前位置：首页 > article >正文

《程序员面试金典（第6版）》面试题 16.11. 跳水板

article 2024/11/15 12:24:05

题目描述

你正在使用一堆木板建造跳水板。有两种类型的木板，其中长度较短的木板长度为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

解题思路与代码

这是一道简单题，其目的就是让我们找出跳水板所有可能的长度，并按照升序返回。
因为一共就只有两种类型，然后让你使用k块板子，那么可能性就有k + 1种，我们要做的，就是返回这k + 1种长度的升序序列。

这道题我第一开始是用的while循环 + 双指针 + sort函数去做的。后来我发现根本就不用双指针，直接一个for循环就解决的事情了。不过我还是把两种方法都贴过来，让大家一起来感受一下这道题我的思考过程。

方法一：while循环 + 双指针 + sort函数

我第一开始想的是，用指针left = 0；指针right = k，然后while循环left <= right 这样的话，我们就可以包含所有的情况，当然k为双数的时候会多push一个，我们把它pop掉就好了。

因为这种方法我们只是统计了所有的可能性，并没有排序。所以我们还需要再用sort函数排序一下

具体的代码如下：

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if(shorter == longer && k != 0) return {shorter * k};
        if(k == 0) return {};
        vector<int> result;
        int left = 0;
        int right = k ;
        if(k % 2 == 1){
            while(left <= right){
                result.push_back(left * shorter + right * longer);
                result.push_back(left * longer + right * shorter);
                ++left;
                --right;
            }
        }else{
            while(left <= right){
                result.push_back(left * shorter + right * longer);
                result.push_back(left * longer + right * shorter);
                ++left;
                --right;
            }
            result.pop_back();
        }
        sort(result.begin(),result.end()) ;
        return result;
    }
};

在这里插入图片描述

复杂度分析

时间复杂度：

while循环会执行k/2次，因此循环内部的代码执行次数是O(k/2)；
sort函数的时间复杂度为O(nlogn)，这里n是result数组的大小。在最坏情况下，result数组的大小为k，所以sort的时间复杂度为O(klogk)。
由于O(klogk)大于O(k/2)，所以总的时间复杂度为O(klogk)。

空间复杂度：

用于存储结果的result数组占用的空间大小与其元素个数成正比。在最坏情况下，result数组的大小为k，所以空间复杂度为O(k)。
综上所述，该代码的时间复杂度为O(klogk)，空间复杂度为O(k)。

方法二：优化，不用排序，一个for循环搞定

我们用for循环变量k + 1次，每次添加一个元素，就可以做到题目要我们做的

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if(k == 0) return {};
        if(shorter == longer) return {k * shorter};
        vector<int> result;
        for(int i = 0; i <=k; ++i){
            result.push_back(shorter * (k-i) + longer * i);
        }
        return result;
    }
};