【Swift】LeetCode：#2「Add Two Numbers」

概要

• LeetCode#2「Add Two Numbers」に対する私見
• 連結リストを使った問題

実装方針

まずは構造体を確認

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     
 *     public init() { 
     *     self.val = 0; 
     *     self.next = nil; 
     * }
 *     public init(_ val: Int) {
     *      self.val = val; 
     *      self.next = nil; 
 *      }
 *     public init(_ val: Int, _ next: ListNode?) {
     *      self.val = val; 
     *      self.next = next; 
 *     }
 * }
 */

• requiredのvalとoptionalのnextの二種類があることを確認できる。
• 構造体の利用方法としてはListNode(N)かListNode(N, ListNode(N1)の2種類がありそう。
• forでListNodeを回して取得した数字をreverseして足したものをListNodeに再変換するという流れで実装すればACになるはず。

ハマった点

• 99%以上のテストケースではPassが通ったものの、Int型の数字を得るカスタムメソッドでハマってしまった。

    func scanL1(_ l1: ListNode?) -> Int {
        var array: [Int] = []
        var l = l1
        while l != nil {
            array.append(l!.val)
            l = l!.next
        }
        array = array.reversed()
        let number = Int(array.map(String.init).joined())!
        return number
    }

ハマってしまったのがこのケース。

[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] [4,6,7]

Int.maxの桁数を超えているから

• 上限値の制約は問題に書かれていないようだが、Int.maxを超えるテストケースを準備しているのはどうなのか？という疑問はさておき、自分はこの問題を解消しようとしたが、Swiftでの実装はあきらめた。

ChatGPT先生の解答

・Int に無理に変換しない
・大きな数は文字列や配列で扱う
・scanL1 なども Int を経由せず 桁ごとの ListNode を足す方法 に変更するのが安全です

とのこと。

大きすぎる値がある場合に備えてString配列で型を保持しておき、

while i >= 0 || j >= 0 || carry > 0 { 
    let x = i >= 0 ? a1[i] : 0 
    let y = j >= 0 ? a2[j] : 0 
    
    let sum = x + y + carry 
    result.append(sum % 10) 
    carry = sum / 10 
    
    i -= 1 
    j -= 1 
}

配列の桁ごとに四則演算を行い、繰り上がりを計算するプログラムを書くことでACにすることが出来るとのことであった。電卓の基本プログラムっぽいので、少し勉強が必要かもしれないと思った。