Description:
https://leetcode.com/problems/pascals-triangle-ii/#/description
Algorithm:
If we use only one vector and update the vector each cycle, we might have the problem of losing old data.
While using two vector will take extra time and space.
So we should use some techniques to calculate the elements!
Because we are afraid of missing result[i – 1], we can try to get result with decreasing index!
For example:
1, 3, 3, 1 -> 1,4, 6, 4, 1
If update with increasing index:
1, 3, 3, 1
1, 4, 3, 1
1, 4, 7, 1
1, 4, 7, 11, 1 -> wrong!
If update with decreasing index:
1, 3, 3, 1
1, 3, 3, 4, 1
1, 3, 6, 4, 1
1, 4, 6, 4, 1 -> correct!
Code:
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<int> kthRow(rowIndex + 1, 0);
kthRow[0] = 1;
for (int row = 1; row <= rowIndex; row++)
for (int col = row; col > 0; col--)
kthRow[col] = kthRow[col - 1] + kthRow[col];
return kthRow;
}
};
Timing:
fastest, oms