ゼロから始めるLeetCode Day34「118. Pascal's Triangle」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day33「1. Two Sum」
次回
ゼロから始めるLeetCode Day35「160. Intersection of Two Linked Lists」

問題

118. Pascal’s Triangle

偶然YouTubeでこの問題をJavaで解いてるのを見たので私も解いてみようと思いました。

難易度はEasyです！

問題としては、自然数であるnumRowsが与えられるので、例のようなパスカルの三角形を作ってください、という問題です。

Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

解説

最初と最後に1を入れることは確定しているので、予め1を挿入した状態を用意してあげて、処理の最後に再び1をappendしてあげれば良さそうです。
問題はどういう風に上位の数字の和を計算し、挿入するかについてですが、forループを二重に回せば二つ分の要素を取得し、足すことが出来そうですね。
なお、今回はnumRowsが0と1の場合は例外として除外するような書き方をしました。
こうすることで、3段目からの処理のみを書けば良いのでより読みやすいと思います。

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        if numRows == 0:
            return []
        elif numRows == 1:
            return [[1]]
        
        triangle = [[1]]
        
        for i in range(1,numRows):
            row = [1]
              
            for j in range(1,i):
                row.append(triangle[i-1][j-1] + triangle[i-1][j])
            
            row.append(1)
            triangle.append(row)
            
        return triangle
# Runtime: 28 ms, faster than 73.84% of Python3 online submissions for Pascal's Triangle.
# Memory Usage: 13.8 MB, less than 7.14% of Python3 online submissions for Pascal's Triangle.

はい、こんな感じになりました。

こっちの書き方の方が良いよ！とかこの言語で書いてみたよ！とかがあれば是非コメントしてみてください。