使琴弦平衡最少的交換次數

1963. Nombre minimum d'échanges pour équilibrer la chaîne

Difficulté :Moyen

Sujets : Deux pointeurs, chaîne, pile, gourmand

Vous recevez une chaîne indexée à 0 s de longueur pair n. La chaîne est composée de exactement n/2 parenthèses ouvrantes '[' et n/2 parenthèses fermantes ']'.

Une chaîne est dite équilibrée si et seulement si :

• C'est la chaîne vide, ou
• Il peut s'écrire AB, où A et B sont tous deux équilibrés cordes, ou
• Il peut être écrit sous la forme [C], où C est une chaîne équilibrée.

Vous pouvez échanger les parenthèses à n'importe quel deux indices n'importe quel nombre de fois.

Renvoyer le nombre minimum de swaps pour réaliser des s équilibrés.

Exemple 1 :

• Entrée : s = "][]["
• Sortie : 1
• Explication : Vous pouvez équilibrer la chaîne en échangeant l'index 0 avec l'index 3.
  • La chaîne résultante est "[[]]".

Exemple 2 :

• Entrée : s = "]]][[["
• Sortie : 2
• Explication : Vous pouvez procéder comme suit pour équilibrer la chaîne :
  • Échangez l'index 0 avec l'index 4. s = "[]][][".
  • Échangez l'index 1 avec l'index 5. s = "[[][]]".
  • La chaîne résultante est "[[][]]".

Exemple 3 :

• Entrée : s = "[]"
• Sortie : 0
• Explication : La corde est déjà équilibrée.

Contraintes :

• n == s.length
• 2 <= n <= 10⁶
• n est pair.
• s[i] est soit '[' ou ']'.
• Le nombre de parenthèses ouvrantes '[' est égal à n/2, et le nombre de parenthèses fermantes ']' est égal à n/2.

Indice :

1. Parcourez la chaîne et gardez une trace du nombre de parenthèses d'ouverture et de fermeture à chaque étape.
2. Si le nombre de parenthèses fermantes est toujours plus grand, vous devez effectuer un échange.
3. Échangez-le avec le support d'ouverture le plus proche de la fin de s.

Solution :

Nous pouvons utiliser une approche à deux points, qui est efficace compte tenu des contraintes.

Approche:

1. Suivi de l'équilibre : au fur et à mesure que nous parcourons la chaîne, nous pouvons suivre l'équilibre entre les parenthèses d'ouverture et de fermeture :

   • Incrémentez le solde lorsque vous rencontrez '['.
   • Décrémentez le solde lorsque vous rencontrez ']'.

2. Identifier le déséquilibre : Lorsque le solde devient négatif, cela indique qu'il y a plus de parenthèses fermantes ']' que de parenthèses ouvrantes '[' à ce stade de la chaîne. C'est là que nous devons échanger les crochets pour équilibrer la corde.

3. Compter les Swaps : Pour corriger un déséquilibre :

   • Gardez un compteur max_imbalance pour suivre le déséquilibre maximum observé lors de l'itération.
   • Le nombre de swaps requis est égal à (max_imbalance 1) / 2, ce qui donne effectivement le nombre minimum de swaps nécessaires pour équilibrer la chaîne.

Implémentons cette solution en PHP : 1963. Nombre minimum d'échanges pour équilibrer la chaîne

  
  
  Explication:




Suivi du solde :



le solde garde une trace de la différence entre le nombre de '[' et ']'.
Si le solde devient négatif, cela indique qu'il y a plus de ']' que de '[' à ce stade.



Calculer le déséquilibre maximum :



max_imbalance stocke le plus gros déséquilibre rencontré lors de l'itération.
Si le solde devient négatif, mettez à jour max_imbalance avec le plus grand de max_imbalance ou -balance.



Calculer les échanges :


Pour corriger un déséquilibre, le swap minimum requis est de (max_imbalance 1) / 2.





  
  
  Complexité temporelle :



La complexité temporelle est O(n), où n est la longueur de la chaîne. Nous parcourons la chaîne une fois pour déterminer le max_imbalance.
La complexité spatiale est O(1) car nous utilisons quelques variables pour suivre l'équilibre et le déséquilibre maximal.


Cette solution garantit que nous respectons les contraintes, même pour des intrants importants.

Liens de contact
如果您發現本系列有幫助，請考慮在 GitHub 上給 存儲庫 一個星號或在您最喜歡的社交網絡上分享該帖子？ 。您的支持對我來說意義重大！ 

如果您想要更多類似的有用內容，請隨時關注我：


領英
GitHub



          

            
  

            
        
以上是使琴弦平衡最少的交換次數的詳細內容。更多資訊請關注PHP中文網其他相關文章！