はじめに
LeetCodeの問題を解答します。
なるべく、問題の和訳と詳細なコメントを書いています。
余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。
様々なカテゴリの問題をランダムにあたる方法も良いですが、
二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。
テーマごとに問題を分類しました。
LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。
また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。
LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。
はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。
問題
原文
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
内容
整数の変数numRowsが与えられます。パスカルの三角形を返してください。パスカルの三角形では各数字は直上の2つの要素の合計値になります。
※正しくない可能性があります。
方針
・動的計画法(DP)では、最終的な返り値(多次元リスト)を全て1で初期化した状態で作成し、
計算が必要な個所に対して計算を行っていく
・再帰的な処理では、numRowsの1つ小さい数字で関数を再度呼び出し、計算が必要な個所を更新する。
解答
解答1：
|
1 2 3 4 5 6 7 8 9 10 11 |
#DP class Solution: def generate(self, numRows: int) -> List[List[int]]: #全て1で初期化した配列を最初に作成する[1] ans = [[1] * i for i in range(1, numRows+1)] #[2] for i in range(1, numRows): for j in range(1, i): #[3]値を更新 ans[i][j] = ans[i-1][j] + ans[i-1][j-1] return ans |
[1]rangeの終端をnumRows + 1としているのは番兵？(配列外参照を防ぐため？)
[2]二重ループは、1つ目のループが行、2つ目のループが各列の値を処理
→各行の更新箇所は1,2行目は0、3行目は1、4行目は2という具合で(行数-2)個となる。
for文のrangeで終端を示すときは(行数-1)個となる→for文のrangeの終端はループ実行回数に含まれないため。4行目の場合、for i in range(1,3):となり、4行目の(0から数えて)1,2番目の要素を処理する。
[3]ans[i][j]は更新箇所、ans[i-1][j]は更新箇所の右上、 ans[i-1][j-1]は更新箇所の左上の要素
解答2：動的計画法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#再帰 class Solution: def generate(self, numRows: int) -> List[List[int]]: def helper(numRows): if numRows: #最後の行から開始して1つ手前の行の処理を再帰的な関数呼出しによって行う helper(numRows-1) #行全体を1で初期化 ans.append([1]*numRows) #更新箇所の分だけ繰り返し処理を行う for i in range(1, numRows-1): #例：numRowsが5の時は4行目の1~3の要素に、3行目の2つの要素の合計を入れる ans[numRows-1][i] = ans[numRows-2][i] + ans[numRows-2][i-1] ans = [] helper(numRows) return ans |
numRowsの値が5なら、4→3→2→1という順で呼び出す。 ”if numRows”では、numRowsが0の時には実行されないので最初にnumRowsが1の時に
補足・参考・感想
参考
コメント