Leetcode - Pascal's Triangle

Description

link

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

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)

聽說幫這篇按讚的這個月發票都會中喔😘