[Go/LeetCode] 66. Plus One

概要

↓の解法メモです。
https://leetcode.com/problems/plus-one/

問題概要

整数が各桁区切りのスライスで渡されるので、+1 した状態で返します。
たとえば [1, 2, 3, 4] の場合 [1, 2, 3, 5] が返されます。

解法

初見

基本的には一の位に +1 して返せばよいですが、繰り上げの処理を書く必要があります。
これが [1, 9] みたいな場合は十の位に +1 して一の位を -10 すればよいですが、[1, 9, 9] とかの場合は再帰的に繰り上げる必要があります。

ほんとは関数に分離して再帰的に呼ぼうと思ってたんですが、うまい書き方が思いつかなかったのでポインタで書きました。

func carryup(digits []int) []int {
    for p := len(digits)-1; p>0; p-- {
        if digits[p] < 10 {
            break
        }
        digits[p] -= 10
        digits[p-1] += 1
    }
    if digits[0] >= 10 {
        n := append([]int{1}, digits...)
        n[1] -= 10
        return n
    }
    return digits
}

func plusOne(digits []int) []int {
    digits[len(digits)-1] += 1
    r := carryup(digits)
    return r
}

再帰的に処理する

Solution から引用。
https://leetcode.com/problems/plus-one/solutions/6987115/go-recursion-approach-very-easy-and-simple-to-grasp

処理速度は前者と変わりません。

func plusOne(digits []int) []int {
    return plusOneRecursion(digits, len(digits)-1)
}

func plusOneRecursion(digits[]int, index int) []int {
    if digits[index] == 9 {
        digits[index] = 0;
        if index == 0 {
        newDigits := append([]int{1}, digits...);           
        return newDigits;
        }
        return plusOneRecursion(digits, index-1);
    }
    digits[index] = digits[index] + 1;
    return digits;
}