Preface explains

Algorithm learning, daily brush record.

Subject to connect

Diving board

The subject content

You are building a diving board with a pile of boards, there are two types of boards, the shorter boards are shorter and the longer boards are longer, and you must use exactly K boards. Write a method that generates all possible lengths for a diving board.

The returned length needs to be sorted from smallest to largest.

Example 1:

Input:

shorter = 1

longer = 2

k = 3

Output:,4,5,6 [3]

Explanation:

I can use it 3 times and get 3; Use shorter 2 times and longer 1 time, and get result 4. And so on, to get the final result.

Tip:

0 < shorter <= longer

0 <= k <= 100000

The analysis process

First find out the maximum and minimum value, and then add the difference of longer and shorter one by one through the minimum value, get the middle value.

Notice the shorter cases with k=0 and longer==.

Returns an empty array when k=0.

With longer==shorter, return an array with one element, longer or shorter.

From 1 to K-1, there are k-2 elements in the length array NUMs, and the shorter and longer distributions are constructed.

Each length is equal to the minimum value plus the difference of n longer-shorter ones, which are all shorter ones at the minimum value. By changing one element into longer and finally changing K-1 element into longer, all the lengths excluding the minimum and maximum value can be obtained, and they are arranged from small to large.

Here again, we don’t have to worry about the maximum minus n longer-shorter differences, because this is the same length as the minimum plus n longer-shorter differences, but the order is reversed.

For example, enter shorter=1, longer=2, k=3.

Then the minimum value is 1,1,1, and the maximum value is 2,2,2, as follows:

1,1,1 = > 3

2,2,2 = > 6

Iterating from the first element to the third, changing 1 to 2, then:

2,1,1 = > 4

2, 2, 1 = > 5

One by one = one by one = one by one = one by one

1,2,2 = > 5

1,1,2 = > 4

I’m going to get the same length as going from 1 to 2, but in the opposite order, so I don’t have to go from 2 to 1.

To solve the code

Class Solution {public int[] divingBoard(int shorter, int longer, int k) {if (k == 0) {// There is no board, there is no possible length, Return new int[]{}; } if (shorter == longer) {// When shorter and longer are equal, there is only one possible length, shorter or longer times k is the possible length. Return new int[]{shorter * k}; Int [] nums = new int[k +1]; // The shorter length nums[0] = shorter * k; // The shorter length nums is shorter * k. // From 1 to k-1, nums has k-2 elements in the middle, construct the distribution of shorter and longer for (int I = 1; i <= k - 1; ++ I) {// Each length is equal to the minimum value plus the difference of n longer-shorter ones, which are all shorter ones. One element at a time is changed into longer, and finally k-1 elements are changed into longer, which just gets all the lengths minus the minimum and maximum value. And they're going from small to large, so I don't have to worry about the maximum minus n longer-shorter differences again, because the length I get here is the same as the minimum plus n longer-shorter differences, Nums [I] = nums[0] + (longer-shorter) * I; Nums [k] = longer * k; // return nums; }}Copy the code

Submit the results

The execution time was 1ms, the time beat 100.00% of the user, the memory consumption was 46.2MB, the space beat 58.48% of the user.

The original link

Diving board