跳转至

面试题 16.11. 跳水板

Tags: Easy Recursion Memory

Links: https://leetcode-cn.com/problems/diving-board-lcci/

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

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

示例：

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

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

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!k) return {};

        set<int> us;
        for (int i = 0; i <= k; ++i) {
            int sum = solve(shorter, i)  +solve(longer, k - i);
            us.emplace(sum);
        }

        return vector<int>(us.begin(), us.end());
    }

    inline int solve(int num, int k)
    {
        return num * k;
    }
};

最初没有考虑清除中间过程，这种暴力解法也可以过。

其实这道题应该考虑最终生成的结果数是个可以预先知道的值，如果shorter和longer不等，那么最终结果一定是n + 1个不同的值，就不需要用set了。

用s代表shorter，l代表longer。假设s取了i次，那么l就取了k - i次。所以结果是s * i + l * (k - i)，那么下一个结果就是s * i + l * (k - i) + l - s，因为l和s不等，所以生成的结果一定不同且有序。

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (!k) return {};

        if (longer == shorter) return vector<int>{shorter * k};

        vector<int> res(k + 1);
        res[0] = shorter * k;
        for (int i = k - 1; i >= 0; --i) {
            res[k - i] = res[k - i - 1] + longer - shorter;
        }

        return res;
    }
};