LeetCode #2 Add Two Numbers 兩個數字加總

Klook.com
文章觀看次數: 617

LeetCode題目翻譯

英文原文如下

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

中文翻譯

給予你兩個非空的鏈結串列來代表兩個非負數的整數。

兩個整數會以倒序的方法儲存，然後鏈結串列中的每一個節點包含了一位整數。將兩個數字加總後並回傳一個鏈結串列。

你可以假設兩個數字不會有任何 0 做為開頭，除了 0 本身。 ➡ 數字 123 不會出現 0123 這種類型的表示

範例及題目限制

每一個鏈結串列的節點個數為 1 到 100之間

節點裡面的值為 0 到 9 之間

這裡又強調了一次，保證該串列代表的數字沒有以 0 開始 (前導數)

可以看到鏈結串列 [2,4,3] 代表的就是倒過來的數字 ➡ 342

解題思路

雖然題目叫做兩個數字相加，會讓人直接想到兩個整數直接加起來，但其實是考驗大家的鏈結陣列呢

好啦，但當筆者第一次看到這題，直接就想說這不是看不起我嗎，這樣還中階難度，我呸

腦海中連怎麼寫都想好了

  1. 用迭代將兩個鏈結串列的值分別加到兩個字串 string上
  2. 倒轉兩個字串，並轉換為整數然後加總
  3. 再將加總後的結果倒轉並轉為鏈結串列

聽起來是不是相當合理，just a piece of cake !

C# 解決方案

❌第一次嘗試 ➡ OverflowException

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        string tmp1 = "";
        string tmp2 = "";
        
        
        while(l1!=null)
        {
            tmp1+=l1.val.ToString();
            l1 = l1.next;
        }
        
        while(l2!=null)
        {
            tmp2+=l2.val.ToString();
            l2 = l2.next;
        }
        
        char[] charArray = tmp1.ToCharArray();
        Array.Reverse(charArray);
        tmp1 =  new string(charArray);
        
        charArray = tmp2.ToCharArray();
        Array.Reverse(charArray);
        tmp2 =  new string(charArray);
        
        string res = (Convert.ToInt32(tmp1)+Convert.ToInt32(tmp2)).ToString();
        Console.WriteLine(res);
        
        charArray = res.ToCharArray();
        Array.Reverse(charArray);
        res =  new string(charArray);
        
        ListNode resNode = new ListNode();
        ListNode copyNode = resNode;
        copyNode.val = Convert.ToInt32(res[0].ToString());
        
        for(int i = 1;i<res.Length;i++)
        {
            ListNode newNode = new ListNode(); 
            
            newNode.val = Convert.ToInt32(res[i].ToString());
            copyNode.next = newNode;
            
            copyNode = newNode;
        }
        
        return resNode;
        
    }
}

快速地寫完提交後，卻… 報錯了!!

從紀錄上，我們可以看到因為數字超過了 Int32的限制

也就是題目中的 [1,9,9,9,9,9,9,9,9,9]，到序後的數字為 9999999991，也就是高達 99億

而Int32的最大值也僅為 232-1 ≈ 約為21億多

所以，或許我們得換另一種方式呢

方案1

