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?
Hide Tags
Array
方法一：保存所有二位数组
class Solution { public: vector<int> getRow(int rowIdx) { vector<int> curLine; vector<vector<int> > res; curLine.push_back(1); res.push_back(curLine); if( rowIdx == 0) return curLine; for(int i = 1; i <= rowIdx; i++) { curLine.clear(); for(int j = 0; j < res[i-1].size(); j++) { if(j == 0) curLine.push_back(1); else curLine.push_back(res[i-1][j-1] + res[i-1][j]); } curLine.push_back(1); res.push_back(curLine); } return res[rowIdx]; } };
方法二：cur只和上一行有关，用滚动数组即可实现空间复杂度O（n）
class Solution { public: vector<int> getRow(int rowIdx) { vector<int> preLine; vector<int> curLine; curLine.push_back(1); if(rowIdx == 0) return curLine; for(int i = 1; i <= rowIdx; i++) { preLine = curLine; curLine.clear(); for(int j = 0; j < preLine.size(); j++) { if(j == 0) curLine.push_back(1); else curLine.push_back(preLine[j-1] + preLine[j]); } curLine.push_back(1); } return curLine; } };