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

 

 

 

方法一：保存所有二位数组

class Solution {    public:        vector
     
       getRow(int rowIdx) {            vector
      
        curLine;            vector
       
        
          >  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
     
       getRow(int rowIdx) {            vector
      
        preLine;            vector
       
         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;        }};