pascal-s-triangle

Pascal’s Triangle – LeetCode 118

Problem

Description

Given numRows, generate the first numRows of Pascal’s triangle.

Example

For example, given numRows = 5,
Return

[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]

Answer

Original

Code

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        if(numRows == 0) return vector<vector<int>>();
        vector<vector<int>> result;
        result.push_back(vector<int>({1}));
        for(int i = 1; i != numRows; ++i){
            vector<int> tmp;
            for(int j = 0; j <= i; ++j){
                int left = j == 0? 0: result[i-1][j-1];
                int right = j == i? 0: result[i-1][j];
                tmp.push_back(left+right);
            }
            result.push_back(tmp);
        }
        return result;
    }
};

思路

简单的生成算法。时间复杂度$O(n^2)$，空间复杂度$O(n^2)$。
耗时$3$ ms，排名$95.04\%$

Better

思路

还有就是组合公式法，但恕我直言，考虑到连续的阶乘极有可能导致溢出，所以并不提倡，就不写了。

Code

下面是一个很不错的写法

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        vector<vector<int>> r(numRows);

        for (int i = 0; i < numRows; i++) {
            r[i].resize(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;
    }
};