Description
Given an integer rowIndex, return the rowIndexth (0-indexed) row of the Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: rowIndex = 3 Output: [1,3,3,1]
Example 2:
Input: rowIndex = 0 Output: [1]
Example 3:
Input: rowIndex = 1 Output: [1,1]
Constraints:
0 <= rowIndex <= 33
Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?
Solution
Python3
class Solution:
def getRow(self, rowIndex: int) -> List[int]:
t = [[1], [1, 1]]
for index in range(2, rowIndex + 1):
tt = t[-1]
tmp = [1] + [0] * (index - 1) + [1]
for i in range(1, len(tmp) - 1):
left = tt[i - 1]
right = tt[-1] if i + 1 >= len(tt) else tt[i]
tmp[i] = left + right
t.append(tmp)
return t[rowIndex]C++
class Solution {
public:
vector<int> getRow(int rowIndex) {
int n = rowIndex+1;
vector<int> tri(n,0);
tri[0] = 1;
for (int i = 1; i < n; i++){
for (int j = i; j > 0; j--){
tri[j] += tri[j-1];
}
}
return tri;
}
};