golangで60 questions to solveを説いてみるシリーズ。
今回の問題はAdd Two Numbers。

Add Two Numbers

まずは自分の限界。

package AddTwoNumbers

import (  
    "strconv"
)

type ListNode struct {  
    Val  int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {  
    connectedL1 := nodeConnect(l1)
    connectedL2 := nodeConnect(l2)

    ansval := connectedL1 + connectedL2
    ansstr := strconv.Itoa(ansval)

    ans := toList(Reverse(ansstr))

    return ans

}

func Reverse(s string) string {  
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

func toList(s string) *ListNode {  
    l := &ListNode{}
    for i, sRune := range s {
        val, err := strconv.Atoi(string(sRune))
        if err != nil {
            panic(err)
        }
        if i == 0 {
            l.Val = val
        } else {
            tmpl := l
            for {
                if tmpl.Next != nil {
                    tmpl = tmpl.Next
                    continue
                }
                tmpl.Next = &ListNode{
                    Val: val,
                }
                break
            }
        }
    }
    return l
}

func nodeConnect(l *ListNode) int {  
    conStr := ""
    for {
        conStr += strconv.Itoa(l.Val)
        l = l.Next
        if l == nil {
            val, err := strconv.Atoi(Reverse(conStr))
            if err != nil {
                panic(err)
            }
            return val
        }
    }
}

大体正解するけど、[1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1]でパニックが出る。31桁なんてどうやればいいんだ？ 考え方を変えないとだめだな。

linked list

このようなデータ構造をlinked listと呼ぶ。スタックやキューの実装に便利だが、n番目の要素にすぐにたどり着いつくのが難しい。

上のlistNodeから順番に足していって、繰り上げていく。 下記の図のように。

このあとも、golangのpointerの仕組みを使ってなんとかしようとしたりしたけど、難しかった。 そして試行錯誤してなんとか正解にたどり着いたのがこちら

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {  
    ans := &ListNode{}
    result := ans
    carry := 0
    for {
        if carry == 1 && l1 == nil && l2 == nil {
            ans.Val = 1
            break
        } else if l1 != nil && l2 != nil {
            sum := l1.Val + l2.Val + carry
            ans.Val = sum % 10
            carry = sum / 10
            l1 = l1.Next
            l2 = l2.Next
            if l1 != nil || l2 != nil || carry == 1 {
                ans.Next = &ListNode{}
                ans = ans.Next
            }
        } else if l1 == nil && l2 != nil {
            sum := l2.Val + carry
            carry = sum / 10
            ans.Val = sum % 10
            l2 = l2.Next
            if l2 != nil || carry == 1 {
                ans.Next = &ListNode{}
                ans = ans.Next
            }
        } else if l1 != nil && l2 == nil {
            sum := l1.Val + carry
            carry = sum / 10
            ans.Val = sum % 10
            l1 = l1.Next
            if l1 != nil || carry == 1 {
                ans.Next = &ListNode{}
                ans = ans.Next
            }
        } else {
            break
        }
    }
    return result
}

if条件がむちゃくちゃだし、ポインタをトリッキーに使っているしなんとも不安になるコードだ。
ということで、むちゃくちゃシンプルな解法がこれ

func addTwoNumbersRecursive(l1 *ListNode, l2 *ListNode) *ListNode {  
    if l1 == nil && l2 == nil {
        return nil
    } else if l1 == nil && l2 != nil {
        return l2
    } else if l1 != nil && l2 == nil {
        return l1
    }

    sum := l1.Val + l2.Val
    next := addTwoNumbersRecursive(l1.Next, l2.Next)

    if sum >= 10 {
        carry := sum / 10
        sum %= 10
        next = addTwoNumbersRecursive(next, &ListNode{Val: carry})
    }
    return &ListNode{Val: sum, Next: next}
}

再帰を全然書いていないからこのコードを見せられてもサクッと読めない・・・

時間計算量

O(max(m,n))となる。maxってなんだ。ちょっとググったところ、このmaxはexcelとかのそれと変わらない。
m, nのうち最大の最大の数ということになる。

O(n) + O(m) = O(n + m) = O(max(n,m))となる。

空間計算量

O(1)かな。ちがうか。計算結果を格納するのに最大必要になる要素数はO(n) + O(m) + 1か。