LeetCode：118（Python）—— 杨辉三角（简单）

杨辉三角

概述：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

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

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

方法一：数学法

思路：每行数字左右对称，由 1 开始逐渐变大再变小，并最终回到 1。每个数字等于上一行的左右两个数字之和，可用此性质写出整个杨辉三角。

# 数学法
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        n = numRows
        for i in range(n):
            row = []
            for j in range(0, i + 1):
                if j == 0 or j == i:
                    row.append(1)
                else:
                    row.append(ans[i - 1][j] + ans[i - 1][j - 1])
            ans.append(row)   
        return ans

方法二：错位相加

思路：观察一下规律，发现当前一行只比上一行多了一个元素，最最关键的一点：本行元素等于上一行元素往后错一位再逐个相加。因此我们只要对最后一行单独处理：最后一行首、尾分别添加一个零然后对应位置求和就可以得到新的一行。

# 错位相加
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        n = numRows
        if n == 0:
            return []
        ans = [[1], ]
        while len(ans) < n:
            row = [i + j for i, j in zip([0] + ans[-1], ans[-1] + [0])]
            ans.append(row)
        return ans

总结

我也在纸上比划了半天，为啥就发现不了这个规律呢？