[Leetcode][javascript]第2題:両方を足します.

16587 ワード

テーマ
二つの非空チェーン表を与えて、二つの非負の整数を表します.ビット数は逆順に記憶され、各ノードは単一の数字だけを記憶する.2つの数値を合わせて新しいチェーンを返します.
この二つの数字はゼロ以外はゼロで始まると仮定できます.
例:
入力:(2->4->>3)+(5->6->4)出力:7->0->8原因:342+465=807
法を解く
公式解析アドレス:https://leetcode-cn.com/articles/add-two-numbers/
/**
 * 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) {
    let dummyHead = new ListNode(0),carry = 0,curr = dummyHead;
     
    while (l1 !== null || l2 !== null) {
        let num1 = l1 ? l1.val : 0;
        let num2 = l2 ? l2.val : 0;
        let sum = num1 + num2 + carry;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
        carry = sum > 9 ? 1 : 0;
        l1 = l1 ? l1.next : l1;
        l2 = l2 ? l2.next : l2;
    }

    if (carry > 0) {
        curr.next = new ListNode(1);
    }

    return dummyHead.next;
};
個人的なステップのまとめ
  • はチェーンを配列として始めました.チェーンの意味は分かりましたが、JavaScriptの中ではどのような状況なのかよく分かりません.そして与えられたテストケースの入力は二つの配列です.簡単で乱暴なものを配列として書きました.しかし、提出する時はどうしてもパスできません.そして私は注釈にListNodeの構造関数があることを観察して、なんとか次のaddTwoNumbersの中の二つのパラメータのval、next、length属性を出力しました.発見の結果は珍しいです.行列のように見えますが、実はそうではありません.例えば、[2,4,3]を入力すると、そのvalは2で、nextは[4,3]と表示され、lengthはundefinedとなります.この時はチェーンの意味を大体理解しました.
  • はnew ListNode()を先に返して、nextを書いて、中間関数を書きました.一つの中間パラメータを使って循環後にnextを保存すると思い付きました.curr.next = new ListNode(sum % 10); curr = curr.next;のようですが、その時は分かりたくなくて、いつもすべてのテストケースを満たすことができなくて、先にこのような方法を放棄して、考えを変えて先に効果を実現するつもりです.その後資料を探して、見つけました.https://segmentfault.com/a/1190000008706650 中のapped方法を参考にして、自分で中間の方法を書きましたが、この問題だけを満足させると、毎回最後のnextを再循環してから値を付ける必要はありません.最後に実現したコードは見たところとても愚かで、しかも時間がかかります.他の似たようなブログ「javascriptのチェーン構造」を紹介します.詳しい話をします.https://www.cnblogs.com/tylerdonet/p/5880088.html .
    /**
     * 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) {
        let l3;
        let pre = 0;
        function _append(_val){
            let _l3 = new ListNode(_val);
            let l4;
            if(l3){
                l4 = l3;
                while(l4.next){
                    l4 = l4.next;
                }
                l4.next = _l3;
            }else{
                l3 = _l3;
            };
        }
        
        while(l1.val || l2.val || l1.val === 0 || l2.val === 0){
            let sum = (l1.val||0 ) + (l2.val||0) + pre;
            pre = sum>9 ? 1 : 0;
            _append(sum%10);
            l1 = l1.next || {};
            l2 = l2.next || {};
            
        }
    
        if(pre){
            _append(1);
        }
    
        return l3;
    };
    
  • 公式解析によると、new ListNode()を先にしないようにして、nextを返します.今は公式解析後のコードを見て、どうやって私の前に欲しい効果に変えたらいいのかが分かりました.しかし、コード全体は循環毎に多くの判断をする必要があります.
    /**
     * 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) {
        let dummyHead,carry = 0,curr;
         
        while (l1 !== null || l2 !== null) {
            let num1 = l1 ? l1.val : 0;
            let num2 = l2 ? l2.val : 0;
            let sum = num1 + num2 + carry;
            if(!dummyHead){
                dummyHead = new ListNode(sum % 10);
                curr = dummyHead;
            }else{
                curr.next = new ListNode(sum % 10);
                curr = curr.next;
            }
            carry = sum > 9 ? 1 : 0;
            l1 = l1 ? l1.next : l1;
            l2 = l2 ? l2.next : l2;
        }
    
        if (carry > 0) {
            curr.next = new ListNode(1);
        }
    
        return dummyHead;
    };