解いた問題
leetcode 118. Pascal's Triangle
パスカルの三角形をプログラミングで書こうねってやつ（雑
学び
- 最適解も2乗オーダーになることもある
- 動的計画法が何かを知れた
- 固定値があるならそれでいったん初期化して、変更が必要な部分だけ計算しなおせばいい
-
[1] * (i+1)で指定要素数をもつリストの初期化ができ、out of range対策しながら簡素にリストを書ける
最初に考えた解法
first.py
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if not numRows:
return None
list = []
lists = {}
for i in range(numRows):
lists[f"list_{i}"] = []
if i >= 3:
for j in range(1, i-1):
lists[f"list_{i}"][j] = lists[f"list_{i-1}"][j-1] + lists[f"list_{i-1}"][j]
else:
lists[f"list_{i}"][0] = 1
lists[f"list_{i}"][-1] = 1
list.append(lists[f"list_{i}"])
return list
上から二つ目の段までは何も考えず1入れればいいし、それ以降も端は1を入れればいい。
3段目からは一つ上の段の同じインデックス+1つ前のインデックスの値が入るからそれらを愚直に実装してみた。
index out of rangeでエラー。lists[f"list_{i}"][0] で空のリストの0番目を指定しているのがいけないっぽい。修正
second.py
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if not numRows:
return None
list = []
lists = {}
for i in range(numRows):
lists[f"list_{i}"] = [1] * (i + 1)
if i >= 3:
for j in range(1, i-1):
lists[f"list_{i}"][j] = lists[f"list_{i-1}"][j-1] + lists[f"list_{i-1}"][j]
else:
lists[f"list_{i}"][0] = 1
lists[f"list_{i}"][-1] = 1
list.append(lists[f"list_{i}"])
return list
動いたが結果がおかしいのでNG
i-1やらif i >= 3やらの境界条件がおかしそうなので修正。
third.py
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
if not numRows:
return None
list = []
lists = {}
for i in range(numRows):
lists[f"list_{i}"] = [1] * (i + 1)
if i >= 2:
for j in range(1, i):
lists[f"list_{i}"][j] = lists[f"list_{i-1}"][j-1] + lists[f"list_{i-1}"][j]
else:
lists[f"list_{i}"][0] = 1
lists[f"list_{i}"][-1] = 1
list.append(lists[f"list_{i}"])
return list
うまくいった～～！
嬉しい。
でもこれO(N^2)くさいよなと思い答えを見てみた。
答え
answer.py
def generate(numRows: int) -> List[List[int]]:
triangle = []
for i in range(numRows):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = triangle[i-1][j-1] + triangle[i-1][j]
triangle.append(row)
return triangle
i=2のところも変に考えず前段の足し算で考えればよかったのか。
もともとi=3からjを回さないとと考えていたからおかしくなったけど、i=2から、と考えていたら最適解を最初に出せていたのかも、、、
これは動的計画法といって、各値を前の行の結果を使って再帰的に計算するアルゴリズムに分類されている。
再利用して効率的に構築し、冗長な計算を避けることができるそう。
感想
最適解もO(n^2)なんかーーーい
コードが冗長だったとはいえある程度アルゴリズムが想像できるようになってうれしい。
これからもちょくちょく進めます。