LeetCode - 2. Add Two Numbersを解く

LeetCode2日目、なんとなく予測できて解けるときは楽しいなと思う。進研ゼミのマンガみたいな感じ。

問題へのリンク

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

問題を解く前に

• 連結リストの復習
  連結リスト - Wikipedia

配列との違いは連結リストではデータの追加がより容易で、データの検索にはコストがかかってしまうこと。
なので毎回数字を探しに行かないように組んでみた。

解答

def add_two_numbers(l1, l2)

    num1 = to_num(l1)
    num2 = to_num(l2)

    sum = num1 + num2
    size = sum.to_s.length - 1
    sumStr = sum.to_s
    ans = ListNode.new
    tmp = ans
    size.step(0, -1) do |i|
        tmp.val = sumStr[i]
        if i == 0
            tmp.next = nil
        else
            tmp.next = ListNode.new
            tmp = tmp.next
        end
    end
    
    return ans
end

def to_num(list_node)
    l = list_node
    index = 0
    num = 0
    while !l.nil? do
        num = num + l.val * (10 ** index)
        l = l.next
        index = index + 1
    end
    return num
end

Runtime	Memory
64 ms	9.8 MB

別解

公式の解答例では1桁ずつ処理する方法を紹介しているのでrubyで書いてみる。

def add_two_numbers(l1, l2)

    p = l1
    q = l2
    ans = ListNode.new
    tmp = ans
    carry = 0
    while !p.nil? || !q.nil? do
        tmp.next = ListNode.new
        tmp = tmp.next

        num1 = p.nil? ? 0 : p.val
        num2 = q.nil? ? 0 : q.val
        sum = num1 + num2 + carry
        
        carry = sum / 10
        tmp.val = sum % 10
        
        p = p.nil? ? nil : p.next
        q = q.nil? ? nil : q.next
    end
    if carry == 1
        tmp.next = ListNode.new(1, nil)
    end
    return ans.next
end

Runtime	Memory
44 ms	9.8 MB