[Leetcode] 118/119. Pascal’s Triangle

帕斯卡三角形，堪稱數學經典題型，不過概念也是十分的簡單。

Leetcode 118/119 兩題都是給定一個 input rowNums，求帕斯卡三角形。不同的是 118 需要回傳前 rowNums, 119 則只需要第 rowNums。

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        for(int i=0; i<numRows; i++){
            vector<int> tmp;
            for(int j=0; j<=i; j++){
                if(j==0 || j==i)
                    tmp.push_back(1);
                else
                    tmp.push_back(ans.back()[j-1]+ans.back()[j]);
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

根據 118 小修改即可改出 119

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> ans;
        for(int i=0; i<=rowIndex; i++){
            vector<int> tmp;
            for(int j=0; j<=i; j++){
                if(j==0 || j==i)
                    tmp.push_back(1);
                else
                    tmp.push_back(ans[j-1]+ans[j]);
            }
            ans = tmp;
        }
        return ans;
    }
};

但為了更節省空間，我們可以只宣告一個 array 直接計算。需要注意的是要從後面加回來，不然前面的改到就會影響後面的結果了。

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