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

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