パス シーケンスが任意の座標を 2 回以上訪れているかどうかを確認する

アプリケーションによっては、パス シーケンスが任意の座標を 2 回訪問するかどうかを確認する必要がある場合があります。これは、GPS 追跡システムで、たとえば車両が 2 点間を往復しているかどうかを検出する場合に役立ちます。この記事では、パス シーケンスが任意の座標を 2 回訪問するかどうかを確認する方法と、その C での実装について説明します。

＃＃＃アルゴリズム＃＃＃

この問題を解決するには、ハッシュ テーブルを使用して、これまでに訪問したすべての座標を追跡します。まずシーケンス内の最初の座標にアクセスし、それをハッシュ テーブルに追加します。次に、シーケンス内の後続の各座標について、それがすでにハッシュ テーブルに存在するかどうかを確認します。そうであれば、以前にこの座標にアクセスしたことがわかっているので、true を返すことができます。そうでない場合は、それをハッシュ テーブルに追加し、次の座標に進みます。すべての座標を訪問して重複が見つからなかった場合は、false を返すことができます。

＃＃＃例＃＃＃

これは、上記のアルゴリズムを C-

で実装したものです。 リーリー ＃＃＃出力＃＃＃ リーリー

テストケースの例

パス「上、下、下、左、左、右、上、上、下、上」を表すシーケンス「UDDLLRUUUDU」について考えてみましょう。

原点 (0, 0) から開始してパスを横断し、途中で座標を更新します。

各ステップで、新しい座標が以前に訪問されたことがあるかどうかを確認します。そうであれば、シーケンスが座標を 2 回訪問したことがわかり、true を返します。そうでない場合は、その座標を訪問済みとしてマークし、続行します。

特定のシーケンスに対してアルゴリズムがどのように機能するかは次のとおりです -

原点(0, 0)から開始

• “U”
  −
• (0, 1) まで移動します。 (0, 1) を訪問済みとしてマークします。

  "D"

  −
• (0, 0) まで下に移動します。 (0, 0) を訪問済みとしてマークします。

  "D"

  −
• (0, -1) まで下に移動します。 (0, -1) を訪問済みとしてマークします。

  “L”

  −
• (-1, -1) まで左に移動します。 (-1, -1) を訪問済みとしてマークします。

  “L”

  −
• (-2, -1) まで左に移動します。 (-2、-1) を訪問済みとしてマークします。

  “R”

  −
• (-1, -1) まで右に移動します。この座標は以前に訪問されているため、true を返します。

  シーケンスは座標に 2 回アクセスするため、関数は true を返します。 したがって、指定されたシーケンス "UDDLLRUUUDU" に対して、関数はシーケンスに 2 回アクセスされた座標を正しく返します。

  ＃＃＃結論は＃＃＃
この記事では、パス シーケンスが任意の座標を 2 回訪問したかどうかを確認する方法について説明しました。ハッシュ テーブルを使用して、これまでに訪問したすべての座標を追跡し、各ステップで重複がないかチェックします。アルゴリズムの C 実装も提供します

以上がパス シーケンスが任意の座標を 2 回以上訪れているかどうかを確認するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。