题目来自于Leetcode
https://leetcode.com/problems/pascals-triangle/
GivennumRows, generate the firstnumRowsof Pascal’s triangle.
For example, givennumRows= 5,Return
[[1],[1,1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]class Solution {public:vector<vector<int>> generate(int numRows) {vector<vector<int> >res;for(int i=0;i<numRows;i++){vector<int>vec(i+1,1);if(i>1)for(int j=1;j<i;j++)vec[j]=res[i-1][j-1]+res[i-1][j];res.push_back(vec);vector<int>().swap(vec);}return res;}};
Pascal’s Triangle IITotal Accepted:42320Total Submissions:143760
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?
此处有内存要求虽然采用第一种方法可以ac但是明显不符合要求
class Solution {public:vector<int> getRow(int rowIndex) {vector<vector<int> >res;for(int i=0;i<rowIndex+1;i++){vector<int>vec(i+1,1);if(i>1)for(int j=1;j<i;j++)vec[j]=res[i-1][j-1]+res[i-1][j];res.push_back(vec);vector<int>().swap(vec);}return res[rowIndex];}};我们必须重新设计算法。
第一想到的就是pascal三角形的系数会等于N行i列的值等于
（ r
n）
但是
class Solution {public:vector<int> getRow(int rowIndex) {vector<int>res(rowIndex+1,1);if(rowIndex<2)return res;long long nth=1;for(int i=1;i<rowIndex+1;i++)nth*=i;long long rth=1,n_rth=nth;for(int i=1;i<rowIndex;i++){n_rth/=(rowIndex-i+1);res[i]=nth/rth/n_rth;rth*=(i+1);}return res;}};用来存储二项式系数的值很容易在rowIndex=24时候就报错了
最后一种也就是正确的方法是利用分配的空间来计算的具体给出了k=5的具体描述
class Solution {public:vector<int> getRow(int rowIndex) {vector<int>res(rowIndex+1,1);if(rowIndex<2)return res;int t1,t2; for(int i=2;i<=rowIndex;i++){t1=res[0];t2=res[1];for(int j=1;j<i+1;j++){res[j]=t1+t2;t1=t2;t2=res[j+1];}res[i]=1;}return res;}};
My Submissions
QuestionSolution
世界会向那些有目标和远见的人让路(冯两努——香港着名推销商
