Arrangement valide des paires

2097. Arrangement valide des paires

Difficulté : Difficile

Sujets : Recherche en profondeur d'abord, graphique, circuit eulérien

Vous recevez un tableau d'entiers 2D indexé 0 paires où paires[i] = [start_i, end_i]. Un arrangement de paires est valide si pour chaque indice i où 1 <= i < paires.longueur, nous avons fin_i-1 == début_i.

Renvoyer tout arrangement de paires valide.

Remarque : Les entrées seront générées de telle sorte qu'il existe un arrangement valide de paires.

Exemple 1 :

• Entrée : paires = [[5,1],[4,5],[11,9],[9,4]]
• Sortie : [[11,9],[9,4],[4,5],[5,1]]
• Explication : Il s'agit d'un arrangement valide puisque fin_i-1 est toujours égal à début_i.
  • fin₀ = 9 == 9 = début₁
  • fin₁ = 4 == 4 = début₂
  • fin₂ = 5 == 5 = début₃

Exemple 2 :

• Entrée : paires = [[1,3],[3,2],[2,1]]
• Sortie : [[1,3],[3,2],[2,1]]
• Explication : Il s'agit d'un arrangement valide puisque fin_i-1 est toujours égal à début_i.
  • fin₀ = 3 == 3 = début₁
  • fin₁ = 2 == 2 = début₂
  • Les arrangements [[2,1],[1,3],[3,2]] et [[3,2],[2,1],[1,3]] sont également valables.

Exemple 3 :

• Entrée : paires = [[1,2],[1,3],[2,1]]
• Sortie : [[1,2],[2,1],[1,3]]
• Explication : Il s'agit d'un arrangement valide puisque fin_i-1 est toujours égal à début_i.
  • fin₀ = 2 == 2 = début₁
  • fin₁ = 1 == 1 = début₂

Contraintes :

• 1 <= paires.longueur <= 10⁵
• paires[i].length == 2
• 0 <= début_i, fin_i <= 10⁹
• début_i != fin_i
• Il n'y a pas deux paires exactement identiques.
• Il existe un arrangement de paires valide.

Indice :

1. Pourriez-vous convertir cela en un problème graphique ?
2. Considérez les paires comme des arêtes et chaque nombre comme un nœud.
3. Il faut trouver un chemin eulérien de ce graphe. L’algorithme de Hierholzer peut être utilisé.

Solution :

Nous pouvons l'aborder comme un problème de chemin eulérien en théorie des graphes. Dans ce cas, les paires peuvent être traitées comme des arêtes et les valeurs contenues dans les paires (le début et la fin) peuvent être traitées comme des nœuds. Nous devons trouver un chemin eulérien, qui est un chemin qui utilise chaque arête exactement une fois, et la fin d'une arête doit correspondre au début de l'arête suivante.

Étapes clés :

1. Représentation graphique : Chaque nombre unique dans les paires sera un nœud, et chaque paire sera une arête du début[i] à la fin[i].
2. Critères du chemin eulérien :
   • Un chemin eulérien existe s'il y a exactement deux nœuds de degrés impairs, et le reste doit avoir des degrés pairs.
   • Nous devons nous assurer que le graphique est connecté (bien que cela soit garanti par l'énoncé du problème).
3. Algorithme de Hierholzer : Cet algorithme peut être utilisé pour trouver le chemin eulérien. Cela implique :
   • Commençant à un nœud avec un degré impair (le cas échéant).
   • Traverser les bords, les marquant comme visités.
   • Si un nœud est atteint avec des arêtes inutilisées, continuez à parcourir jusqu'à ce que toutes les arêtes soient utilisées.

Plan:

• Construisez un graphique à l'aide d'une carte de hachage pour stocker la liste de contiguïté (chaque nœud et ses nœuds connectés).
• Suivez le degré (degré entrant et sortant) de chaque nœud.
• Utilisez l'algorithme de Hierholzer pour trouver le chemin eulérien.

Implémentons cette solution en PHP : 2097. Arrangement valide des paires

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

<ol>
<li>
<p><strong>Construction de graphiques</strong> :</p>

<ul>
<li>Nous construisons le graphique en utilisant une liste de contiguïté où chaque clé est un nœud de départ et la valeur est une liste de nœuds de fin.</li>
<li>Nous maintenons également le degré sortant et le degré entrant pour chaque nœud, ce qui nous aidera à trouver le nœud de départ du chemin eulérien.</li>
</ul>
</li>
<li>
<p><strong>Trouver le nœud de départ</strong> :</p>

<ul>
<li>Un chemin eulérien commence à un nœud où le degré sortant est supérieur de 1 au degré entrant (si un tel nœud existe).</li>
<li>Si aucun nœud de ce type n'existe, le graphique est équilibré et nous pouvons commencer à n'importe quel nœud.</li>
</ul>
</li>
<li>
<p><strong>Algorithme de Hierholzer</strong> :</p>

<ul>
<li>Nous partons du startNode et suivons les bords à plusieurs reprises, les marquant comme visités en les supprimant de la liste de contiguïté.</li>
<li>Une fois que nous atteignons un nœud sans plus d'arêtes sortantes, nous revenons en arrière et construisons le résultat.</li>
</ul>
</li>
<li>
<p><strong>Renvoyer le résultat</strong> :</p>
<ul>
<li>Le résultat est construit dans l'ordre inverse à cause de la façon dont on revient en arrière, donc on l'inverse à la fin.</li>
</ul>
</li>
</ol>

<h3>
  
  
  Exemple de sortie :
</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]]
?>

Complexité temporelle :

• Construction du graphique : O(n), où n est le nombre de paires.
• Algorithme de Hierholzer : O(n), car chaque arête est visitée une fois.
• Complexité temporelle globale : O(n).

Cette approche trouve efficacement un arrangement valide de paires en traitant le problème comme un problème de chemin eulérien dans un graphe orienté.

Liens de contact

Si vous avez trouvé cette série utile, pensez à donner une étoile au référentiel sur GitHub ou à partager la publication sur vos réseaux sociaux préférés ?. Votre soutien signifierait beaucoup pour moi !

Si vous souhaitez du contenu plus utile comme celui-ci, n'hésitez pas à me suivre :

• LinkedIn
• GitHub

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!