[LeetCode]-Pascal's Triangle III 杨辉三角问题
Pascal's Triangle
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
] 思路很简单，下面一层的值（除首尾外）都是前一层肩上两值的和。cur[j]=pre[j-1]+pre[j]。
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int> > ret;
if(numRows<1)return ret;
ret.push_back(vector<int>{1});
generate(numRows,1,ret);
return ret;
}
private:
void generate(int numRows,int n,vector<vector<int> > &ret){
if(n==numRows){
return;
}
vector<int> pre=ret.back();
vector<int> cur;
int m=pre.size();
cur.push_back(1);
for(int i=1;i<m;i++){
cur.push_back(pre[i-1]+pre[i]);
}
cur.push_back(1);
ret.push_back(cur);
generate(numRows,n+1,ret);
}
};Pascal's Triangle II
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1].
Note:
Could you optimize your algorithm to use only O(k) extra space?
由于空间受到限制，用滚动数组，解决问题。和[LeetCode]-Unique Paths 矩阵中求两点间所有路线条数 滚动数组的用法类似。但是需要多记录一个“旧变量值”。
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> cur(rowIndex+1,1);
for(int i=1;i<=rowIndex;i++){
int temp=1; //存上一层的j-1值
for(int j=1;j<i;j++){
//cur[j]表示上一层cur[j]
//temp 表示上一层的cur[j-1]
int old=cur[j];
cur[j]=temp+cur[j];
temp=old;
}
}
return cur;
}
};