Description
Given an integernumRows, 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
Intuition
The first core concept： Handle exceptions when numRows equals one and two.
The second core concept： Use recursion to traverse each level of the Pascal's triangle, and use loops to generate the elements of each layer.
Approach
According to the picture in the question, all of the elements in each layer is the sum of the two elements from the previous layer, except the elements in the first and the second layer, also the first and last elements of each layer.
Complexity
- Time complexity: O(numRows²)
- Space complexity: O(numRows²)
Code
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
self.pascal = [[1]]
self.total = 0
self.total = numRows
if numRows == 1:
return self.pascal
self.pascal.append([1,1])
if numRows == 2:
return self.pascal
self.recursion(3)
return self.pascal
def recursion(self, current_floor: int):
row = []
for i in range(current_floor):
if i==0 or i==current_floor-1:
row.append(1)
continue
row.append(self.pascal[current_floor-2][i-1] + self.pascal[current_floor-2][i])
self.pascal.append(row)
if self.total == current_floor:
return
return self.recursion(current_floor+1)
聽說幫這篇按讚的這個月發票都會中喔😘
