道路標識160号


私の第1ラウンド

var getIntersectionNode = function(headA, headB) {
    let a = [];
    let b = [];
    
    if (!headA.next && !headB.next) {
        if (headA === headB) return headA;
    } else if (!headA.next) {
        while (headB.next) {
            if (headA === headB) return headA;
            headB = headB.next;
        }
        if (headA === headB) return headA;
            headB = headB.next;
    } else if (!headB.next) {
        while (headA.next) {
            if (headA === headB) return headA;
            headA = headA.next;
        }
        if (headA === headB) return headA;
        headA = headA.next;    
    } else {
        while (headA.next && headB.next) {
            a.push(headA);
            b.push(headB);
            headA = headA.next;
            headB = headB.next;

            if (!headA.next && headB.next) {
                while (headB.next) {
                    b.push(headB);
                    headB = headB.next;
                }
                a.push(headA);
                b.push(headB);
            } else if (headA.next && !headB.next) {
                while (headA.next) {
                    a.push(headA);
                    headA = headA.next;
                }
                a.push(headA);
                b.push(headB);
            }

        }
        for (let i = 0; i < a.length; i++) {
            for (let j = 0; j < b.length; j++) {
                if (a[i] === b[j]) return a[i];
            }
        } 
    }

};
多くの例外処理と多くの重複文が使用されています.ルド問題とプログラマー問題はあまりにも違うような気がします.プログラマー問題が冗長な問題にアルゴリズムが隠されているとすれば,ツリーコードには簡単な問題があるが,うまく解けない.特に事前に関数を宣言したのは、関数の使用に慣れていないため、近づきにくいのかもしれません.今は解くスピードが遅く、メモリもたくさん消費されています.しかし、私が考えている方法はこれだけです.Follow upでO(n+m)で解けるのも挑戦です

私の2回目の答え

var getIntersectionNode = function(headA, headB) {
    let arr = [];
    while (headA !== null) {
        arr.push(headA);
        headA = headA.next;
    }
    while (headB !== null) {
        if (arr.includes(headB)) return headB;
        headB = headB.next;
    }
}
配列を作成し、headaのListNodeをすべて入れ、headbをarrに入れると戻ります.
コードはずっと簡単ですが、O(n+m)には達しません.

私の3回目の答え

var getIntersectionNode = function(headA, headB) {
    let map = new Map();
    while (headA !== null) {
        map.set(headA, "");
        headA = headA.next;
    }
    while (headB !== null) {
        if (map.has(headB)) return headB;
        headB = headB.next;
    }
}
地図を使って実現しました.ただし、メモリはO(1)を満たすことはできません.headaの長さによってmapの長さも異なるのでO(n)のメモリと考えられる.

他人の解答


O(1)では記憶が解けないような気がしたので、他人の解を見ました.headaとheadbをコピーしてポインタを付与し、3つの演算子を使用して解きます.言葉で説明するのは難解だ.そして、キラキラしたアイデアも必要だと思います.見たい人はディスカッション-javascriptで一番上の文章を見ることができます