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

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;
    }
};

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料