LeetCode Q118: 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]
]

Solution:
Pascal's Triangle: Each element of current row, expect the boundary elements, is the sum of two elements that are directly on the above row.

	class Solution {
	public:
	vector<vector<int>> generate(int numRows) {
	vector<vector<int> > res;
	if(numRows==0)
	return res;
	for(int i=1; i<=numRows; i++){
	vector<int> newRow;
	vector<int> lastRow;
	if(i>2)
	lastRow=res[i-2];
	for(int j=1; j<=i;){
	if(j==1||j==i){
	newRow.push_back(1);
	j++;
	}
	else
	for(int k=0; k<lastRow.size()-1; ++k, ++j)
	newRow.push_back(lastRow[k]+lastRow[k+1]);
	}
	res.push_back(newRow);
	}
	return res;
	}
	};

view raw Q118PascalTriangle.cpp hosted with ❤ by GitHub

Round 2 solution:

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

view raw Q118Rnd2.cpp hosted with ❤ by GitHub