力扣118. 杨辉三角

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

力扣118. 杨辉三角

一、题目描述：

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5 输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]] 示例 2:

输入: numRows = 1 输出: [[1]]

提示:

1 <= numRows <= 30

来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/pa… 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

1. 这道题考察了什么思想？你的思路是什么？

   这道题目十分经典，做这道题目我只有通过数学方法完成的思路。我们看到杨辉三角每行的数字左右是对称的，从1增大到最大然后减小到1。然后第n行有n+1个元素，最令人惊讶的是，我们可以发现，坐标从0开始，第n行第m个元素的大小与组合数 \mathcal{C}_n^m 的大小相等。至于每个数字与上一行的左右两边数字的和相等，也是符合组合数的性质咯。

2. 做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？

   是一次通过的，该题只要明白了推导关系，就十分简单了。

3. 有几种解法，哪种解法时间复杂度最低，哪种解法空间复杂度最低，最优解法是什么？其他人的题解是什么，谁的效率更好一些？用不同语言实现的话，哪个语言速度最快？

   这就是一道简单的题目，不过看到了一种取巧解法。

   

三、AC 代码：

 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;
     }
 }
复制代码

 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
复制代码

四、总结：

大佬想的第二种巧妙的方法真是令人感到豁然开朗啊，再遇到这种题目基本上没得问题了！