原题地址（简单）

方法1—直接法(递推)

思路

直接根据题意做，不过不如官方写的代码好。

代码

我的：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        if(rowIndex == 0)  return {1};
        vector<int> v;
        v.push_back(1);
        v.push_back(1);
        for(int i=0; i<rowIndex - 1; i++) {
            for(int j = 0; j < v.size() - 1; j++) {
                v[j] += v[j+1];
            }
            v.insert(v.begin(), 1);
        }
        return v;
    }
};

官方代码如下：

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            for (int j = i; j > 0; --j) {
                row[j] += row[j - 1];
            }
        }
        return row;
    }
};

时空复杂度

时间

空间

（不考虑返回值所占用空间）

方法2—线性递推

思路

由组合数公式 ，可以得到同一行的相邻组合数的关系。由于，利用上述公式我们可以在线性时间计算出第 nn 行的所有组合数。

代码

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row(rowIndex + 1);
        row[0] = 1;
        for (int i = 1; i <= rowIndex; ++i) {
            row[i] = 1LL * row[i - 1] * (rowIndex - i + 1) / i;   // 1LL表示long long类型
        }
        return row;
    }
};

时空复杂度

时间 空间