ペアの有効な配置

2097年。有効なペアの配置

難易度: 難しい

トピック: 深さ優先探索、グラフ、オイラー回路

0 インデックスの 2D 整数配列ペアが与えられます。ここで、pairs[i] = [start_i, end_i]。すべてのインデックス i について、1 有効です。ペア.長さ、end_i-1 == start_i.

があります。

任意の ペアの有効な配置を返します。

注: 入力は、有効なペアの配置が存在するように生成されます。

例 1:

• 入力: ペア = [[5,1],[4,5],[11,9],[9,4]]
• 出力: [[11,9],[9,4],[4,5],[5,1]]
• 説明: end_i-1 は常に start_i と等しいため、これは有効な配置です。
  • 終了₀ = 9 == 9 = 開始₁
  • 終了₁ = 4 == 4 = 開始₂
  • 終了₂ = 5 == 5 = 開始₃

例 2:

• 入力: ペア = [[1,3],[3,2],[2,1]]
• 出力: [[1,3],[3,2],[2,1]]
• 説明: end_i-1 は常に start_i と等しいため、これは有効な配置です。
  • 終了₀ = 3 == 3 = 開始₁
  • 終了₁ = 2 == 2 = 開始₂
  • [[2,1],[1,3],[3,2]] および [[3,2],[2,1],[1,3]] の配置も有効です。

例 3:

• 入力: ペア = [[1,2],[1,3],[2,1]]
• 出力: [[1,2],[2,1],[1,3]]
• 説明: end_i-1 は常に start_i と等しいため、これは有効な配置です。
  • 終了₀ = 2 == 2 = 開始₁
  • 終了₁ = 1 == 1 = 開始₂

制約:

• 1 5
• ペア[i].length == 2
• 0 <= 開始_i、終了_i <= 10⁹
• 開始_i != 終了_i
• まったく同じペアは 2 つとありません。
• 有効なペアの配置が存在します。

ヒント:

1. これをグラフの問題に変換してもらえますか?
2. ペアをエッジ、各数値をノードとみなします。
3. このグラフのオイラー経路を見つける必要があります。 Hierholzer のアルゴリズムを使用できます。

解決策:

グラフ理論におけるオイラー経路問題としてアプローチできます。この場合、ペアはエッジとして扱うことができ、ペア内の値 (開始と終了) をノードとして扱うことができます。オイラー パスを見つける必要があります。これは、すべてのエッジを 1 回だけ使用するパスであり、1 つのエッジの終わりは次のエッジの始まりと一致する必要があります。

主な手順:

1. グラフ表現: ペア内のそれぞれの一意の番号がノードになり、各ペアが start[i] から end[i] までのエッジになります。
2. オイラーパス基準:
   • オイラー パスは、奇数の次数を持つノードが 2 つだけ存在する場合に存在し、残りのノードは偶数の次数を持つ必要があります。
   • グラフが接続されていることを確認する必要があります (ただし、これは問題ステートメントによって保証されています)。
3. Hierholzer のアルゴリズム: このアルゴリズムは、オイラー パスを見つけるために使用できます。それには以下が含まれます:
   • 奇数次数 (存在する場合) のノードから開始します。
   • エッジをトラバースし、訪問済みとしてマークします。
   • 未使用のエッジでノードに到達した場合は、すべてのエッジが使用されるまでトラバースを続けます。

プラン：

• ハッシュ マップを使用してグラフを構築し、隣接リスト (各ノードとそれに接続されているノード) を保存します。
• 各ノードの次数 (入次数と出次数) を追跡します。
• Hierholzer のアルゴリズムを使用してオイラー パスを見つけます。

このソリューションを PHP で実装してみましょう: 2097。ペアの有効な配置

<?php
/**
 * @param Integer[][] $pairs
 * @return Integer[][]
 */
function validArrangement($pairs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$pairs1 = [[5, 1], [4, 5], [11, 9], [9, 4]];
$pairs2 = [[1, 3], [3, 2], [2, 1]];
$pairs3 = [[1, 2], [1, 3], [2, 1]];

print_r(validArrangement($pairs1)); // Output: [[11, 9], [9, 4], [4, 5], [5, 1]]
print_r(validArrangement($pairs2)); // Output: [[1, 3], [3, 2], [2, 1]]
print_r(validArrangement($pairs3)); // Output: [[1, 2], [2, 1], [1, 3]]
?>




<h3>
  
  
  説明：
</h3>

<ol>
<li>
<p><strong>グラフの構築</strong>:</p>

<ul>
<li>各キーが開始ノード、値が終了ノードのリストである隣接リストを使用してグラフを構築します。</li>
<li>また、各ノードの出次数と入次数も維持します。これは、オイラー パスの開始ノードを見つけるのに役立ちます。</li>
</ul>
</li>
<li>
<p><strong>開始ノードの検索</strong>:</p>

<ul>
<li>オイラー パスは、出力次数が入力次数より 1 大きいノードから始まります (そのようなノードが存在する場合)。</li>
<li>そのようなノードが存在しない場合、グラフはバランスが取れており、どのノードからでも開始できます。</li>
</ul>
</li>
<li>
<p><strong>ヒアホルツァーのアルゴリズム</strong>:</p>

<ul>
<li>startNode から開始してエッジを繰り返したどり、隣接リストから削除することでエッジを訪問済みとしてマークします。</li>
<li>発信エッジがなくなったノードに到達したら、バックトラックして結果を構築します。</li>
</ul>
</li>
<li>
<p><strong>結果を返す</strong>:</p>
<ul>
<li>バックトラックの方法により、結果は逆の順序で構築されるため、最後に逆にします。</li>
</ul>
</li>
</ol>

<h3>
  
  
  出力例:
</h3>



<pre class="brush:php;toolbar:false"><?php
/**
 * @param Integer[][] $pairs
 * @return Integer[][]
 */
function validArrangement($pairs) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$pairs1 = [[5, 1], [4, 5], [11, 9], [9, 4]];
$pairs2 = [[1, 3], [3, 2], [2, 1]];
$pairs3 = [[1, 2], [1, 3], [2, 1]];

print_r(validArrangement($pairs1)); // Output: [[11, 9], [9, 4], [4, 5], [5, 1]]
print_r(validArrangement($pairs2)); // Output: [[1, 3], [3, 2], [2, 1]]
print_r(validArrangement($pairs3)); // Output: [[1, 2], [2, 1], [1, 3]]
?>

時間計算量:

• グラフの構築: O(n)、n はペアの数です。
• Hierholzer のアルゴリズム: O(n)、各エッジが 1 回訪問されるため。
• 全体の時間計算量: O(n).

このアプローチは、問題を有向グラフのオイラー経路問題として扱うことにより、ペアの有効な配置を効率的に見つけます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上がペアの有効な配置の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。