ゼロから始めるLeetCode Day42「2. Add Two Numbers」

#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day41「394. Decode String」

今はTop 100 Liked QuestionsのMediumを解いています。
Easyは全て解いたので気になる方は目次の方へどうぞ。

Twitterやってます。

問題

2. Add Two Numbers

難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

空ではない連結リストを与えられるので与えられた数字をそれぞれ桁ごとに足していき、反転させて返すようなアルゴリズムを設計してください、というものです。

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解法

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        tempsum = 0
        root = cur = ListNode(0)
        while l1 or l2 or tempsum:
            if l1: tempsum += l1.val; l1 = l1.next
            if l2: tempsum += l2.val; l2 = l2.next
            cur.next = cur = ListNode(tempsum % 10)
            tempsum //= 10
        return root.next
# Runtime: 64 ms, faster than 95.04% of Python3 online submissions for Add Two Numbers.
# Memory Usage: 13.9 MB, less than 5.67% of Python3 online submissions for Add Two Numbers.

シンプルなものにはなりましたが、良さげですね。
問題番号でも最初の方のものは良問揃いな気がしますね。
今回のようにしっかりとした数学的な知識というよりは頭を使ってしっかりとフローチャートを考えれば解けるような問題が多い気がします。

※2021/11/1 追記

Javaで解きました。

このアルゴリズムを考える時には

• 桁上げが起こった時の処理
• 連結リストの走査方法
• 連結リストの長さが異なる時の処理
• 走査が終わった後にcarryがある場合の処理

などなど色んなことを考えなくてはならないので良い問題だなあと思いました。

それこそSolutionの↓はいい回答だと思います。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    // dummyHeadを作っておくことで余分なチェックが必要なくなる
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    // p,qのいずれかが存在する限り続ける
    while (p != null || q != null) {
        // nullでない場合に値を代入する。nullの場合は0を返す。
        int x = (p != null) ? p.val : 0;
        int y = (q != null) ? q.val : 0;
        // carry(前の値の足し算の桁上がり)とそれぞれの値の足し算
        int sum = carry + x + y;
        // sumを10で割った値が桁上がり値となる 
        carry = sum / 10;
        // curr.nextにsumを10で割った時の余りを値を入れる
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        if (p != null) p = p.next;
        if (q != null) q = q.next;
    }
    // ループ終了後に桁上がりがあった場合に引き継ぐことで桁上がりをカバー
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    return dummyHead.next;
}

今回はこの辺で。お疲れ様でした。