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);elsecurLine.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);elsecurLine.push_back(preLine[j-1] + preLine[j]);}curLine.push_back(1);}return curLine;} };

 

转载于:https://www.cnblogs.com/diegodu/p/4421725.html

总结

以上是生活随笔为你收集整理的Pascal's Triangle II的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。