1.题目描述

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?

2.解法分析

题目说要优化空间需求,实际上就是要复用空间,于是写出的代码如下:

class Solution {

public:

vector
           
             getRow(int rowIndex) {
           

// Start typing your C/C++ solution below

// DO NOT write int main() function\

//areslipan

vector
           
            curRow;
           

curRow.push_back(1);

if(rowIndex == 0)return curRow;

curRow.push_back(1);

if(rowIndex == 1)return curRow;

vector
           
            result;
           

result.assign(rowIndex+1,1);

int cur;

int nextCur;

for(int i = 2;i<=rowIndex;++i)

{

cur = result[0];

for(int j =1;j

{

nextCur = result[j];

result[j]=cur+result[j];

cur = nextCur;

}

}

return result;

}

};