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

The title

Given a non-negative integer numRows, generate the previous numRows of the “Yanghui triangle”. In Yang Hui’s triangle, each number is the sum of the numbers on its upper left and upper right.

Example 1:

Input: numRows = 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]]Copy the code

Example 2:

Input: numRows = 1 Output: [[1]]Copy the code

Tip:

  • 1 <= numRows <= 30

Answer key

Analysis of the problem solving

Yang Hui Triangle Introduction:

Yang Hui’s triangle, a geometric arrangement of binomial coefficients in triangles, appeared in the detailed Explanation of Jiuzhang Algorithm written by Yang Hui, a mathematician in the Southern Song Dynasty, in 1261. In Europe, PASCAL (1623-1662) discovered this mathematical rule in 1654, so this is also known as PASCAL’s triangle. PASCAL’s discovery was 393 years later than Yang Hui’s and 600 years later than Jia Xian’s. Yang Hui’s triangle is a great achievement in the history of Chinese mathematics.

The law of Yang Hui triangle is shown in the question.

Antithesis thought

  1. Define a collection to store the result set
  2. Define a double loop that evaluates the rows as numRows and the columns as0 -> iWhere I represents the current row.
  3. If the current row column is the first or last column, the current value is 1.
  4. Other data in other columns of the current row is equal tore.get(i-1).get(j-) + re.get(i -1).get(j)The sum of the

Complexity analysis

  • O(num * numRow ^2)
  • Space complexity: O(1)

The problem solving code

The solution code is as follows (there are detailed notes in the code) :

class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> re = new ArrayList<>();
        for (int i =0; i< numRows; i++) {
            List<Integer>  row = new ArrayList<>();
            for (int j=0; j<=i; j++) {
                // The first and last data in the row have values of 1
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    / / other data, equal to re. Get (I - 1) get (j) + re. Get (I - 1). Get the sum of (j)
                    row.add(re.get(i -1).get(j -1) + re.get(i -1).get(j));
                }
            }
            re.add(row);
        }
        returnre; }}Copy the code

Feedback results after submission:

The reference information

  • Problem 118: Yang Hui triangle