2022/04/25

Leetcode Note: Go - Pascals Triangle

Pascal’s Triangle - LeetCode
https://leetcode.com/problems/pascals-triangle/

  • Go 言語で取り組んだメモ

所感

実装準備

func generate(numRows int) [][]int {
    return [][]int{}
}

func main() { 
    numRows := 5
    fmt.Println(generate(numRows)) 
}

回答

0ms, 2MB, Golang Solution Easy to Understand - LeetCode Discuss
https://leetcode.com/problems/pascals-triangle/discuss/1878753/0ms-2MB-Golang-Solution-Easy-to-Understand

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

    // numRows 分のループ
    for i := 0; i < numRows; i++ {

        // ループカウンター +1 分のループ
        for j := 0; j < i+1; j++ {

            // 各行の初回に 1 をセットする
            if j == 0 {
                triangle = append(triangle, []int{1})
            
            // 各行の初回以外
            } else {

                // 各行の終端に 1 をセット
                if j == i {
                    triangle[i] = append(triangle[i], 1)

                // 各行の中心部分
                } else {

                    // triangle[i-1][j] + triangle[i-1][j-1]
                    // triangle[i-1][j] => 前行の j
                    // triangle[i-1][j-1] => 前行の j-1
                    // これで前行の 2要素 を加算した結果を算出して代入する
                    triangle[i] = append(triangle[i], triangle[i-1][j] + triangle[i-1][j-1])
                }
            }
        }
    }
    return triangle
}
  • 実装すべきことの全体像はつかめていたが、実装に落とし込むまでは出来なかった
  • ループ処理の具体的な実装イメージが不足していた感
    • 今回の処理では、各行の初回・終端・中心に分けて考える必要があり、このあたりの意識があれば実装できた気がする

See Also