119. Pascal's Triangle II


Given an indexk, return thekthrow of the Pascal's triangle.

For example, givenk= 3,
Return[1,3,3,1].

Note:
Could you optimize your algorithm to use onlyO(k) extra space?

代码如下:(使用双数组处理，未优化版)

classSolution{public:vector<int>getRow(introwIndex){vector<int>curVec;vector<int>nextVec;if(rowIndex<0)returncurVec;for(inti=0;i<=rowIndex;i++){for(intj=0;j<=i;j++){if(j==0)nextVec.push_back(1);else{if(j>=curVec.size())nextVec.push_back(curVec[j-1]);elsenextVec.push_back(curVec[j]+curVec[j-1]);}}curVec.swap(nextVec);nextVec.clear();}returncurVec;}};


使用思路：

The basic idea is to iteratively update the array from the end to the beginning.

从后到前来更新结果数组。

参考自：https://discuss.leetcode.com/topic/2510/here-is-my-brief-o-k-solution

classSolution{public:vector<int>getRow(introwIndex){vector<int>result(rowIndex+1,0);result[0]=1;for(inti=1;i<rowIndex+1;i++)for(intj=i;j>=1;j--)result[j]+=result[j-1];returnresult;}};


2016-08-12 10:46:10