Pascal’s Triangle 系列

LeetCode上有两道关于Pascal’s Triangle的问题，问题一比较简单，问题二有个比较有意思的知识点。纪录如下：

118.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] ]

解答

这道题比较简单，因为每次都把上行的数据存储了起来，所以我们计算新的数据的时候，只要从上行中取出想要的数据就可以了。

class Solution { public: vector<vector<int>> generate(int numRows) { if(numRows <= 0) return vector<vector<int>>(); vector<vector<int>> res(1,vector<int>(1,1)); for(int i = 1; i < numRows; ++i) { vector<int> Row(i+1,1); for(int j = 1; j < i; ++j) { Row[j] = res[i-1][j-1] + res[i-1][j]; } res.push_back(Row); } return res; } };

119. 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].

解答

这一题中只要求返回给定行的数据，题目要求的关键点在于如何以O(k)的存储空间来进行完成功能。

关键在于我们每次生成数据的时候，不再是从数组前端开始，而是从末尾元素开始。因为对于res[j] = res[j]+res[j-1]，如果j从前往后进行计算新数据，就会覆盖后续所要使用的数据，但是如果j从后往前计算新数据，就不会覆盖原有的数据。

class Solution { public: vector<int> getRow(int rowIndex) { vector<int> res(rowIndex+1,1); for(int i = 2; i <= rowIndex;++i) for(int j = i-1; j >= 0;--j) res[j] = res[j] + res[j-1]; return res; } }