# LeetCode Easy 119. Pascal's Triangle II

tags: leetcode

問題

• Explore
• 普通

非負整数のindex, $k \leq 3$を与えられた時, パスカルの三角形の$k$番目の段を返せ

0段目から始まることに注意せよ

追加:

余分に$O(k)$メモリだけを使うようにアルゴリズムを最適化できるか?

解法1

最適化を気を付けなければ前回の解答を使って問題を解くことが可能です

propyon.hateblo.jp

• 空間計算量は$O(k^{2})$
• 時間計算量は$O(k^{2})$

Python

class Solution:
    def getRow(self, numRows: int) -> List[List[int]]:
      pascal = [[1]]
      for row in range(1, numRows+1):
        p_row = [1]
        for col in range(1, row):
          p_row.append(pascal[row-1][col] + pascal[row-1][col-1])
        p_row.append(1)
        pascal.append(p_row)
      return pascal[numRows]

C++

class Solution {
public:
    vector<int> getRow(int rowIndex) {
      if (rowIndex == 0) {
        return vector<int> {1};
      } else {
        vector<vector<int>> pascal{{1}};
        for (int i = 1; i <= rowIndex; ++i) {
          vector<int> row{{1}};
        for (int j = 1; j < i; ++j) {
         row.push_back(pas[i-1][j-1] + pascal[i-1][j]);
        }
        row.push_back(1);
        pascal.push_back(row);
        }
        return pascal[rowIndex];
      }
    };
};

解法2(recursive)

返す配列の間の要素は前回までに得られた配列の要素から得られることを利用します

• 基底としてrowIndex==0のときは[1]を出力します
• rowIndex==1の時
  • 返す数列の最初と最後の数は$1$
  • rowIndex-1で得られる配列の用いてその間の数は作れます
• 空間計算量は$O(k)$回再帰関数を呼び出し, それぞれに長さ$O(k)$の配列が必要に成るので必要があるので$O(k^{2})$
• 時間計算量は$O(k)$回再帰関数を呼び出し, それぞれに$O(k)$の処理を必要とするので$O(k^{2})$

Python

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
      if rowIndex == 0:
        return [1]
      else:
        prev = self.getRow(rowIndex-1)
        return [1] + [prev[i-1] + prev[i] for i in range(1, rowIndex)] + [1]

C++

class Solution {
public:
    vector<int> getRow(int rowIndex) {
      if (rowIndex == 0) {
        return {1};
      } else {
        vector<int> prev = getRow(rowIndex-1);
        vector<int> ret{1};
        for (int i = 1; i < rowIndex; i++) {
          ret.emplace_back(prev[i-1] + prev[i]);
        }
        ret.emplace_back(1);
        return  ret;
      }
    }
};

解法3(iterative)

• 最初に長さがrowIndex+1の配列を用意します
  • $n \in \mathbb{N}$段目の配列は長さが$n+1$だからです
• 以下の処理を行うことでこの配列のみで処理を行うことが可能です
  • $row = [1, \text{rowIndex}]$ごとに
  • $col = [row, 1]$番目の要素で前の要素を加える
    • arr[j] += a[j-1]とコードだと表せます
  • $rowIndex = 0$のとき
    • {1}と成ります
  • $rowIndex = 1$のとき
    • {1, 1}と成ります
  • $rowIndex = 2$のとき
    • {1, 2, 1}と成ります
  • $rowIndex = 3$のとき
    • {1, 3, 3, 1}と成ります
• この処理は本質的には再帰と同じことをやっています
  • rowは今処理をしている配列が何番目かということを示しています
  • colは返す配列の更新する要素です
  • row番目の処理でcol-1番目の要素にcol番目の要素を足すのを数式で表すと$\pmatrix{row \ col} = \pmatrix{row - 1 \ col} + \pmatrix{row - 1 \ col - 1}$となります
  • row番目の処理が始まるまではrow-1番目の処理がされた配列, つまりrow-1番目の配列だからです
  • この処理を後ろの配列からするのは前から(左から?)足すと後ろの要素は上の数式のようにならずに別の要素まで足されてしまうからです
• 空間計算量は$O(k)$の配列が必要なだけなので$O(k)$
• 時間計算量は$O(k)$の繰り返し処理が2重で必要なので$O(k^{2})$

Python

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
      pascal = [0] * (rowIndex+1)
      pascal[0] = 1
      for row in range(1, rowIndex+1):
        for col in reversed(range(1, row+1)):
          pascal[col] += pascal[col-1]
      return pascal

C++

class Solution {
public:
    vector<int> getRow(int rowIndex) {
      vector<int> pascal(rowIndex+1);
      pascal[0] = 1;
      for (int row = 1; row <= rowIndex; row++) {
        for (int col = row; col >= 1; col--) {
          pascal[col] += pascal[col-1];
        }
      }
      return pascal;
    }
};