Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Question 119 Yang Hui triangle II is shown as follows:

Given a non-negative index rowIndex, return the rowIndex row of the “Yang Hui triangle”.

In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Example 1:

RowIndex = 3 output: [1,3,3,1]Copy the code

Example 2:

RowIndex = 0 output: [1]Copy the code

A, thinking

This is very similar to the previous problem, except that you only need to get the data for the row number rowIndex. In fact, we can directly use the idea of the previous problem, first construct the whole Yang Hui triangle, and then return the data of the last line.

But since it’s an advanced problem, we have to follow his advanced requirements. The advanced requirements are as follows:

They’re asking us to only use the extra O(rowIndex) space, and it’s obvious that storing the entire Yang Hui triangle in a two-dimensional array is not going to work.

What is the pattern between the two adjacent lines below?

We find that the result of the current row is only associated with the result of the previous row, and that the first and last element of each row are both 1. So how do you do it using only the O(rowIndex) space?

Since arr[I][j] = arr[i-1][j] + arr[i-1][J-1] (arr[I][j] is not the outer element), it indicates that the current value of the element is only related to the i-th and i-1 elements in the previous row.

Arr [I] = arr[I] + arr[i-1] (arr[I] is the ith element in the previous row)

Since the idea has, so it is not difficult to achieve.

Second, the implementation

The implementation code

And since the first column must be 1 we can start by adding 1 to the array. If the current element is the last, we also need to add 1 to the array, because we need it when we evaluate the next row.

    public List<Integer> getRow(int rowIndex) {
        List<Integer> ret = new ArrayList<>();
        ret.add(1); // Initialize the first column
        for (int i=0; i<rowIndex+1; i++){
            for (int j=i; j>0; j--){
                if (j==i){  // The last element of the current line
                    ret.add(1);
                } else {    // Non-edge elements
                    ret.set(j, ret.get(j) + ret.get(j-1)); }}}return ret;
    }
Copy the code

The test code

    public static void main(String[] args) {
        List<Integer> list = new Number119().getRow(4);
        System.out.println(list.size());
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section