首页 > 代码库 > Pascal's Triangle

Pascal's Triangle

2024-07-11 07:23:00   229人阅读

Given numRows, generate the first numRows of Pascal‘s triangle.

For example, given numRows = 5,
Return

[     [1],    [1,1],   [1,2,1],  [1,3,3,1], [1,4,6,4,1]]

 1 class Solution { 2 public: 3     vector<vector<int> > generate(int numRows) { 4         vector<vector<int>> sols; 5         if(numRows==0)return sols; 6         vector<int> pre(1,1); 7         sols.push_back(pre); 8         for(int i=1;i<numRows;i++) 9         {10             vector<int> cur;11             cur.push_back(1);12             for(int j=1;j<i;j++)13             {14                cur.push_back(sols[i-1][j-1]+sols[i-1][j]);15             }16             cur.push_back(1);17             sols.push_back(cur);18         }19         return sols;20     }21 };

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?

思路：从后往前加就可以利用一个数组。

 1 class Solution { 2 public: 3     vector<int> getRow(int rowIndex) { 4         vector<int> sols(1,1); 5         for(int i=1;i<rowIndex+1;i++) 6         { 7             sols.resize(i+1,0); 8             for(int j=sols.size()-1;j>=1;j--) 9             {10                 sols[j]=sols[j]+sols[j-1];//!!!!11             }12         }13         return sols;14         15     }16 };

 


联系
我们