首页 > 代码库 > LeetCode: pascal's Triangle
LeetCode: pascal's Triangle
LeetCode: pascal‘s Triangle
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]]地址：https://oj.leetcode.com/problems/pascals-triangle/
算法：pascal‘s triangle的特点是第i+1行第j个元素为第i行第j个元素和第j-1个元素的和，当然头尾两个元素要特殊处理。掌握这个特点，写出代码应该不难：
1 class Solution { 2 public: 3 vector<vector<int> > generate(int numRows) { 4 vector<vector<int> > result; 5 if(numRows < 1){ 6 return result; 7 } 8 result.push_back(vector<int>(1,1)); 9 for(int i = 1; i < numRows; ++i){10 vector<int> temp(i+1);11 temp[0] = 1;12 temp[i] = 1;13 for(int j=1; j < i; ++j){14 temp[j] = result[i-1][j] + result[i-1][j-1];15 }16 result.push_back(temp);17 }18 return result;19 }20 };第二题：
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?
地址：https://oj.leetcode.com/problems/pascals-triangle-ii/
算法：要产生第k行的数组必须先产生第k-1行数组，但跟第k-2行的数组完全无关，所以可以用上一篇文章的方法来达到空间上的限制，而产生数组的方式跟第一题的方法一样。代码：
1 class Solution { 2 public: 3 vector<int> getRow(int rowIndex) { 4 if(rowIndex < 0) return vector<int>(); 5 if(rowIndex == 0) return vector<int>(1,1); 6 vector<int> result1(rowIndex+1); 7 vector<int> result2(rowIndex+1); 8 result1[0] = 1; 9 vector<int> *pre = &result1;10 vector<int> *p = &result2;11 for(int i = 1; i <= rowIndex; ++i){12 (*p)[0] = 1;13 (*p)[i] = 1;14 for(int j = 1; j < i; ++j){15 (*p)[j] = (*pre)[j] + (*pre)[j-1];16 }17 vector<int> *temp = pre;18 pre = p;19 p = temp;20 }21 return *pre;22 }23 };
LeetCode: pascal's Triangle
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。