【LeetCode】119. Pascal’s Triangle II 解答・解説【Python】

問題
1. 原文
2. 内容
方針
解答
1. 解答1：
補足・参考・感想

問題

原文

Given an integer rowIndex, return the rowIndex^th (0-indexed) row of the Pascal’s triangle.

In Pascal’s triangle, each number is the sum of the two numbers directly above it as shown:

Example 1:

Input: rowIndex = 3

Output: [1,3,3,1]

Example 2:

Input: rowIndex = 0

Output: [1]

Example 3:

Input: rowIndex = 1

Output: [1,1]

Constraints:

0 <= rowIndex <= 33

Follow up: Could you optimize your algorithm to use only O(rowIndex) extra space?

内容

整数の変数rowIndexが与えられます。パスカルの三角形からrowIndexで指定された行(0から数える)を返してください。パスカルの三角形では、各値は直上の2要素の合計値になります。

※正しくない可能性があります。

方針

・1行目から順に要素を埋めていく

・各行では端の要素であるかによって処理を変える

解答

解答1：

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = []
        for i in range(rowIndex+1):
            #今回の行のリストを作成
            res.append([])
            for j in range(i+1):
                #各行の最初から最後の列の場合
                if j==0 or j==i:
                    #1を要素として加える
                    res[i].append(1)
                #各行の端ではない場所(更新が必要な箇所)の場合
                else:
                    #1つ前の行の2つの要素の合計値を加える
                    res[i].append(res[i-1][j-1] + res[i-1][j])
        #指定された行のリストを返す
        return res[rowIndex]

class Solution:

def getRow(self, rowIndex: int) -> List[int]:

res = []

for i in range(rowIndex+1):

#今回の行のリストを作成

res.append([])

for j in range(i+1):

#各行の最初から最後の列の場合

if j==0 or j==i:

#1を要素として加える

res[i].append(1)

#各行の端ではない場所(更新が必要な箇所)の場合

else:

#1つ前の行の2つの要素の合計値を加える

res[i].append(res[i-1][j-1] + res[i-1][j])

#指定された行のリストを返す

return res[rowIndex]

補足・参考・感想

参考

前：118. Pascal’s Triangle

次：136. Single Number

LeetCode 解答・解説記事一覧