# Li Kou question 119 - Yang Hui triangle II

Posted on May 28, 2023, 2 a.m. by Kate Flood
Category: The back-end

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.

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 ListInteger getRow(int rowIndex) {
ListInteger ret = new ArrayList();
ret.add(1); // Initialize the first column
for (int i=0; irowIndex+1; i++){
for (int j=i; j0; j--){
if (j==i){  // The last element of the current line
} 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) {
ListInteger list = new Number119().getRow(4);
System.out.println(list.size());
}
Copy the code``````

# 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

Search