LeetCode.2 兩數相加(Add Two Numbers)(JS)

Binguner 發布于2019-08-23 16:26 / 1814人閱讀

摘要：更新之前說感覺優秀答案的最后三行可以用尾遞歸優化不知道尾遞歸的小伙伴可以點這里，仔細想了一下，并不能。尾遞歸的實現，往往需要改寫遞歸函數，確保最后一步只調用自身。

上周日就想寫vue.nextTick的源碼分析，可是總是不知道從哪兒下手，今天有時間，先把leetcode第二題補了，感覺這道題還挺簡單的

一、題目

兩數相加：

給出兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點只能存儲一位數字。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。您可以假設除了數字 0 之外，這兩個數都不會以 0 開頭。
示例：

示例

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

二、我的答案

/**
 *. Definition for singly-linked list.
 *. function ListNode(val) {
 *.     this.val = val;
 *.     this.next = null;
 *. }
 */
/**
 *. @param {ListNode} l1
 *. @param {ListNode} l2
 *. @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) { 
      function ListToArray(list) {
        if(list.next) {
          return [list.val, ...ListToArray(list.next)]
        } else {
          return [list.val]
        }
      }
      function sumArray(arr1, arr2) {
        if(arr1.length < arr2.length) {
          let arr = []
          arr = arr1
          arr1 = arr2
          arr2 = arr
        }
        let littleLen = arr2.length
        let i =0
        for(; i < littleLen; i++) {
          arr1[i] += arr2[i]
          if(arr1[i] >= 10) {
            arr1[i] -= 10
            arr1[i + 1] ? arr1[i + 1]++ : arr1[i+1] =1
          }
        }
        for(; i < arr1.length; i++ ) {
          if(arr1[i] >= 10) {
            arr1[i] -= 10
            arr1[i + 1] ? arr1[i + 1]++ : arr1[i+1] =1
          }
        }
        return arr1.reverse()
      }

      function ArrayToList(arr) {
        if(arr.length > 0) {
          let node = new ListNode(arr.pop())
          node.next = ArrayToList(arr)
          return node
        } else {
          return null
        }
      }
      return ArrayToList(sumArray(ListToArray(l1),ListToArray(l2)))
    };

計算兩個鏈表表示的數的和，統共分三步：

~~把冰箱門打開~~ 鏈表轉數組；

兩個數組相加得到和數組；

和數組轉鏈表

我的寫法答案簡單易懂，就不做解釋，這里說一下寫的時候碰到一個坑
關于第二步兩個數組相加，一開始的思路并不是這樣的，而是轉成String再轉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]和[5,6,4]，轉成Number相加得1e+30，沒錯，萬惡的弱類型，查詢能不能不轉換，未果，就只能遍歷各數位相加了

這題一開始沒懂啥意思，懂了之后思路還挺清晰的，擊敗33.45%，嘛，喜聞樂見，看看大手子們是咋寫的吧

三、優秀答案

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2, curr = 0) {
    if(l1 === null && l2 === null) {
        if(curr) return new ListNode(curr)
        else return null;
    } else {
        if(l1 == null) l1 = new ListNode(0)
        if(l2 == null) l2 = new ListNode(0)
        let nextVal = (l2.val || 0) + (l1.val || 0) + curr
        curr = 0
        if(nextVal > 9) {
            curr = 1
            nextVal -= 10
        }
        l1.val = nextVal
        l1.next = addTwoNumbers(l1.next, l2.next, curr)
        return l1
    }
};

這個是我看到的最優秀的答案，本地跑擊敗91%，甩我不知道幾條街，看各種優秀答案總是能刷新認知，來看他的思路
首先他把函數改了，函數的本意是相加兩個鏈表，他改成了相加兩個節點，參數中curr的意思是上一組節點相加是否進位~~這什么命名~~
再來看函數內，if部分的代碼意為處理最后的邊界情況，例[1],[9,9,9,9],即遍歷完兩個鏈表之后，如果上一次遍歷有進位，則new一個節點
else內則是主要的節點相加部分，其中

    if(l1 == null) l1 = new ListNode(0)
    if(l2 == null) l2 = new ListNode(0)
    let nextVal = (l2.val || 0) + (l1.val || 0) + curr

(l2.val || 0)明顯是多余的，我猜他本來寫的是let nextVal = (l2.val || 0) + (l1.val || 0) + curr但是執行發現null點不出val，就加了上面的判斷不過下面的沒刪，不精簡代碼差評。
剩下的邏輯就顯而易見了，進位什么的，不過這種同步遍歷真的很巧妙，我怎么就是學不會/捂臉

四、路漫漫其修遠兮

???????這幾道題提交都是在力扣上的，但是做完這道題去看優秀答案，發現有一個排名較前的答案返回值是Array，我自己復制過來甚至根本過不了測試用例，應該是力扣沒有像leetcode更新全面吧，題改了但是答案卻沒有改，決定以后還是提交到leetCode吧，
???????再細看優秀答案的最后三行，怎么總感覺好像可以用尾調用優化一下，有空看一下，今天這篇博客到此為止，下面該做的第四題難度為hard，害怕之余突然有點期待看到各種神仙解法/捂臉。

THE END

2019.3.27更新
之前說感覺優秀答案的最后三行可以用尾遞歸優化（不知道尾遞歸的小伙伴可以點這里），仔細想了一下，并不能。

尾遞歸的實現，往往需要改寫遞歸函數，確保最后一步只調用自身。做到這一點的方法，就是把所有用到的內部變量改寫成函數的參數。

原因如下：
????????假設我們按照上面描述實現尾遞歸，那么函數需要三個參數，分別是l1, l2，還有當前組裝的listNode對象，那么我們每次調用的時候，都需要l1.val + l2.val賦值給當前組裝的對象的最深層，要想獲得對象的最深層，就得遍歷，那我們還優化個錘子。
????????不過這么分析下來，優秀答案作者可能本來的意圖就是用尾遞歸優化，所以給第三個參數命名為curr，發現得不償失后放棄這種做法，把第三個參數的作用改為進位，但是并沒有再修改變量名，不過這個編碼習慣倒是很符合上文我猜測的let nextVal = (l2.val || 0) + (l1.val || 0) + curr這行代碼沒有精簡的理由。
????????~~分析個優秀答案能分析出破案的感覺我也是服我自己~~

云服務器 GPU云服務器兩數相加 two.js cdn js相加數據 js 時間的相加

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/103021.html

Leetcode 2 Add Two Numbers 兩數相加

摘要：這題是說給出兩個鏈表每個鏈表代表一個多位整數個位在前比如代表著求這兩個鏈表代表的整數之和同樣以倒序的鏈表表示難度這個題目就是模擬人手算加法的過程需要記錄進位每次把對應位置兩個節點如果一個走到頭了就只算其中一個的值加上進位值 Add Two Numbers You are given two linked lists representing two non-negative num...

Charlie_Jade 2019-08-14 17:01 評論0 收藏0
LeetCode 2：兩數相加 Add Two Numbers

摘要：給出兩個非空的鏈表用來表示兩個非負的整數。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。需要考慮到兩個鏈表長度不同時遍歷方式鏈表遍歷完成時最后一位是否需要進一位。 ?給出兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點只能存儲一位數字。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。 ...

diabloneo 2019-08-16 18:39 評論0 收藏0
LeetCode 2：兩數相加 Add Two Numbers

摘要：給出兩個非空的鏈表用來表示兩個非負的整數。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。需要考慮到兩個鏈表長度不同時遍歷方式鏈表遍歷完成時最后一位是否需要進一位。 ?給出兩個非空的鏈表用來表示兩個非負的整數。其中，它們各自的位數是按照逆序的方式存儲的，并且它們的每個節點只能存儲一位數字。如果，我們將這兩個數相加起來，則會返回一個新的鏈表來表示它們的和。 ...

Towers 2019-07-31 11:30 評論0 收藏0
LeetCode 之 JavaScript 解答第二題 —— 兩數相加（Add Two Number

摘要：多位數加多位數，反轉鏈表轉化整數，如果整數相加，可能會溢出，此方法行不通。直接進行位數運算，兩鏈表每取出一個就做運算，將結果放入到新鏈表中。求和運算會出現額外的進位一般進位與最高位進位兩種情況。兩位數取模運算。 Time：2019/4/2Title: ADD Two NumbersDifficulty: mediumAuthor:小鹿公眾號：一個不甘平凡的碼農。題目二：ADD Two...

Sunxb 2019-08-23 16:43 評論0 收藏0
LeetCode 167：兩數之和 II - 輸入有序數組 Two Sum II - Input a

摘要：公眾號愛寫給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值和，其中必須小于。示例輸入輸出解釋與之和等于目標數。公眾號：愛寫bug（ID：icodebugs）給定一個已按照升序排列的有序數組，找到兩個數使得它們相加之和等于目標數。函數應該返回這兩個下標值 index1 和 index2，其中 index1 必須小于 index2。...

張春雷 2019-08-16 18:29 評論0 收藏0