Diving Board

You are building a diving board using a pile of wooden planks. There are two types of planks, with the shorter plank having a length of shorter and the longer plank having a length of longer. You must use exactly k planks. Write a method to generate all possible lengths of the diving board.

The returned lengths need to be arranged in ascending order.

Example

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

Solution

/**
 * @param {number} shorter
 * @param {number} longer
 * @param {number} k
 * @return {number[]}
 */
var divingBoard = function(shorter, longer, k) {
    if(k === 0) return [];
    if(shorter === longer) return [ longer * k ];
    var target = [];
    for(let i=0; i<=k; ++i) target.push( shorter*(k-i) + longer*i);
    return target;
};

Idea

According to the requirements of this problem, we must use k planks of wood. Therefore, we only need to maintain a fixed-length sliding window of length k. First, fill the window with the shorter planks, and then slide the window, that is, move the shorter plank out and insert the longer plank step by step. Considering two boundary situations, when the length of k is 0, we only need to return an empty array, and when the length of the longer plank is equal to the length of the shorter plank, there is only one situation, which is the length of the plank multiplied by the number of planks. First process the boundary conditions, return an empty array directly when k === 0, and return an array with only one value longer * k when shorter === longer. During the process of sliding the window, when the number of planks needed is k, k+1 situations will be generated, which means that k+1 loops will be needed. Then, take i as the pivot point. Because the lengths are arranged in ascending order, first fill the window with planks of length shorter, and then calculate by sliding one by one.

Daily Exercise

https://github.com/WindrunnerMax/EveryDay

Problem Source

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