2022/04/11

Leetcode Note: Go - Plus One

Plus One - LeetCode
https://leetcode.com/problems/plus-one/

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

所感

  • 配列の要素を 1つ の数値に統合して +1 し、その結果を配列としてパースして return すれば良さそう

実装準備

func plusOne(digits []int) []int {
    return digits
}

func main() { 
    digits := []int{1,2,3}
    fmt.Println(plusOne(digits))
}

v1

func plusOne(digits []int) []int {
    for i := 0; i < len(digits); i++ {
        if i == len(digits) -1 {
            digits[i]++
        }
    }
    return digits
}
  • 数値を統合してプラスして return するより、ループで最後の要素に +1 した方が計算量が少ないのでは、と実装中に思いついた
  • しかし、これは桁上りが考慮されていないため、不完全

回答

func carryUp(digits []int) []int {
    for i := len(digits) - 1; i >= 0; i-- {
        if digits[i] > 9 {
            digits[i] = 0
            if i != 0 {
                digits[i-1] += 1
            } else {
                digits = append([]int{1}, digits...)
            }
        }
    }
    return digits
}

func plusOne(digits []int) []int {
    digits[len(digits) - 1]++
    digits = carryUp(digits)
    return digits
}
  • 色々修正していって結果は上記のようになった
  • そもそも plusOne の for loop は不要だったので削除
  • 桁上りを行う carryUp 関数を実装
    • 配列を loop して 10 の値があったら桁数を調整する
    • スライスの先頭に要素を追加したい場合に digits = append([]int{1}, digits...) のように、追加したい要素から append に指定するという書き方があった

  • 反省点としては…

    • for loop で i– をする書き方で時間を使ってしまったので、サッと書けるようになりたい所

    • carryUp 関数内で append で digits を操作するので、わざわざ digits を return する必要ないか？と思ったが、そうすると plusOne で append した digits が return できず、これに詰まった

      • append は新しい配列を生成するので、改めて return する必要があった
      • これは append を使わない場合でも、新しい配列を定義すると同じく return が必要

      • 与えられた配列の既存要素を上書きするなら不要

        package main

import "fmt"

func myAppend(x []int) {
	x = append(x, 2)
}

func myNewArray(x []int) {
	x = []int{1, 2, 3}
}

func myArray(x []int) {
	x[1] = 3
}

func main() {
	x := []int{0}
	fmt.Println(x) // [0]

	x = append([]int{1}, x...) // 普通に Append する分には問題なし
	fmt.Println(x) // [1 0]

	myAppend(x) // 別関数内で Append すると、呼び出し元のスライスには影響がない
	fmt.Println(x) // [1 0]

	myNewArray(x)  // 別関数内で新しく配列を定義しても同様で、呼び出し元に影響は内
	fmt.Println(x) // [1 3]

	myArray(x) // 別関数内で既存要素を変更すると、呼び出し元の要素に影響する
	fmt.Println(x) // [1 3]
}

  • そこそこの可読性を保ちつつ、計算量の少ない実装ができて結構満足度が高かった

See Also