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

Binguner 發(fā)布于2019-08-23 16:26 / 1808人閱讀

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

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

一、題目

兩數(shù)相加：

給出兩個 非空 的鏈表用來表示兩個非負的整數(shù)。其中，它們各自的位數(shù)是按照 逆序 的方式存儲的，并且它們的每個節(jié)點只能存儲 一位 數(shù)字。如果，我們將這兩個數(shù)相加起來，則會返回一個新的鏈表來表示它們的和。您可以假設(shè)除了數(shù)字 0 之外，這兩個數(shù)都不會以 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)))
    };

計算兩個鏈表表示的數(shù)的和，統(tǒng)共分三步：

~~把冰箱門打開~~ 鏈表轉(zhuǎn)數(shù)組；

兩個數(shù)組相加得到和數(shù)組；

和數(shù)組轉(zhuǎn)鏈表

我的寫法答案簡單易懂，就不做解釋，這里說一下寫的時候碰到一個坑
關(guān)于第二步兩個數(shù)組相加，一開始的思路并不是這樣的，而是轉(zhuǎn)成String再轉(zhuǎn)Number相加再轉(zhuǎn)回來，那么這個思路折哪兒了呢，有一個測試用例是[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]，轉(zhuǎn)成Number相加得1e+30，沒錯，萬惡的弱類型，查詢能不能不轉(zhuǎn)換，未果，就只能遍歷各數(shù)位相加了

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

三、優(yōu)秀答案

/**
 * 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
    }
};

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

    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但是執(zhí)行發(fā)現(xiàn)null點不出val，就加了上面的判斷不過下面的沒刪，不精簡代碼差評。
剩下的邏輯就顯而易見了，進位什么的，不過這種同步遍歷真的很巧妙，我怎么就是學不會/捂臉

四、路漫漫其修遠兮

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

THE END

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

尾遞歸的實現(xiàn)，往往需要改寫遞歸函數(shù)，確保最后一步只調(diào)用自身。做到這一點的方法，就是把所有用到的內(nèi)部變量改寫成函數(shù)的參數(shù)。

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