題目： LeetCode - 119. Pascal’s Triangle II

題目說明

給一個整數 rowIndex，求第 rowIndex 層 ( 從 0 開始 ) 的帕斯卡三角形的值。( 回傳一個陣列 )
※ 題目希望空間複雜度為 O(rowIndex)。

解題思路

當我們將帕斯卡三角形轉換成陣列的表示方法時：

1
2
3
4
1
1 1
1 2 1
1 3 3 1

會發現對於 pascal[i][j] 來說，其值為 pascal[i - 1][j] + pascal[i - 1][j - 1]。而題目只要求特定的某一層，所以我們從後面開始做就可以省掉上面層數的空間。

參考解法

1
2
3
4
5
6
7
8
9
class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> v(rowIndex + 1);
        v[0] = 1;
        for(int i = 0; i < rowIndex; ++i) for(int j = i + 1; j > 0; --j) v[j] += v[j - 1];
        return v;
    }
};