The puzzle is to generate the first few numRows rows of Pascal’s Triangle.
C++ Coding Exercise – Interview – Pascal’s Triangle
Do you need to keep each row in separate variables (row vector)? Apparently no. The trick here is to have a row vector that represents the last row (n) and base on that construct a new row (n + 1). After each iteration, the row vector is pushed back to the result vector. Of course, for each new row, we increase the size of the vector by one element (number 1 is pushed to the right).
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class Solution { public: vector<vector<int> > generate(int numRows) { vector<vector<int> > r; if (numRows <= 0) { return r; } vector<int> cur; cur.push_back(1); r.push_back(cur); for (int i = 0; i < numRows - 1; i ++) { for (int j = cur.size() - 1; j > 0; j --) { cur[j] += cur[j - 1]; } cur.push_back(1); // right-most 1 r.push_back(cur); } return r; } }; |
class Solution {
public:
vector<vector<int> > generate(int numRows) {
vector<vector<int> > r;
if (numRows <= 0) {
return r;
}
vector<int> cur;
cur.push_back(1);
r.push_back(cur);
for (int i = 0; i < numRows - 1; i ++) {
for (int j = cur.size() - 1; j > 0; j --) {
cur[j] += cur[j - 1];
}
cur.push_back(1); // right-most 1
r.push_back(cur);
}
return r;
}
};Example: 1 – 3 – 3 – 1 ==> 1 – (1+3) – (3+3) – (3+1) and we add 1 to the right at the end of each iteration.
To return the N-th row, we can use a simplified solution: Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm
Pascal Triangle Implementations:
- Teaching Kids Programming – Pascal Triangle Algorithms and Applications
- Coding Exercise – Pascal Triangle II – C++ and Python Solution
- How to Print Pascal Triangle in C++ (with Source Code)
- Compute the Nth Row of a Pascal’s Triangle using Dynamic Programming Algorithm
- GoLang: Generate a Pascal Triangle
–EOF (The Ultimate Computing & Technology Blog) —
loading...
Last Post: Introduction to programming - C Exercise - Circuit
Next Post: Code Snippet Auto Complete on Switch Statement using enum in Visual Studio
iam beginer in programming make me difficult to understand from if(numRows<=0) and for(int i=0; i<numRow-1 i++) my question if(numRow<=0) there is 0,-1,-2 and for i<=numRow-1 i++) its only 0 with other negative number or other positive with from that increment? help me please
In this puzzle, negative inputs are invalid, and that is why it returns [] (empty vector) when it is invalid.