【LeetCode with JavaScript】119. Pascal’s Triangle II

Love The Way You Lie 2022-05-24 08:42 162阅读 0赞

原题网址：[https://leetcode.com/problems/pascals-triangle-ii][https_leetcode.com_problems_pascals-triangle-ii]  
难度：Easy

#### 问题 ####

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

![这里写图片描述][70_pic_center]

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

**Example:**

输入: 3
    输出: [1,3,3,1]

**Follow up：**

你可以优化你的算法到 O(k) 空间复杂度吗？

#### 思路一 ####

--------------------

更改前一题（）的输出结果，根据输入的行数，构建二维数组，再输出该行的数组，代码如下：

/**
     * @param {number} rowIndex
     * @return {number[]}
     */
    var getRow = function(rowIndex) {
        var outputs = [];
        for(var i = 0; i < rowIndex + 1; i++) {
            var curArr = [i];
            curArr[0] = 1,curArr[i] = 1;
            for(var j = 1; j < i; j++) {
                curArr[j] = outputs[i - 1][j - 1] + outputs[i - 1][j];
            }
            outputs.push(curArr);
        }
        return outputs[rowIndex];
    };

Your runtime beats 88.46 % of javascript submissions.  
运行时间：56ms，且**没达到进阶 O(k) 空间复杂度的要求**，还有改进空间。

#### 思路二 ####

--------------------

因为要求 **O(k) 的空间复杂度**，所以就要改变构建二维数组的思路，就以题目给的例子，思考如何以一维数组体现杨辉三角的数字变化：

输入: 3
    输出: [1,3,3,1]

思路与构建二维数组的思路大体一致，在前一种思路中我们为何要采用二维数组呢？不止因为答案要求我们输出一个二维数组，而且二维数组便于我们取上一行的数组来构建当前行的数组，即下面的这行代码

curArr[j] = outputs[i - 1][j - 1] + outputs[i - 1][j];

而在此题中我们不需要输出二维数组，所以我们没有必要来构建二维数组，我们可以再创建一个新的 `prevRow` 数组来记录前一行的数组。下面是具体代码实现：

/**
     * @param {number} rowIndex
     * @return {number[]}
     */
    var getRow = function(rowIndex) {
        var row = [1];
        for(var i = 1; i < rowIndex + 1; i++) {
            row[0] = 1, row[i] = 1;
            for(var j = 1; j < i; j++) {
               row[j] = prevRow[j - 1] + prevRow[j];
            }
            prevRow = row.slice();
        }
        return row;
    };

Your runtime beats 99.23 % of javascript submissions. 运行时间：52ms，clear！

[https_leetcode.com_problems_pascals-triangle-ii]: https://leetcode.com/problems/pascals-triangle-ii
[70_pic_center]: /images/20220524/00b26d74cfe3429aaf40e73b0db71b50.png