Question:
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?
Anwser 1:
class Solution {
public:
vector<int> getRow(int rowIndex) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
vector<int> ret;
for(int i = 0; i <= rowIndex; i++){
if(i == 0) {
ret.push_back(1);
continue;
}
for(int j = i; j >= 0; j--){ // from end to begin
if(j == 0) {
ret[0] = 1;
} else if(j == i){
ret.push_back(1);
}else {
ret[j] = ret[j-1] + ret[j];
}
}
}
return ret;
}
};