道路標識160号
15528 ワード
私の第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で一番上の文章を見ることができます
Reference
この問題について(道路標識160号), 我々は、より多くの情報をここで見つけました https://velog.io/@htogether7/리트코드-160번テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol