Nombre minimum d'inversions de préfixe requis pour convertir une chaîne binaire en une autre

Dans ce problème, nous devons convertir la première chaîne binaire en deuxième chaîne binaire en retournant son préfixe. Pour obtenir le nombre minimum d'inversions de préfixe, nous devons parcourir la fin des chaînes, et si un caractère non correspondant est trouvé dans les deux chaînes, nous devons inverser le préfixe de la première chaîne.

Énoncé du problème - On nous donne deux chaînes binaires différentes appelées première et seconde. Les deux chaînes binaires sont de longueur égale, N. Nous devons convertir la première chaîne en deuxième chaîne en retournant son préfixe. Ici, nous devons calculer le nombre total de retournements de préfixe requis pour convertir une chaîne en une autre. Flip signifie convertir « 0 » en « 1 » et « 1 » en « 0 ».

Exemples d'exemples

Input –  first = "001", second = "000"

Output – 2

Explication

• Tout d'abord, nous devons inverser le préfixe de longueur 3 pour la première chaîne, et la chaîne résultante sera 110.

• Après cela, nous devons inverser le préfixe de longueur 2 et la chaîne résultante sera 000, ce qui est égal à la deuxième chaîne.

Input –  first = "10", second = "01"

Output – 1

Explication

Nous devons inverser le préfixe de longueur 2, et la chaîne résultante sera « 01 », qui est égale à la deuxième chaîne.

Input –  first = "11", second = "11"

Output – 0

Explication

Étant donné que les deux chaînes sont égales, nous n’avons pas besoin de les retourner.

Approche 1

Dans cette méthode, nous parcourons à partir de la fin de la chaîne et si nous trouvons un caractère qui ne correspond pas, nous retournons tous les caractères du préfixe de longueur « I + 1 ». C'est un moyen simple de résoudre le problème.

Algorithme

• Étape 1 - Définissez la variable 'cnt' et initialisez-la à 0.

• Étape 2 - Commencez à parcourir la chaîne depuis la fin en utilisant la boucle.

• Étape 3 − Si premier[i] et deuxième[i] ne sont pas égaux, nous devons inverser tous les caractères du préfixe dont la longueur est égale au I + 1.

• Étape 4 - Utilisez la boucle nest for pour parcourir le préfixe de longueur égale à I + 1 et retournez chaque caractère de celui-ci en exécutant la fonction flipBits().

• Étape 4.1 - Nous renvoyons « 0 » si le caractère actuel est « 1 » et « 1 » si le caractère actuel est « 0 » dans la fonction flipBits().

• Étape 5 - Augmentez la valeur de la variable 'cnt' de 1 lorsque nous retournons le préfixe.

• Étape 6 - Renvoyez la valeur de la variable 'cnt'.

Exemple

#include <bits/stdc++.h>
using namespace std;
char flipBits(char ch){
   // if the bit is '0', flip it to '1', else flip it to '0'.
   return (ch == '0') ? '1' : '0';
}
int minimumFlips(string first, string second, int n){
   // to store the count of flips
   int cnt = 0;
   
   // Traverse the string
   for (int i = n - 1; i >= 0; i--){
   
      // If first[i] is not equal to second[i]
      if (first[i] != second[i]){
      
         // flip the bits
         for (int j = 0; j <= i; j++){
            first[j] = flipBits(first[j]);
         }
         cnt++;
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Sortie

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Approche 2

Dans cette approche, nous utiliserons la variable « inversée » pour savoir si le bit actuel est inversé ou non, plutôt que d'inverser chaque bit de préfixe à chaque fois. Nous avons également optimisé la complexité temporelle du code dans cette approche.

Algorithme

• Étape 1 - Définissez la variable « cnt » et initialisez-la avec « 0 ». Définissez également la variable « inversée » et initialisez-la avec une valeur fausse.

.

• Étape 2 - Parcourez la corde en commençant par la fin. Si les premier [i] et deuxième [i] caractères ne correspondent pas, procédez comme suit.

• Étape 2.1 - Si la valeur de « inversé » est fausse, augmentez la valeur de la variable « cnt » de 1 et changez la valeur de la variable « inversée » en vrai.

• Étape 3 - Si les deux caractères correspondent et que la valeur de « inversé » est vraie, nous devons à nouveau inverser le bit. Donc, augmentez la valeur de « cnt » de 1 et changez la valeur de « inversé ». 'à faux.

Exemple

Déboguons l'algorithme ci-dessus en prenant l'exemple.

Input – first = ‘001’, second = ‘000’

• Dans la première étape, le premier [2] et le deuxième [2] ne correspondent pas et la valeur de « inversé » est fausse. Par conséquent, la valeur de « cnt » deviendra 1 et « inversé » deviendra vrai. Ici, en changeant la valeur de « inversé » en vrai, nous supposons que nous avons virtuellement inversé le préfixe.

• Après cela, le premier[1] et le deuxième[1] correspondent, mais la valeur de « inversé » est vraie. Ainsi, la valeur « cnt » deviendra 2 et « inversé » est faux.

• Ensuite, le premier[0] et le deuxième[0] correspondent, et la valeur de « inversé » est fausse. Nous n'avons donc pas besoin d'effectuer d'opération.

.

• Enfin, il renvoie « cnt », qui a une valeur de 2.

#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of flips of prefixes required to convert the first binary string to the second
int minimumFlips(string first, string second, int N){

   // number of flips
   int cnt = 0;
   
   // to track whether the current bit is already flipped.
   // When we flip a bit 2 times, it becomes the same as the original bit.
   bool inverted = false;
   
   // Traverse the given string
   for (int i = N - 1; i >= 0; i--){
   
      // If A[i] is not equal to B[i]
      if (first[i] != second[i]){
      
         // If the current bit is not already flipped
         if (!inverted){
            cnt++; // Increase the count of flips
            inverted = true; // Invert all prefix bits
         }
      }
      else{
      
         // If A[i] is equal to B[i], but a current bit is flipped, we need to flip it again
         if (inverted){
         
            // Increase the count of flips
            cnt++;
            
            // Update inverted to false
            inverted = false;
         }
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Sortie

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Conclusion

Nous avons appris deux méthodes pour trouver le nombre minimum de retournements de préfixe requis pour convertir une chaîne en une autre. La logique est de parcourir la chaîne à partir de la fin et d'inverser le préfixe si nous trouvons un caractère qui ne correspond pas.

Nous avons optimisé le deuxième morceau de code en termes de complexité temporelle en utilisant une variable "inversée" pour garder une trace des préfixes inversés au lieu de les inverser comme dans la première approche.

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!