今日、私たちはあなたをもたらす、リングにチェーンテーブル検出の古典的なトピック。あなたがそう思うなら、あなたはより多くの忍耐強く、慎重に読みたいと思うかもしれませんしてください、私はいくつかの異なる収穫があると信じています！またはトピックYOで始まる、準備はいいですか？ 行こう！
この本では、トピックを分析しています。
| 連鎖表が与えられたとき、その中に環があるかどうかを判定しなさい。与えられた連鎖表にリングがあることを表すには、連鎖表の中で端のリンクがつながっている位置を表す整数posを使います。pos が -1 なら、その連鎖表にはリングがありません。 |
例1：
入力：頭 = [3,2,0,-4], pos = 1
出力：真
解説：連鎖表の中にリングがあり、そのテールは2番目のノードに接続されている。
例2：
入力：頭 = [1,2], pos = 0
出力：真
解説：連鎖表の中に、末尾が最初のノードにつながっているリングがある。
例 3：
入力：頭 = [1], pos = -1
出力：偽
解説：連鎖表には輪がない。
このタイトルは簡単すぎると思うかもしれません！でも、辛抱強く読んでみてください！
そうすれば必ず何かを得られるはずです！
この本では、トピックを分析しています。
トピック解決策1：ハッシュテーブルの決定
アイデア：チェーンテーブルがリング状になっているかどうかを判断するために、ノードがハッシュテーブルを通してアクセスされたかどうかを検出します。これが一番考えやすい。コードに直行するにはシンプルすぎます：
func hasCycle(head *ListNode) bool {
m := make(map[*ListNode]int)
for head != nil {
if _,exist := m[head];exist {
return true
}
m[head]= 1 9
head = head.Next
}
return false12
}
問題解決2：JS特殊解
JSのJSON.stringify()メソッドは、主にJSオブジェクトをJSON文字列に変換するために使用します。基本的な使い方は以下の通りです：
var car = {
name: ' ,
age: 20,
}
var str = JSON.stringify(car);
console.log(str)
//=> {"name":" ,"age":20}
考えてみてください、このような関数を自分で実装する場合、どのような特殊なケースに対応する必要があるでしょうか？そう、循環参照です。というのも、循環参照はJSONの構造で示すのが難しいからです！例えば、以下のような場合です：
var a = {}
var b = {
a: a
}
a.b = b
console.log(JSON.stringify(a))
//=> TypeError: Converting circular structure to JSON
環状に連結されたテーブルは、環状構造ではありませんか？もちろんそうです！なぜなら、循環連鎖テーブルである限り、以下のようなコードを持たなければならないからです：
a.Next = b b.Next = a
つまり、JSON.stringify()のプロパティで解決できます：
var hasCycle = function(head) {
try{
JSON.stringify(head)
}catch(e){
return true
}
return false
};
もちろん、この解決策は、この問題に対する標準的な解決策ではありません！もちろん、この解決策は、この問題に対する標準的な解決策ではありません！
問題解決法3：ダブルポインタの解決法
この問題の標準的な解法です！マスターすべき常識的な要素です！
アイデアソース：まず、2人のアスリートが異なるスピードでトラックを走ったときに何が起こるかを想像してください。ミーティング！さて、こんな質問が出ます。
解答：速度の異なる2つのポインタ（速いポインタと遅いポインタ）を使って連鎖表をトラバースすることで、空間の複雑さをO(1)に減らすことができます。遅いポインタは一度に1ステップ移動し、速いポインタは一度に2ステップ移動します。
連鎖表を
分析が終わったら、そのままコードに進みます：
func hasCycle(head *ListNode) bool {
if head == nil {
return false
}
fast := head.Next // クイック・ポインター、一度に2つのステップ
for fast != nil && head != nil && fast.Next != nil {
if fast == head { // 速いポインタと遅いポインタが出会い、リングを示す
return true
}
fast = fast.Next.Next
head = head.Next // スロー・ポインタ、一歩ずつ
}
return false
}
スロー・ポインタのステップを1に、ファースト・ポインタのステップを2に設定する理由は重要です。
まず、スロー・ポインターのステップ数が1である理由は簡単で、スロー・ポインターを各要素まで歩かせる必要があるからです。2の高速ポインタのステップの長さは、1つだけの相対速度の違いの共通点として理解することができ、高速のみ1つのグリッドで、必然的にグリッドで会う遅い追いかけることができます。
もし理解できないなら、分析する：速い速い遅い追いつくために、それらの間に1～2マスだけでなければなりません。もし1マス遅れていれば、次に追いつくでしょう。もし2マス遅れていれば、次は1マス遅れて、次に追いつきます！下の図のように：
つまり、高速ポインターのステップサイズは2に設定できます。
特記事項
いわゆる「素朴な疑問」にしばしば遭遇し、前世代が残した「古典的な解法」を使って素早く回答することがあります。問題を解く過程で、定型化、テンプレート化を追求するのです。もちろん、社会でも仕事でも勉強でも必要なことですから、このプロセスは良いことです！しかし、私は、それが最適な解決策でなくても、それは私自身のアイデア、創造であり、私自身の思考の一部を残すことができることを願っています！アルゴリズミックな問題に喜びを感じてください。
私が書いたすべての解答を、各問題の完全な図解付きの電子書籍に整理しました。
