力扣118. 杨辉三角

力扣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）链接：https://leetcode-cn.com/problems/pascals-triangle著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、思路分析：

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

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

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

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

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

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

三、AC 代码：

classSolution {

   publicList<List<Integer>>generate(intnumRows) {

       List<List<Integer>>res=newArrayList<List<Integer>>();

       for(inti=0;i<numRows;i++){

           List<Integer>row=newArrayList<Integer>();

           for(intj=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);

       }

       returnres;

   }

}

classSolution:

   defgenerate(self, numRows: int) ->List[List[int]]:

       ifnumRows == 0: return []

       res = [[1]]

       whilelen(res) <numRows:

           newRow = [a+bfora, binzip([0]+res[-1], res[-1]+[0])]

           res.append(newRow)      

       returnres

四、总结：

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