众所周知，杨辉三角是二项式系数在三角形中的一种几何排列，中国南宋数学家杨辉1261年所著的《详解九章算法》一书中出现。

image

杨辉三角的特点就是每一行都是以1开头和结尾，而中间的数等于左上角的数加上右上角的数的和。并且不难发现，第n行的个数与n相等。（第1行【1】，第2行【1,1】，第三行【1,2,1】）

image

那么如何通过给定一个行数n（非负整数），获得此时杨辉三角的前n行呢（返回一个二维数组）？
例子1：

输入:n= 1

输出:[[1]]

例子2：

输入:n= 5

输出:[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

思路：

通过仔细观察杨辉三角，会发现它中间数等于上方两数之和的特点是从第三行（也就是n=3）开始的，所以可以把当n=1和n=2时，分开讨论，以免逻辑混乱。同时，还需要一个变量来储存前一行的数组（第n-1行），这样才能在第n行时能够计算中间值。并且每一行的第一个数和最后一个数都为1，所以可以声明一个数组里面只有一个数1（[1]），在计算完中间数并且添加进当前数组之后，最后在末尾添加一个数1（[...newArray, 1]）。

题解：

1、首先处理n=1和n=2的情况。

    if(n === 1) return [[1]];

    if(n === 2) return [[1], [1,1]];

2.既然已经处理掉n为1和2的情况，那么当n > 2时，也需要返回前两行的数组，所以声明一个数组把前两行当做初始值。

    let ans = [[1], [1,1]];

3、从第三行开始，外部使用一个for循环遍历所有行数，内部使用for循环计算出中间数并且添加到当前数组中。

    // i从2开始也就是第三行开始
    for(let i = 2; i < n; i++){
        // 声明当前行的数组并把首个1放入
        let newArray = [1];
        // 定义前一行（n-1行）的数组用来计算当前行的中间数
        let prevArray = ans[i-1];
        // 当前行的数组第一个数为1并且已经添加，所以从第二个开始
        // 当前行的数组长度为前一行的长度加1，
        for(let j = 1; j < prevArray.length; j++){
            // 计算中间值
            newArray.push(prevArray[j] + prevArray[j - 1]);
        }
        // 添加末尾1
        newArray = [...newArray, 1];
        // 合并每一行数组
        ans = [...ans, newArray];
    }

测试结果：
示例：n = 8
结果：[[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1],[1,5,10,10,5,1],[1,6,15,20,15,6,1],[1,7,21,35,35,21,7,1]]

完整代码：

function generate(n: number): number[][] {
    if(n=== 1) return [[1]];
    if(n=== 2) return [[1], [1,1]];
    let ans = [[1], [1,1]];
    for(let i = 2; i < n; i++){
        let newArray = [1];
        let prevArray = ans[i-1];
        for(let j = 1; j < prevArray.length; j++){
            newArray.push(prevArray[j] + prevArray[j - 1]);
        }
        newArray = [...newArray, 1];
        ans = [...ans, newArray];
    }
    return ans;
};