Nombre minimum de modifications pour rendre la chaîne binaire belle

2914. Nombre minimum de modifications pour rendre la chaîne binaire belle

Difficulté :Moyen

Sujets : Chaîne

Vous recevez une chaîne binaire indexée à 0 ayant une longueur paire.

Une chaîne est belle s'il est possible de la partitionner en une ou plusieurs sous-chaînes telles que :

• Chaque sous-chaîne a une longueur paire.
• Chaque sous-chaîne contient seulement des 1 ou uniquement des 0.

Vous pouvez changer n'importe quel caractère de s en 0 ou 1.

Renvoyer le nombre minimum de modifications nécessaires pour rendre la chaîne belle.

Exemple 1 :

• Entrée : s = "1001"
• Sortie : 2
• Explication : Nous changeons s[1] en 1 et s[3] en 0 pour obtenir la chaîne "1100".
  • On voit que la chaîne "1100" est belle car on peut la partitionner en "11|00".
  • On peut prouver que 2 est le nombre minimum de changements nécessaires pour rendre la ficelle belle.

Exemple 2 :

• Entrée : s = "10"
• Sortie : 1
• Explication : Nous changeons s[1] en 1 pour obtenir la chaîne "11".
  • On voit que la chaîne "11" est belle car on peut la partitionner en "11".
  • On peut prouver que 1 est le nombre minimum de changements nécessaires pour rendre la ficelle belle.

Exemple 3 :

• Entrée : s = "0000"
• Sortie : 0
• Explication : Nous n'avons pas besoin d'apporter de modifications car la chaîne "0000" est déjà belle.

Contraintes :

• 2 <= s.length <= 10⁵
• s a une longueur paire.
• s[i] est soit « 0 » soit « 1 ».

Indice :

1. Pour toute partition valide, puisque chaque partie est constituée d'un nombre pair des mêmes caractères, nous pouvons diviser davantage chaque partie en longueurs d'exactement 2.
2. Après avoir remarqué le premier indice, nous pouvons décomposer la chaîne entière en blocs disjoints de taille 2 et trouver le nombre minimum de modifications requises pour rendre ces blocs beaux.

Solution :

Nous devons nous assurer que chaque paire de caractères de la chaîne binaire s est soit "00" soit "11". Si une paire ne se trouve pas dans l'un de ces deux motifs, nous devrons changer l'un des caractères pour le faire correspondre.

Voici l'approche de la solution étape par étape :

1. Divisez la chaîne en blocs : Puisqu'une belle chaîne peut être formée à partir de blocs de longueur 2, nous pouvons parcourir la chaîne par étapes de 2.

2. Compte des modifications : Pour chaque bloc de 2 caractères, nous devons déterminer le caractère majoritaire (soit 0, soit 1). Nous modifierons le caractère minoritaire dans le bloc pour qu'il corresponde au caractère majoritaire.

3. Calculer les modifications minimales : Pour chaque bloc, si les deux caractères sont différents, nous aurons besoin d'1 modification ; s'ils sont identiques, aucune modification n'est requise.

Implémentons cette solution en PHP : 2914. Nombre minimum de modifications pour rendre la chaîne binaire belle

  
  
  Explication:



Définition de la fonction : Nous définissons une fonction minChanges qui prend une chaîne binaire s.
Initialisation : Nous initialisons une variable $changes pour garder une trace du nombre de modifications requises.

Itérer sur la chaîne : Nous parcourons la chaîne en incrémentant de 2 à chaque fois pour vérifier chaque bloc de deux caractères :



$first est le caractère à la position actuelle.

$second est le caractère à la position suivante.


Vérifier les modifications : Si les caractères du bloc actuel sont différents, nous incrémentons le compteur $changes de 1.
Résultat du retour : Enfin, nous renvoyons le nombre total de modifications requises.



  
  
  Complexité:




Complexité temporelle : O(n), où n est la longueur de la chaîne, comme nous le sommes parcourir la chaîne une fois.

Complexité spatiale : O(1), puisque nous utilisons une quantité constante d'espace supplémentaire.


Cette solution fonctionne en O(n) complexité temporelle, où n est la longueur de la chaîne, ce qui la rend efficace pour les contraintes données.

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!