118. Pascal's Triangle
Đề Bài
Given an integer numRows, return the first numRows of Pascal's triangle.
In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:
Example 1:
Input: numRows = 5 Output: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
Example 2:
Input: numRows = 1 Output: [[1]]
Constraints:
1 <= numRows <= 30
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(n²)
💾 Không gian
O(n)
Lời Giải
C++
0118-pascals-triangle.cpp
class Solution {
public:
vector<vector<int>> generate(int numRows) {
vector<vector<int>> tri(numRows);
for (int i = 1; i <= numRows; ++i) {
vector<int> row(i, 1);
for (int j = 1; j < i - 1; ++j) {
row[j] = tri[i - 2][j - 1] + tri[i - 2][j];
}
tri[i - 1] = row;
}
return tri;
}
};
Python
0118-pascals-triangle.py
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
ans = []
for i in range(numRows):
tmp = [1] * (i + 1)
for j in range(1, i):
tmp[j] = ans[i - 1][j - 1] + ans[i - 1][j]
ans.append(tmp)
return ans