This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

1. Title Description

Interview question 16.11. Diving board

You’re building a diving board out of a pile of planks. There are two types of boards, with shorter boards and longer boards. You have to 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: [3,4,5,6] Use shorter 2 times and longer 1 time, and get result 4. And so on, to get the final result.

Second, train of thought analysis

The other

  • This problem is very close to our life, in our daily many scenes will encounter the combination of problems. The topic of this question is also relatively simple. The website suggests the skills needed arerecursive,Memory, 。
  • Either way you can solve the problem. We’re not going to hide the recursion here. It’s a cliche to think that algorithms can be implemented and that they’re not really complicated.

  • First we build a tree, and the root node is an empty combination. Then, with the increase of the number of layers, each node can be mounted with a node, which are respectively long board and short board.
  • We think of the figure above as a binary tree. K is the height of the binary tree. And the leaves are our final result set. So in this case we can store all the result sets from 0 to k in terms of a binary tree. But the memory usage must be high. Because we need to store a lot of data that we don’t need
  • Based on binary tree analysis, it is not difficult to find that we only need leaf nodes. And the leaves of binary trees are ordered. It is not difficult to find that the minimum value of a binary tree leaf node is short*k. We define the result set group as result[]. So let’s first remember one conclusion

r e s u l t [ 0 ] = s h o r t e r ∗ k ; result[0] = shorter * k ;

The result set

  • It says that the leaves of the binary tree are our result set, which is not quite accurate. Duplicate data occurs in leaf nodes

  • The length of the diving board in the two leaf nodes is the same. Therefore, complete leaf nodes do not meet the requirements of our result set. But we get the initial value of the result set by analyzing the properties of binary tree
  • As we recall, we need to use K and boards. It’s a combination of long and short boards. So he’s going to have 0 to K possible combinations for the long boards

  • So the length of our result set is zeroK+1. And the first element is shorter* K.

Dynamic programming of deformation

  • I’m sure some of you can see that it’s a little bit like dynamic programming. Our initial value is shorter* K. The length is fixed. So as long as we can determine the transformation equation, we’re done.
  • Since there are only two templates to choose from, we let I represent the number of long boards, where I ranges from [0,k]. So the relative number of short boards is k minus I. So when the long board is I, the length is zero

f ( i ) = s h o r t e r ∗ ( k – i ) + l o n g e r ∗ i f(i) = shorter*(k-i) + longer * i
  • And we can get that from this formula

f ( i + 1 ) – f ( i ) = ( s h o r t e r ∗ ( k – ( i + 1 ) ) + l o n g e r ∗ ( i + 1 ) ) – ( s h o r t e r ∗ ( k – i ) + l o n g e r ∗ i ) = s h o r t e r ∗ ( – 1 ) + l o n g e r ∗ 1 = l o n g e r – s h o r t e r f(i+1)-f(i) = (shorter * (k-(i+1)) + longer * (i+1)) – (shorter*(k-i) + longer * i) = shorter * (-1) + longer * 1 = longer – shorter
  • So this is the transfer equation that we’re familiar with

f ( i + 1 ) = ( l o n g e r – s h o r t e r ) + f ( i ) f(i+1) = (longer-shorter) + f(i)

AC code

public int[] divingBoard(int shorter, int longer, int k) {
    if (k == 0) {
        return new int[] {}; }if (shorter == longer) {
        return new int[]{shorter * k};
    }
    int[] arr = new int[k+1];
    arr[0] = k * shorter;
    for (int i = 1; i < arr.length; i++) {
        arr[i] = (longer - shorter) + arr[i - 1];
    }
    return arr;
}
Copy the code

  • The idea is to try to change

Four,

  • Algorithms are important, but mathematics can’t be lost. A lot of algorithms are combined with mathematical formulas.
  • Above, we combine binary tree + mathematical formula to transform this problem into dynamic programming

Thumb up: