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

Force buckle 118. Yang Hui triangle

I. Title Description:

Given a non-negative integer numRows, generate the former numRows 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:

Input: numRows = 5 output: [[1], [1, 1], [1, 2, 1],,3,3,1 [1], [1,4,6,4,1]] example 2:

Input: numRows = 1 Output: [[1]]

Tip:

1 <= numRows <= 30

Source: LeetCode link: leetcode-cn.com/problems/pa… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Ii. Analysis of Ideas:

  1. What ideas does this question examine? What’s your thinking?

    This topic is very classic, I do this topic only through mathematical methods to complete the idea. We see that the numbers in each row of the Yanghui triangle are symmetrical, increasing from 1 to a maximum and then decreasing to 1. Then the NTH row has n+1 elements, and most surprisingly, we can find that the size of the MTH element on the NTH row is equal to the size of the combinatorial number \mathcal{C}_n^m, starting at coordinates 0. As for each number equal to the sum of the left and right sides of the previous row, it is also consistent with the property of combination numbers.

  2. Did you pass the problem at the first time? What problems did you encounter? What details should you pay attention to?

    Is a pass, the problem as long as understand the derivation, it is very simple.

  3. There are several solutions, which one has the least time complexity, which one has the least space complexity, and what is the optimal solution? What are other people’s problems? Who’s more efficient? Which language is the fastest to implement in different languages?

    So this is a simple problem, but we see a trick.

Iii. AC Code:

class Solution { public List<List<Integer>> generate(int numRows) { List<List<Integer>> res = new ArrayList<List<Integer>>(); for(int i=0; i<numRows; i++){ List<Integer> row = new ArrayList<Integer>(); for(int j=0; j<i+1; j++){ if(j==0 || j==i){ row.add(1); }else{ row.add(res.get(i-1).get(j-1) + res.get(i-1).get(j)); } } res.add(row); } return res; }}Copy the code

 class Solution:
     def generate(self, numRows: int) -> List[List[int]]:
         if numRows == 0: return []
         res = [[1]]
         while len(res) < numRows:
             newRow = [a+b for a, b in zip([0]+res[-1], res[-1]+[0])]
             res.append(newRow)      
         return res
Copy the code

Iv. Summary:

Big guy think of the second clever method is really a person feel suddenly enlightened ah, again encounter this kind of topic basically have no problem!