LeetCode.2両数加算(Add Two Numbers)(JS)


先週の日曜日にvueを書きたいです.nexttickのソースコードの分析、しかしいつもどこから手をつけることを知らないで、今日时间があって、先にleetcodeの第2题を补って、この问题はまたとても简単だと感じます

一、テーマ


2つの合計:
2つの非負の整数を表すために、2つの非空のチェーンテーブルが与えられる.ここで、それぞれのビット数は逆順序で格納され、各ノードには1桁の数字しか格納されません.この2つの数を加算すると、新しいチェーンテーブルが返され、合計が表示されます.数値0以外の2つの数は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)))
    };

2つのチェーンテーブルで表される数の和を計算し、合計3つのステップに分けます.
  • 冷蔵庫のドアをチェーンテーブルを開けて配列を回す.
  • の2つの配列を加算して配列を得る.
  • および配列回転チェーンテーブル
  • 私の書き方の答えは分かりやすくて、説明をしないで、ここで書く時に1つの穴に出会って第2歩の2つの配列の加算について、最初の構想はそうではありませんて、Stringに回転して更にNumberを回転して加算して更に回転して帰って、それではこの構想はどこに折れて、1つのテストの用例は[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,1]と[5,6,4]に回転して、Numberに1 e+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%を破って、私を振っていくつかの街を知らないで、各種の優秀な答えを見ていつも認知を更新することができて、彼の構想を見てまず彼は関数を変えて、関数の本意は2つのチェーンテーブルを加えることで、彼は2つのノードを加えることに変えて、参数の中でcurrの意味は前のグループのノードが加算されているかどうかを意味して、この名前を見てから関数内を見て、if部分のコードは最後の境界状況を処理する例[1],[9,9,9,9]すなわち,2つのチェーンテーブルを遍歴した後,前回遍歴してキャリーがあった場合,newの1つのノードelse内は主要なノード加算部分であり,ここで
        if(l1 == null) l1 = new ListNode(0)
        if(l2 == null) l2 = new ListNode(0)
        let nextVal = (l2.val || 0) + (l1.val || 0) + curr

    (l 2.val||0)明らかに余計で、彼はもともとlet nextVal = (l2.val || 0) + (l1.val || 0) + currと書いていたと思いますが、実行はnull点がvalを出ないことを発見し、上の判断を加えましたが、下の削除はなく、コードの評価を簡略化しません.残りのロジックは明らかで、進位とか、でもこのような同期遍歴は本当に巧みで、私はどうして学ぶことができません/顔を覆うことができません

    四、道が長くて遠い


    これらの問題の提出はすべてスナップにありますが、この問題を完成して優秀な答えを見てみると、上位の答えの戻り値がArrayであることに気づきました.私は自分でコピーしてもテストの例を越えることができません.力ボタンがleetcodeのように全面的に更新されていないのではないでしょうか.問題が変わっても答えは変わっていません.決定したらleetCodeに提出しましょう.優秀な答えの最後の3行をよく見てみましょう.今日のブログはここまでで、次の第4題の難易度はhardで、恐れのあまり、突然いろいろな神仙の解法/顔を見ることを期待しています.

    THE END


    2019.3.27更新前に優秀な答えを感じた最後の3行を尾再帰で最適化(尾再帰を知らない仲間はここをクリック)して、よく考えてみましたが、できませんでした.
    最後の再帰の実装では、再帰関数を書き換え、最後のステップが自身だけを呼び出すことを確保する必要があることが多い.これを行う方法は,使用するすべての内部変数を関数のパラメータに書き換えることである.
    理由は以下の通りである:上述のように最後の再帰を実現すると仮定すると、関数には3つのパラメータが必要であり、それぞれl 1,l 2、および現在組み立てられているlistNodeオブジェクトが必要であり、呼び出すたびにl 1が必要である.val + l2.valは、現在組み立てられているオブジェクトの最深層に値を割り当て、オブジェクトの最深層を得るには、ハンマーを最適化する必要があります.しかし、このように分析すると、優秀な答えの著者は本来、尾再帰最適化を意図している可能性があるので、3番目のパラメータにcurrと命名し、損得がないことを発見した後、このやり方を放棄し、3番目のパラメータの役割をキャリーに変更したが、量名を変更したわけではないが、この符号化習慣は上述したlet nextVal = (l2.val || 0) + (l1.val || 0) + currのコードが簡略化されていない理由に合っている.優秀な答えを分析して事件を解決する感じを分析することができて、私も私自身に従います