Gültige Paaranordnung

2097. Gültige Paaranordnung

Schwierigkeit:Schwer

Themen: Tiefensuche, Graph, Eulerscher Schaltkreis

Sie erhalten ein 0-indiziertes 2D-Integer-Array-Paare, wobeipairs[i] = [start_i, end_i]. Eine Anordnung von Paaren ist gültig, wenn für jeden Index i mit 1 <= i < pairs.length, wir haben end_i-1 == start_i.

Geben Sie jede gültige Anordnung von Paaren zurück.

Hinweis: Die Eingaben werden so generiert, dass eine gültige Paaranordnung vorliegt.

Beispiel 1:

• Eingabe: Paare = [[5,1],[4,5],[11,9],[9,4]]
• Ausgabe: [[11,9],[9,4],[4,5],[5,1]]
• Erklärung: Dies ist eine gültige Vereinbarung, da Ende_i-1 immer gleich Start_i ist.
  • Ende₀ = 9 == 9 = Anfang₁
  • Ende₁ = 4 == 4 = Anfang₂
  • Ende₂ = 5 == 5 = Anfang₃

Beispiel 2:

• Eingabe: Paare = [[1,3],[3,2],[2,1]]
• Ausgabe: [[1,3],[3,2],[2,1]]
• Erklärung: Dies ist eine gültige Vereinbarung, da Ende_i-1 immer gleich Start_i ist.
  • Ende₀ = 3 == 3 = Anfang₁
  • Ende₁ = 2 == 2 = Anfang₂
  • Die Vereinbarungen [[2,1],[1,3],[3,2]] und [[3,2],[2,1],[1,3]] gelten ebenfalls.

Beispiel 3:

• Eingabe: Paare = [[1,2],[1,3],[2,1]]
• Ausgabe: [[1,2],[2,1],[1,3]]
• Erklärung: Dies ist eine gültige Vereinbarung, da Ende_i-1 immer gleich Start_i ist.
  • Ende₀ = 2 == 2 = Anfang₁
  • Ende₁ = 1 == 1 = Anfang₂

Einschränkungen:

• 1 <= Paare.Länge <= 10⁵
• pairs[i].length == 2
• 0 <= Anfang_i, Ende_i <= 10⁹
• Anfang_i != Ende_i
• Keine zwei Paare sind genau gleich.
• Es existierteine gültige Anordnung von Paaren.

Hinweis:

1. Könnten Sie das in ein Diagrammproblem umwandeln?
2. Betrachten Sie die Paare als Kanten und jede Zahl als Knoten.
3. Wir müssen einen Eulerschen Pfad dieses Graphen finden. Der Hierholzer-Algorithmus kann verwendet werden.

Lösung:

Wir können es als Euler-Pfad-Problem in der Graphentheorie betrachten. In diesem Fall können die Paare als Kanten und die Werte innerhalb der Paare (Anfang und Ende) als Knoten behandelt werden. Wir müssen einen Eulerschen Pfad finden, der jede Kante genau einmal verwendet, und das Ende einer Kante muss mit dem Anfang der nächsten Kante übereinstimmen.

Wichtige Schritte:

1. Grafikdarstellung: Jede eindeutige Zahl in den Paaren ist ein Knoten und jedes Paar ist eine Kante von Anfang[i] bis Ende[i].
2. Kriterien des Eulerschen Pfades:
   • Ein Eulerscher Pfad existiert, wenn es genau zwei Knoten mit ungeraden Graden gibt und der Rest gerade Grade haben muss.
   • Wir müssen sicherstellen, dass der Graph verbunden ist (obwohl dies durch die Problemstellung garantiert wird).
3. Hierholzer-Algorithmus: Dieser Algorithmus kann verwendet werden, um den Eulerschen Pfad zu finden. Es beinhaltet:
   • Beginnend bei einem Knoten mit ungeradem Grad (falls vorhanden).
   • Überqueren Sie die Kanten und markieren Sie sie als besucht.
   • Wenn ein Knoten mit ungenutzten Kanten erreicht wird, fahren Sie mit der Durchquerung fort, bis alle Kanten verwendet sind.

Planen:

• Erstellen Sie ein Diagramm mithilfe einer Hash-Map, um die Adjazenzliste (jeder Knoten und seine verbundenen Knoten) zu speichern.
• Verfolgen Sie den Grad (In-Grad und Out-Grad) jedes Knotens.
• Verwenden Sie den Hierholzer-Algorithmus, um den Eulerschen Pfad zu finden.

Lassen Sie uns diese Lösung in PHP implementieren: 2097. Gültige Paaranordnung

<?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]]
?>




</p>
<h3>
  
  
  Erläuterung:
</h3>

<ol>
<li>
<p><strong>Grafikkonstruktion</strong>:</p>

<ul>
<li>Wir erstellen das Diagramm mithilfe einer Adjazenzliste, wobei jeder Schlüssel ein Startknoten und der Wert eine Liste von Endknoten ist.</li>
<li>Wir pflegen außerdem den Ausgangs- und Eingangsgrad für jeden Knoten, was uns hilft, den Startknoten für den Euler-Pfad zu finden.</li>
</ul>
</li>
<li>
<p><strong>Startknoten finden</strong>:</p>

<ul>
<li>Ein Eulerscher Pfad beginnt an einem Knoten, bei dem der Ausgangsgrad um 1 größer als der Eingangsgrad ist (falls ein solcher Knoten existiert).</li>
<li>Wenn kein solcher Knoten vorhanden ist, ist der Graph ausgeglichen und wir können bei jedem Knoten beginnen.</li>
</ul>
</li>
<li>
<p><strong>Hierholzer-Algorithmus</strong>:</p>

<ul>
<li>Wir beginnen am Startknoten und folgen wiederholt Kanten, markieren sie als besucht, indem wir sie aus der Adjazenzliste entfernen.</li>
<li>Sobald wir einen Knoten ohne weitere ausgehende Kanten erreichen, gehen wir zurück und erstellen das Ergebnis.</li>
</ul>
</li>
<li>
<p><strong>Ergebnis zurückgeben</strong>:</p>
<ul>
<li>Das Ergebnis wird aufgrund der Art und Weise, wie wir zurückverfolgen, in umgekehrter Reihenfolge erstellt, also kehren wir es am Ende um.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Beispielausgabe:
</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]]
?>

Zeitkomplexität:

• Aufbau des Diagramms: O(n), wobei n die Anzahl der Paare ist.
• Hierholzer-Algorithmus: O(n), da jede Kante einmal besucht wird.
• Gesamtzeitkomplexität: O(n).

Dieser Ansatz findet effizient eine gültige Anordnung von Paaren, indem er das Problem als Eulersches Pfadproblem in einem gerichteten Graphen behandelt.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonGültige Paaranordnung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!