Minimisez le nombre de retournements afin qu'il n'y ait pas de paires de zéros consécutives dans la chaîne

Ici, nous devons manipuler la chaîne binaire afin qu'elle ne contienne aucun zéro consécutif. Si nous trouvons des zéros consécutifs, nous devons changer n'importe quel zéro en 1. Nous devons donc compter le nombre total de 0. en 1 conversion nous devrions effectuer pour supprimer tous les zéros consécutifs de la chaîne.

Énoncé du problème - On nous donne une chaîne binaire « str » qui ne contient que 0 et 1. Nous devons trouver le nombre minimum de retournements requis pour que la chaîne résultante ne contienne pas de zéros consécutifs.

Exemple Exemple

Input –  0101001

Output – 1

Explication

Nous devons inverser uniquement l’avant-dernier zéro.

Input –  str = 00100000100

Output – 4

Explication

Nous devons inverser les 2ème, 5ème, 7ème et 11ème zéros pour éliminer toutes les paires de zéros consécutives.

Input –  0101010101

Output – 0

Explication

Nous n'avons pas besoin de retourner puisqu'il n'y a pas de zéros consécutifs dans la chaîne.

Méthode 1

Dans cette méthode, nous allons parcourir la chaîne du début à la fin et retourner les caractères si elle contient des zéros consécutifs. Enfin, nous pouvons obtenir le nombre minimum de retournements requis pour supprimer tous les zéros consécutifs d’une chaîne binaire donnée.

Algorithme

• Étape 1 - Initialisez la variable 'cnt' avec zéro, stockant un nombre total de flips.

• Étape 2 - Parcourez la chaîne binaire en utilisant la boucle.

• Étape 3 - Si le caractère à l'index 'I' et à l'index 'I +1' est 0, retournez le caractère suivant et augmentez la valeur de la variable 'cnt' de 1.

• Étape 4 - Lorsque l'itération de la boucle for est terminée, renvoyez la valeur de 'cnt'.

Exemple

#include <bits/stdc++.h>
using namespace std;
// Function to get the total number of minimum flips required so the string does not contain any consecutive 0’s
int findCount(string str, int len){

   // initialize the count
   int cnt = 0;
   
   // iterate over the string
   for (int i = 0; i < len - 1; i++){
   
      // If two consecutive characters are the same
      if (str[i] == '0' && str[i + 1] == '0'){
      
         // Flip the next character
         str[i + 1] = '1';
         
         // increment count
         cnt++;           
      }
   }
   return cnt;
}
int main(){
   string str = "00100000100";
   int len = str.length();
   cout << "The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - " << findCount(str, len);
   return 0;
}

Sortie

The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - 4

Complexité temporelle − O(N), lorsque nous parcourons la chaîne binaire.

Complexité spatiale − O(1), car nous utilisons un espace constant pour stocker le nombre total.

Conclusion

Nous avons appris à calculer le nombre minimum de retournements requis pour supprimer des paires consécutives de zéros d'une chaîne binaire donnée. L'utilisateur peut essayer de calculer le nombre minimum de retournements requis pour supprimer une paire consécutive d'une chaîne binaire donnée.

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!