LeetCode 119.Pascal's Triangle II (杨辉三角 II)

淡淡的烟草味﹌ 2022-05-08 00:36 176阅读 0赞

题目描述：

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

![PascalTriangleAnimated2.gif][]

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

**示例:**

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

**进阶：**

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

AC C++ Solution:

方法1：

沿用上一题的解决方案，返回第row行即可；

[LeetCode 118.Pascal's Triangle (杨辉三角)][LeetCode 118.Pascal_s Triangle]

class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<vector<int>> r(rowIndex+1);        
            
            for(int i = 0; i <= rowIndex; i++) {
                r[i].resize(i+1);   //第i行有i+1个元素
                r[i][0] = r[i][i] = 1;
                
                for(int j = 1; j < i; j++)
                    r[i][j] = r[i-1][j-1] + r[i-1][j];
            }
            
            return r.back();
        }
    };

方法2：

row0 = 1  
row1 =（row0 \[0\]），（row1 \[1\] + row0 \[0\]）= 1,1  
row2 =（row0 \[0\]），（row1 \[1\] + row1 \[0\]），（row2 \[2\] + row1 \[1\]）= 1,2,1  
row3 =（row0 \[0\]），（row2 \[1\] + row2 \[0\]），（row2 \[2\] + row2 \[1\]）。（row3 \[3\] + row2 \[2\]）= 1,3,3,1

使用一个数组动态规划的方法即能解决:

class Solution {
    public:
        vector<int> getRow(int rowIndex) {
            vector<int> A(rowIndex+1, 0);
            A[0] = 1;
            for(int i=1; i<=rowIndex; i++)     //因为行计数是从0开始,所以第rowIndex行有rowIndex+1个元素
                for(int j=i; j>=1; j--)
                    A[j] += A[j-1];
            return A;
        }
    };

[PascalTriangleAnimated2.gif]: https://upload.wikimedia.org/wikipedia/commons/0/0d/PascalTriangleAnimated2.gif
[LeetCode 118.Pascal_s Triangle]: https://blog.csdn.net/amoscykl/article/details/82964531