LeetCode-118-杨辉三角

数组

原题地址：杨辉三角

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

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

示例:

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

解答

只需按照题目要求逐行求解即可，具体的实现如下：

/**
 * @param {number} numRows
 * @return {number[][]}
 */
const generate1 = function(numRows) {
    // 空的杨辉三角
    if (numRows === 0) {
        return [];
    }
    // 第一行只有一个1
    let result = [[1]];
    // 从第二行开始处理
    for (let i = 1; i < numRows; i ++) {
        // 第i行的长度为i+1，左右两边的值为1
        let array = new Array(i + 1).fill(1);
        // 处理除两端外剩余的值
        for (let j = 1; j < i; j ++) {
            // 等于上一行左右两边的值之和
            array[j] = result[i - 1][j - 1] + result[i - 1][j]
        }
        // 将第i行加入到结果集中
        result.push(array);
    }
    return result;
};

测试：

let start = new Date();
const test = generate1;
console.log(test(5)); // [ [ 1 ], [ 1, 1 ], [ 1, 2, 1 ], [ 1, 3, 3, 1 ], [ 1, 4, 6, 4, 1 ] ]
console.log(new Date().getTime() - start.getTime()); // 11

时间复杂度： 第i行的处理次数为i-1，所以时间复杂度为等差数列求和，结果为$O(N^2)$
空间复杂度： 同样为等差数列之和，为$O(N^2)$

本文由 李海平 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: Sep 17,2019