LeetCode: Add Two Numbers - ys7i’s diary

https://leetcode.com/problems/add-two-numbers/description

筆算みたいなことをやるだろうなと思いつつ、力技で解いてみようと思った。 ListNodeの表す数を取得、文字列に変換、reverseしてintに戻し、足し合わせてからListNodeにするという案。確か昔Rubyでこの問題をやったことがあって、その時にうまくいったので一度実装してみた。

しかしListNodeの表す数を取得する時点で、goのintの上限を突破してしまい、正しい解が出なかった。ここから学んだこととして、自分の扱う言語のint型の範囲くらい覚える必要があるということ。そして実装に入る前に制約を確認するということ。

ちなみにRubyでは数値型に上限はないので気にする必要はない。

ということで筆算法で解いてみる。

Solution1

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummyHead := &ListNode { 0, nil }
    current := dummyHead
    isCarryOver := false

    for l1 != nil || l2 != nil || isCarryOver {
        value1 := getValueAndMove(l1)
        if l1 != nil {
            value1 = l1.Val
            l1 = l1.Next
        }

        value2 := 0
        if l2 != nil {
            value2 = l2.Val
            l2 = l2.Next
        }

        currentValue := value1 + value2
        if isCarryOver {
            currentValue += 1
            isCarryOver = false
        }

        if currentValue >= 10 {
            currentValue -= 10
            isCarryOver = true
        }

        current.Next = &ListNode { currentValue, nil }
        current = current.Next
    }
    return dummyHead.Next
}

時間計算量O(n), 空間計算量O(n) になると思っていたが、LeetCodeのEditorialを見ると時間計算量O(max(m, n))、空間計算量O(1)とある。(m, nはl1, l2それぞれの長さ) 空間計算量については

The length of the new list is at most max(m,n)+1 However, we don't count the answer as part of the space complexity.

とあるので返り値は空間計算量に含めないらしい。これは人によって考え方が違いそう。

上のコードはまだ改良できそう。

Solution1 改良版

l1 != nilとl2 != nilの条件式を含むif文の部分の重複を消してみる。

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    sentinel := &ListNode { 0, nil }
    currentNode := sentinel
    carryOverValue := 0

    for l1 != nil || l2 != nil || carryOverValue > 0 {
        value1 := 0
        if l1 != nil {
            value1 = l1.Val
            l1 = l1.Next
        }

        value2 := 0
        if l2 != nil {
            value2 = l2.Val
            l2 = l2.Next
        }

        currentValue := value1 + value2
        currentValue += carryOverValue

        carryOverValue = currentValue / 10
        currentValue -= carryOverValue * 10

        currentNode.Next = &ListNode { currentValue, nil }
        currentNode = currentNode.Next
    }
    return sentinel.Next
}

次の桁上げをフラグで管理するのをやめて桁上げする値で管理するようにした。

        value1 := 0
        if l1 != nil {
            value1 = l1.Val
            l1 = l1.Next
        }

        value2 := 0
        if l2 != nil {
            value2 = l2.Val
            l2 = l2.Next
        }

が冗長であると感じるなら

func moveNextDigit(l *ListNode) (int, *ListNode) {
    if l == nil {
        return 0, nil
    }
    return l.Val, l.Next
}

とかを導入して

        var value1, value2 int
        value1, l1 = moveNextDigit(l1)
        value2, l2 = moveNextDigit(l2)

にも出来るが、これは処理内容をうまく切り出しているというよりは冗長なものをただ消しているだけなので、適切なメソッド名が思い浮かばない。これくらいであればメソッド化せずに書き下すのが好み。

他にはdummyHeadをsentinelという変数名に変えた。 sentinelは番兵という意味で、番兵法の2つの意味

実データには出現しない、データの終了を表すための専用の値
入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ

「番兵」の意味や使い方わかりやすく解説 Weblio辞書より

のうち後者に当たるのでこの名前にした。

Solution2

ループで解けるなら再帰で解けるはず

func addTwoNumbersHelper(l1 *ListNode, l2 *ListNode, carryOverValue int) *ListNode {
    if l1 == nil && l2 == nil && carryOverValue == 0 {
        return nil
    }

    value1 := 0
    if l1 != nil {
        value1 = l1.Val
        l1 = l1.Next
    }

    value2 := 0
    if l2 != nil {
        value2 = l2.Val
        l2 = l2.Next
    }

    total := value1 + value2 + carryOverValue
    nextCarryOverValue := total / 10
    value := total % 10
    
    return &ListNode { value, addTwoNumbersHelper(l1, l2, nextCarryOverValue) }
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    return addTwoNumbersHelper(l1, l2, 0)
}

計算量は前と同じ。再帰のパワーをうまく使えている気がする。番兵も消えてシンプルになった。

スタックサイズの見積もりなどが出来るといいと思いLLMに聞いてみると

1. 各再帰呼び出しで使用されるメモリ:
- 関数の引数:
  - l1, l2 のポインタ (8バイト × 2)
  - carryOverValue (8バイト)
- ローカル変数:
  - value1, value2 (8バイト × 2)
  - total (8バイト)
  - nextCarryOverValue (8バイト)
  - value (8バイト)
  - 戻り値のListNode (16バイト)
  - 関数呼び出しのオーバーヘッド (約16バイト)

2. 1回の再帰呼び出しで使用される合計メモリ:
    8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 16 + 16 = 96バイト

と返ってきた。調べてみるとポインタは8バイト、intは4 or 8バイトだが大体8バイトだろう。 ListNodeはintとポインタを含むので8+8=16バイト関数呼び出しのオーバーヘッドについてはソースが見つからなかった。 8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 16 = 8 + 8 + 8 + 8 + 8 + 8 + 8 + 8 + 16 = 80バイトとして良いかなぁ