LeetCode / Pascal's Triangle

（ブログ記事からの転載）

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

Given a non-negative integer numRows, generate the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it.

Example:

パスカルの三角形と言われるものを、数列を重ねていくことで作ります。
各々の数列は、上段の数列の2つの値の和になっているのが特徴です。

解答・解説

解法1

私のsubmitした手法です。
愚直にnumRows段目までの数列を1つ1つ作り、積み上げていきます。

上の段の数列の2つの値を足して新たな数列を計算するとき、
l_pre = [0]+ans[-1]+[0]
のように数列の両端に[0]を追加して、
l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)]
のようにすっきりしたループ処理となるようにしていします。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        if numRows > 0:
            ans.append([1])
            for _ in range(numRows-1):
                l_pre = [0]+ans[-1]+[0]
                l_nxt = [l_pre[i]+l_pre[i+1] for i in range(len(l_pre)-1)]
                ans.append(l_nxt)
        return ans

解法2

Discussionの中で、これは良いなと思った解法を紹介します。

pascal = [[1]*(i+1) for i in range(numRows)]
として、はじめに全ての値を1にしてnumRows段目までの三角形を作ってしまってから、正しい値を代入します。

解法1と比べて時間・空間計算量は変わりませんが、公式よりもさらにすっきりした美しい解法だと思います。

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