LeetCode 118. Pascal's Triangle

はじめに

LeetCode 「118. Pascal's Triangle」の問題をGoで解きました。

問題

https://leetcode.com/problems/pascals-triangle/description/

問題文

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:

和訳
整数 numRows が与えられたとき、パスカルの三角形の最初の numRows を返す。

パスカルの三角形では、各数値はその真上にある2つの数値の和となる：

例

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

Input: numRows = 1
Output: [[1]]

制約

• 1 <= numRows <= 30

解答

パスカルの三角形 を構築する問題です。

以下の手順で実装します。

1. numRows 行分の2次元スライスを用意
2. 各行に i+1 個のようを持つスライスを作成
3. 各要素jに対して
   • 先頭・末尾は1
   • それ以外は前の行の j-1番目 + j番目 の値

コード

func generate(numRows int) [][]int {
  triangle := make([][]int, numRows)

  for i := 0; i < numRows; i++ {
    row := make([]int, i+1)
    for j := 0; j <= i; j++ {
      if j == 0 || j == i {
        row[j] = 1
      } else {
        row[j] = triangle[i-1][j-1] + triangle[i-1][j]
      }
    }
    triangle[i] = row
  }

  return triangle
}

また、各要素を作成する際に、あらかじめ先頭と末尾に1を代入することにより、
if文を減らし簡潔に実装することも可能です。

func generate(numRows int) [][]int {
  triangle := make([][]int, numRows)

  for i := 0; i < numRows; i++ {
    row := make([]int, i+1)
    row[0], row[i] = 1, 1

    for j := 1; j < i; j++ {
      row[j] = triangle[i-1][j-1] + triangle[i-1][j]
    }
    triangle[i] = row
  }

  return triangle
}

計算量

• 時間的計算量：O(n²)
• 空間的計算量：O(n²)