【小Y學演算法】??每日LeetCode打卡??——2.兩數相加

📢前言

• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻
• 🌲 每天打卡一道演算法題，既是一個學習程序，又是一個分享的程序😜
• 🌲 提示：本專欄解題 編程語言一律使用 C# 和 Java 兩種進行解題
• 🌲 要保持一個每天都在學習的狀態，讓我們一起努力成為演算法大神吧🧐！
• 🌲 今天是力扣演算法題持續打卡第2天🎈！
• 🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻🌻

🌲原題樣例

• 給你兩個 非空 的鏈表，表示兩個非負的整數，它們每位數字都是按照 逆序 的方式存盤的，并且每個節點只能存盤 一位 數字，

• 請你將兩個數相加，并以相同形式回傳一個表示和的鏈表，

• 你可以假設除了數字 0 之外，這兩個數都不會以 0 開頭，

示例 1：

輸入：l1 = [2,4,3], l2 = [5,6,4]
輸出：[7,0,8]
解釋：342 + 465 = 807.

示例 2：

輸入：l1 = [0], l2 = [0]
輸出：[0]

示例 3：

輸入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
輸出：[8,9,9,9,0,0,0,1]

提示：

• 每個鏈表中的節點數在范圍 [1, 100] 內
• 0 <= Node.val <= 9
• 題目資料保證串列表示的數字不含前導零

🌞解題思路

🌻 C#方法

核心思路就是do while回圈兩張鏈表，將他們每一位的值加起來，如果存在進位的話就將進位存在Other變數中下一次回圈使用，在下一次回圈時Ohter又會被重置，

代碼

    public static ListNode AddTwoNumbers(ListNode l1, ListNode l2)
            //定義回傳值
            var result = new ListNode(-1);
            //定義回圈用的物件，將形參制定到temp
            var temp = result;
            //前一輪數字和的十位數
            int Other = 0;
            do
            {
                //取出numbe1和number2的值
                var number1 = l1 == null ? 0 : l1.val;
                var number2 = l2 == null ? 0 : l2.val;
                //計算兩數之和 并加上前一輪需要進位的值
                var sum = number1 + number2 + Other;
                //計算個位
                var value = sum % 10 ;
                //計算十位并賦值
                Other = sum / 10;
                //將資料添加到回圈鏈表中
                temp.next = new ListNode(value);
                //回圈用的temp物件賦值為回圈鏈表中的下一個物件
                temp = temp.next;
                //l1 l2 指向自己在鏈表中對應的下一個值
                l1 = l1?.next;
                l2 = l2?.next;
            } while (l1 != null || l2 != null|| Other!=0);
            return result.next;
        }

執行結果

執行結果 通過，執行用時116ms，記憶體消耗 27.7 MB.

🎋Java方法：模擬

思路與演算法

由于輸入的兩個鏈表都是逆序存盤數字的位數的，因此兩個鏈表中同一位置的數字可以直接相加，

我們同時遍歷兩個鏈表，逐位計算它們的和，并與當前位置的進位值相加，具體而言，如果當前兩個鏈表處相應位置的數字為 n1,n2n1,n2，進位值為 \textit{carry}carry，則它們的和為 n1+n2+\textit{carry}n1+n2+carry；

其中，答案鏈表處相應位置的數字為 (n1+n2+\textit{carry}) \bmod 10(n1+n2+carry)mod10，而新的進位值為 \lfloor\frac{n1+n2+\textit{carry}}{10}\rfloor? 10n1+n2+carry? ?，

如果兩個鏈表的長度不同，則可以認為長度短的鏈表的后面有若干個 00 ，

此外，如果鏈表遍歷結束后，有 \textit{carry} > 0carry>0，還需要在答案鏈表的后面附加一個節點，節點的值為 \textit{carry}carry，

代碼

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

執行結果

執行結果 通過，執行用時2ms，記憶體消耗 38.8 MB.

復雜度分析

時間復雜度：O(\max(m,n))O(max(m,n))，其中 mm 和 nn 分別為兩個鏈表的長度，
我們要遍歷兩個鏈表的全部位置，而處理每個位置只需要 O(1)O(1) 的時間，
空間復雜度：O(1)O(1)，注意回傳值不計入空間復雜度，

💬總結

• 今天是力扣演算法題打卡的第二天，剛開始還有些生疏，后邊會越來越熟練的！
• 文章采用 C# 和 Java 兩種編程語言進行解題
• 一些方法也是參考力扣大神寫的，也是邊學習邊分享，再次感謝演算法大佬們
• 那今天的演算法題分享到此結束啦，明天再見！