/**
 * 省略掉...太長了
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        bool next = false;
        int res = 0;
       
        
        //first init
        ListNode resNode = new ListNode();
        ListNode copyNode = new ListNode();
        
        res = l1.val+l2.val;
        if(res>9)
        {
            next = true;
            res -=10;
        }
        resNode.val = res;
        copyNode = resNode;
        
        l1 = l1.next;
        l2 = l2.next;
        
        //開始迭代
        while(l1!=null || l2!=null)
        {
            
            int tmp1 = 0;
            int tmp2 = 0;
            
            if(l1!=null)
            {
                tmp1 = l1.val;
                l1 = l1.next;
            }
            
            if(l2!=null)
            {
                tmp2 = l2.val;
                l2 = l2.next;
            }
            
            res = tmp1+tmp2;
            if(next)
            {
                res+=1;
                next = false;
            }
            
            if(res>9)
            {
                next = true;
                res -=10;
            }

            ListNode newNode = new ListNode();
            newNode.val = res;
            copyNode.next = newNode;
            copyNode = newNode;
            
        }
        
        if(next)
        {
            ListNode newNode = new ListNode();
            newNode.val = 1;
            copyNode.next = newNode; 
        }
        
    return resNode;
    }
}

在這一次的解答中，我們將計算跟建立鏈結串列放在同個迭代中

這邊來講解一下邏輯，首先我們先看向範例1

鏈結串列分別為 [2,4,3] 及 [5,6,4] ➡ 也就是數字 342 及 465

這時候讓我們來重溫一下國小的數學課 – 下面有請直式加法

咦 !!! 是不是兩個鏈結串列一次拿一個節點的值來做計算也可以得到答案

直式加法 ➡ 從位數最小加到最大 ， 而我們的鏈結串列直接給了我們倒序的節點了 !!!

那所以我們需要在意的點只剩下兩個

  • 需進位的狀況 ( 該次計算大於9 )
  • 兩個鏈結串列節點數不同

避免了使用字串轉 integer的計算，只是看起來似乎麻煩了些

我們接下來來進行一些簡單的優化 ➡ 避免使用太多變數

⭐方案2 – 更改了判斷的條件

/**
 * 省略掉...太長了
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        int sum = 0;

        //first init
        ListNode resNode = new ListNode();
        ListNode copyNode = resNode;
        
        //start iteration
        while(l1!=null || l2!=null || sum!= 0)
        {
            if(l1!=null)
            {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if(l2!=null)
            {
                sum += l2.val;
                l2 = l2.next;
            }

            ListNode newNode = new ListNode();
            newNode.val = sum%10;
            copyNode.next = newNode;
            copyNode = newNode;
            
            sum/=10;   //永遠只會為 0 或 1
        }
        
    return resNode.next;
    }
}

*小提示 : sum/=10 意思是 sum = sum/10

至於為什麼只會出現 0 或 1 呢，則是因為節點中的值最大為 9

考慮兩個節點值均為最大的情況 ➡ 9+9 + 進位的1 = 19

而C#中兩個整數互除則會得到無條件捨去小數位的整數結果，故僅會出現 0 或 1

Java解決方案

方案1

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int sum = 0;

        //first init
        ListNode resNode = new ListNode();
        ListNode copyNode = resNode;
        
        //start iteration
        while(l1!=null || l2!=null || sum!= 0)
        {
            if(l1!=null)
            {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if(l2!=null)
            {
                sum += l2.val;
                l2 = l2.next;
            }

            ListNode newNode = new ListNode();
            newNode.val = sum%10;
            copyNode.next = newNode;
            copyNode = newNode;
            
            sum/=10;   //will always be 0 or 1
        }
        
    return resNode.next;
    }
}

運行時間 : 2ms

Python3解決方案

方案1

# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        sum = 0;

        #first init
        resNode = ListNode();
        copyNode = resNode;
        
        #start iteration
        while(l1!=None or l2!=None or sum!= 0):
            if(l1!=None):
                sum += l1.val;
                l1 = l1.next;
            
            if(l2!=None):
                sum += l2.val;
                l2 = l2.next;

            newNode = ListNode();
            newNode.val = sum%10;
            copyNode.next = newNode;
            copyNode = newNode;
            
            sum= int(sum/10);
            
        return resNode.next;

JavaScript解決方案

方案1

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
        var sum = 0;

        //first init
        var resNode = new ListNode();
        var copyNode = resNode;
        
        //start iteration
        while(l1!=undefined || l2!=undefined || sum!= 0)
        {
            if(l1!=undefined)
            {
                sum += l1.val;
                l1 = l1.next;
            }
            
            if(l2!=undefined)
            {
                sum += l2.val;
                l2 = l2.next;
            }
            
            var newNode = new ListNode();
            newNode.val = sum%10;
            copyNode.next = newNode;
            copyNode = newNode;
            
            sum = parseInt(sum/10);
            
        }
        
    return resNode.next;
    
};

結論

這一題其實沒有想像中的那麼簡單呢，筆者第一次寫的時候看到 ERROR 確實嚇了一大跳

但其實轉個彎想想就會突然豁然開朗呢哈哈 !

🧡如果這篇文章有幫上你的一點點忙，那是我的榮幸

🧡幫我分享或是收藏，我都會很感激的

✅如有任何疑問，歡迎透過留言或messenger讓我知道 !

題目連結 : Add Two Numbers – LeetCode

這裡看下一題 : LeetCode #3 最長且沒有重複的子字串 – Zyrastory-當程式碰上美食

隨機文章

相關文章

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *