题解 | #杨辉三角(二)#

题目的主要信息：

给定一个非负索引值 num ，请返回杨辉三角中从上到下第 num 层。索引值从 0 开始。 杨辉三角中，每个数是左上方和右上方的数之和。

方法一：

模拟杨辉三角。用二维数组res模拟杨辉三角。用一个for循环计算第i层的数字，因为杨辉三角中每个数等于左上方和右上方的数之和，所以从res 中取出第i-1层的所有数字，遍历计算第i层的数字。最后返回第num层的数字。

具体做法：

class Solution {
public:
    vector<int> getRow(int num){
        vector<vector<int>> res; //二维数组，用来模拟杨辉三角
        for(int i = 0; i <= num; i++) {
            vector<int> vec(i + 1);//第i层数字
            vec[0] = 1; //第i层第1个数字
            if(i==0){//如果是第0层，只有一个元素
                res.push_back(vec);
                continue;
            }else{
                vector<int> pre=res[i-1];//第i-1层
                for(int j = 1; j < i; j++){
                    //杨辉三角中每个数等于左上方和右上方的数之和
                    vec[j] = pre[j - 1] + pre[j];
                }
            }
            vec[i] = 1; //当前层最后1个数字
            res.push_back(vec);
        }
        return res[num];//返回第num层
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，双重for循环。
• 空间复杂度：$O(n^2)O(n^2)$，res数组大小与num有关，大小为$O(nu{m}^2)O(num^2)$。

方法二：

对方法一进行优化，我们不需要存储整个杨辉三角，只需要上一行的数据就可以求出当前行的数据，因此我们只需用一维数组pre存储最新计算得到的那一层的数据即可，用pre计算当前行的数据vec，然后用vec替换pre，不断滚动往下计算。

具体做法：

class Solution {
public:
    vector<int> getRow(int num){
        vector<int> pre;
        for(int i = 0; i <= num; i++) {
            vector<int> vec(i + 1);//第i层数字
            vec[0] = 1; //第i层第1个数字
            if(i==0){//如果是第0层，只有一个元素
                pre = vec;
                continue;
            }else{
                for(int j = 1; j < i; j++){
                    //杨辉三角中每个数等于左上方和右上方的数之和
                    vec[j] = pre[j - 1] + pre[j];
                }
            }
            vec[i] = 1; //当前层最后1个数字
            pre = vec;
        }
        return pre;//返回第num层
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，双重for循环。
• 空间复杂度：$O(n)O(n)$，pre数组的大小为$O(n)O(n)$。