Leetcode # 118. Pascal’s Triangle

https://leetcode.com/problems/pascals-triangle/

Solution

Time Complexity: O((1 + numRows) * numRows / 2) = O(numRows ^ 2)
Space Complexity: O(1)
(The input and output generally do not count towards the space complexity.)

注意：
pascals_triangle[i][j] = pascals_triangle[i - 1][j - 1] + pascals_triangle[i - 1][j]
 pascals_triangle[i][j] = pascals_triangle[i - 1][j - 1] + pascals_triangle[i - 1][j + 1]

class Solution:
  def generate(self, numRows: int) -> List[List[int]]:
    pascals_triangle = [[1] * i for i in range(1, numRows + 1)]
    for i in range(2, numRows):
      for j in range(1, (i + 2) // 2):
        pascals_triangle[i][j] = pascals_triangle[i][-1 - j] \
          = pascals_triangle[i - 1][j - 1] + pascals_triangle[i - 1][j]
    return pascals_triangle

Last Updated on 2023/08/16 by A1go