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)