Nombre minimum de mouvements requis pour placer tous les 0 avant les 1 dans une chaîne binaire

Énoncé du problème

On nous donne une chaîne binaire str et on nous demande de supprimer le nombre minimum de caractères de la chaîne afin que nous puissions mettre tous les zéros avant les uns.

Exemple

Entrez

str = ‘00110100111’

Sortie

3

Instructions

Ici, nous pouvons atteindre le résultat 3 de deux manières.

Nous pouvons supprimer arr[2], arr[3] et arr[5] ou arr[4], arr[6] et arr[7] de la chaîne.

Entrez

str = ‘001101011’

Sortie

2

Instructions

Nous pouvons supprimer arr[4] et arr[6] et mettre tous les zéros avant les uns.

Entrez

str = ‘000111’

Sortie

0

Instructions

Dans la chaîne donnée, tous les zéros ont été placés avant 1, nous n'avons donc pas besoin de supprimer aucun caractère de la chaîne donnée.

Méthode 1

Dans la première méthode, nous utiliserons deux tableaux. Le premier tableau stocke tous les 1 à gauche et l’autre tableau stocke tous les 0 à droite. Après cela, nous pouvons ajouter les éléments au i-ème index dans les deux tableaux et trouver la somme minimale.

Algorithme

• Étape 1 - Définissez une liste nommée de zéros et de uns de longueur n, où n est la longueur de la chaîne que nous pouvons obtenir en utilisant la méthode size().

• Étape 2 - Si le premier caractère de la chaîne donnée est "1", stockez 1 au 0ème index du tableau "ones" sinon, stockez 0.

• Étape 3 - Utilisez une boucle for pour parcourir à partir du deuxième élément de la chaîne. Dans la boucle for, Ones[i] est initialisé avec la valeur obtenue en ajoutant Ones[i-1] à 1 ou 0 en fonction du caractère de la chaîne à l'index i.

• Étape 4 - Stockez 1 ou 0 à Zeros[n-1] en fonction du dernier caractère de la chaîne donnée.

• Étape 5 - Utilisez une boucle for pour parcourir la chaîne à partir du caractère de la dernière seconde et mettre à jour la valeur de la liste zéro en fonction des caractères de la chaîne.

• Étape 6 - Définissez la variable "min_zeros_to_remove" et initialisez-la avec la valeur entière maximale.

• Étape 7 - Maintenant, parcourez les listes « zéro » et « un ». Accédez aux valeurs de l'index "i+1" dans la liste zéro et de l'index "I" dans la liste "un". Après cela, ajoutez ces deux éléments.

• Étape 8 - Si la valeur de "min_zeros_to_remove" est inférieure à la valeur actuelle de la variable "min_zeros_to_remove", modifiez sa valeur par la somme des deux éléments du tableau.

• Étape 9 - Renvoyez la valeur du résultat.

Exemple

#include <bits/stdc++.h>
using namespace std;

int minimumZeroRemoval(string str){
   int n = str.size();
   // arrays to store the prefix sums of zeros and ones
   vector<int> zeros(n);
   vector<int> ones(n);
   // compute total number of 1s at the left of each index
   ones[0] = (str[0] == '1') ? 1 : 0;
   for (int i = 1; i < n; i++) {
      ones[i] = ones[i - 1] + ((str[i] == '1') ? 1 : 0);
   }
   // compute total number of 0s at the right of each index
   zeros[n - 1] = (str[n - 1] == '0') ? 1 : 0;
   for (int i = n - 2; i >= 0; i--){
      zeros[i] = zeros[i + 1] + ((str[i] == '0') ? 1 : 0);
   }
   // do the sum of zeros and ones for each index and return the minimum value
   int min_zeros_to_remove = INT_MAX;
   for (int i = 0; i < n - 1; i++){
      min_zeros_to_remove = min(min_zeros_to_remove, zeros[i + 1] + ones[i]);
   }
   return min_zeros_to_remove;
}
int main() {
   string str = "00110100111";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Sortie

The minimum number of zeros required to remove from the given string is - 3

• Complexité temporelle - O(N) car nous avons besoin d'une boucle pour parcourir des chaînes et des listes de taille N.

• Space Complexity - O(N) car nous utilisons deux listes pour stocker les comptes de 1 et 0.

Méthode 2

Cette méthode est une version optimisée de la première méthode. Ici, au lieu d'une liste, nous utilisons deux variables pour stocker le nombre de 1 et de 0.

Algorithme

• Étape 1 - Définissez la variable "zeros_right" et initialisez-la à 0.

• Étape 2 - Parcourez la chaîne, comptez le nombre total de caractères "0" dans la chaîne donnée et mettez à jour la valeur de la variable "zero_right" en conséquence.

• Étape 3 - Définissez la variable "ones_left" et initialisez-la à 0.

• Étape 4 - Utilisez une boucle for pour parcourir la chaîne. Si le caractère à l'index i dans la chaîne est "1", augmentez la valeur de la variable "ones_left" de 1. Sinon, réduisez la valeur de la variable "zeros_right" de 1.

• Étape 5 - Si "zeros_right + Ones_left" est inférieur à la valeur actuelle de la variable "res", mettez à jour la valeur de la variable "res".

Exemple

#include <bits/stdc++.h>
using namespace std;

// function to remove zeros from the string to place all zeros before 1.
int minimumZeroRemoval(string str){
   // counting the total number of zeros in the given string
   int zeros_right = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] == '0')
      zeros_right += 1;
   }
   // variable to store the number of ones from left
   int ones_left = 0;
   // Size of the string
   int len = str.size();
   // variable to store the final result
   int result = INT_MAX;
   // Traverse the string from left to right
   for (int i = 0; i < len; i++){
      // If the current character is '1', then increment ones_left by 1 else, decrement zeros_right by 1
      if (str[i] == '1') {
         ones_left += 1;
      } else {
         zeros_right -= 1;
      }
      // Store the minimum result and zeros_right + ones_left in result
      result = min(result, zeros_right + ones_left);
   }
   // Return the final result
   return result;
}
int main() {
   string str = "001101011";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Sortie

The minimum number of zeros required to remove from the given string is - 2

• Time Complexity - O(N), lorsque nous parcourons la chaîne.

• Complexité spatiale - O(1) puisque nous n'utilisons que l'espace constant.

Conclusion

L'utilisateur a appris deux façons de supprimer le nombre minimum de caractères d'une chaîne binaire donnée. Le code de la deuxième approche est plus lisible car nous utilisons des variables pour stocker le nombre de zéros et de uns au lieu d'utiliser une liste.

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!