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

I. Title Description:

118. Yang Hui Triangle – Force button (LeetCode) (leetcode-cn.com) Given a non-negative integer numRows, generate “Yang Hui triangle” of the previous numRows.

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

Ii. Analysis of Ideas:

Look at how row I is filled.

The first number is always going to be 1,

Starting with the second number, the value of j in each position is equal to the value of j minus 1 in the previous row plus the value of j in the previous row

Except for the last number, which is 1, everything else satisfies this formula.

Such as:

[[1], [1,1], [1,2,1], [1,3,3,1]Copy the code

Let’s think about the last row,

The value 4 at subscript 1 is equal to the value at subscript 0 on the previous row plus the value at subscript 1 on the previous row is equal to 1 plus 3.

The value at subscript 1 is equal to the value at subscript 1 plus the value at subscript 2 is equal to 3 plus 3.

The value at subscript 1 is equal to the value at subscript 2 on the previous row plus the value at subscript 3 on the previous row is equal to 3 plus 1.

Iii. AC Code:

    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for(int i=0; i<numRows; ++i){ ans.push_back(vector<int> ()); vector<int>& cols=ans[i];
            cols.push_back(1);
            for(int j=1; j<i; ++j) cols.push_back(ans[i-1][j-1] + ans[i-1][j]);
            if(cols.size() < i+1) cols.push_back(1);
        }
        
        return ans;
    }
Copy the code

Iv. Summary:

The question itself is very simple, no skills, as long as there is a certain mathematical understanding of Yang Hui triangle on the line.

【 范文 】

Yang Hui Triangle – Yang Hui Triangle – Force buckle (LeetCode) (leetcode-cn.com)

Trick solution: Add the wrong bits one by one, 28ms/12.5MB – Yang Hui Triangle – Force button (LeetCode) (leetcode-cn.com)