面试题 16.11

You are building a diving board by placing a bunch of planks of wood end-to-end. There are two types of planks, one of length shorter and one of length longer. You must use exactly K planks of wood. Write a method to generate all possible lengths for the diving board.

return all lengths in non-decreasing order.

Example:

Input: shorter = 1 longer = 2 k = 3 Output: {3,4,5,6} Note:

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

Solutions

1. hashset O(k)

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k <= 0) return {};
        unordered_set<int> seen;
        for (int i = 0; i <= k; i++) {
            seen.insert(shorter * i + longer * (k - i));
        }
        vector<int> lens(seen.begin(), seen.end());
        sort(lens.begin(), lens.end());

        return lens;
    }
};

1. math O(k)

2. reference: https://leetcode-cn.com/problems/diving-board-lcci/solution/qing-xi-yi-dong-de-shu-xue-tui-dao-che-di-nong-don/
3. The key point is: length of all possible combinations of (shorter * i + longer * (k - i)) are different than each other. Thus the hashset can be omitted.

   • This is true only when shorter != longer, otherwise their is only one answer.

   • Proof:

len = f(i) = shorter * i + longer * (k - i)
           = shorter * i - longer * i + longer * k
           = (shorter - longer) * i + longer * k

As this is a monotonically decreasing function, `f(i)` is unique for each different i.

class Solution {
public:
    vector<int> divingBoard(int shorter, int longer, int k) {
        if (k <= 0) return {};
        if (shorter == longer)
            return {shorter * k};

        vector<int> lens;
        for (int i = 0; i <= k; i++)
            lens.push_back(longer * i + shorter * (k - i));

        return lens;
    }
};