Traduisez ce qui suit en chinois : Réduisez la suppression des sous-chaînes 0 pour supprimer toutes les occurrences de 0 d'une chaîne binaire en boucle.

Dans ce problème, nous devons supprimer tous les zéros de la chaîne binaire donnée. Dans le même temps, nous devons supprimer simultanément les paires de zéros consécutives et compter le nombre total de paires de zéros supprimées.

Nous pouvons résoudre le problème en comptant le nombre de paires de zéros consécutifs dans la chaîne donnée. Dans ce tutoriel, nous apprendrons deux solutions différentes pour résoudre le problème.

Énoncé du problème - On nous donne une chaîne binaire circulaire str de longueur N. Nous devons trouver le nombre minimum de zéros consécutifs requis pour supprimer tous les zéros de la chaîne.

Exemple Exemple

Input –  str = "0011001"

Output – 2

Explication

Nous pouvons supprimer str[0] et str[1] ensemble. Après cela, nous pouvons supprimer str[4] et str[5]. Nous devons donc supprimer 2 paires de zéros consécutifs.

Input –  str = ‘0000000’

Output – 1

Explication

Nous pouvons supprimer tous les zéros en même temps.

Input –  str = ‘00110010’

Output – 2

Explication

Nous supprimons can str[0], str[1] et str[7] ensemble car la chaîne binaire est circulaire. Ensuite, nous pouvons supprimer str[5] et str[6] ensemble.

Approche 1

Dans cette méthode, nous trouverons le nombre total de paires de zéros consécutives dans la chaîne donnée, qui répondra à la question posée.

Algorithme

• Étape 1 - Initialisez la variable 'cnt' à zéro.

• Étape 2 - Initialisez la variable 'isOne' à la valeur false pour garder une trace du chiffre 1 dans la chaîne donnée.

• Étape 3 - Parcourez la chaîne à l'aide d'une boucle. Dans la boucle, si le caractère actuel est '0', augmentez la valeur de 'cnt' de 1.

• Étape 4 - Utilisez une boucle while pour itérer jusqu'à ce que nous continuions à trouver le caractère suivant qui est « 0 » et augmentons la valeur de « I » de 1.

• Étape 5 - Si le caractère actuel est « 1 », changez la valeur de la variable « isOne » en vrai, indiquant que la chaîne contient au moins un « 1 ».

• Étape 6 - Une fois l'itération de la boucle terminée, si la valeur de 'isOne' est fausse, cela signifie que la chaîne ne contient que des zéros dans de tels cas.

.

• Étape 7 - Si le premier et le dernier caractères sont « 0 », diminuez la valeur du « cnt » de 1 car la chaîne est circulaire.

• Étape 8 − Renvoie la valeur de 'cnt'.

La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   bool isOne = false;
   
   // Iterate over the string
   for (int i = 0; i < N; i++){
   
      // If the current character is 0, increment the count of 0s
      if (str[i] == '0'){
         cnt++;
         
         // traverse the string until a 1 is found
         while (str[i] == '0'){
            i++;
         }
      }
      else{
      
         // If the current character is 1, then set isOne as true
         isOne = true;
      }
   }
   
   // If string contains only 0s, then return 1.
   if (!isOne)
      return 1;
      
   // If the first and last character is 0, then decrement the count, as the string is circular.
   if (str[0] == '0' && str[N - 1] == '0'){
      cnt--;
   }
   
   // return cnt
   return cnt;
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

Sortie

The total number of minimum substrings of consecutive zeros required to remove is - 2<font face="sans-serif"><span style="font-size: 16px; background-color: rgb(255, 255, 255);">.</span></font></p><p>

Complexité spatiale - O(1)

Méthode 2

Dans cette méthode, nous calculerons le nombre minimum de sous-chaînes de suppression de zéros requises pour supprimer tous les zéros en comptant les différences des éléments adjacents.

Algorithme

• Étape 1 - Définissez les variables « cnt » et « isOne » et initialisez-les avec 0 et false, respectivement.

• Étape 2 - Utilisez la boucle for pour effectuer N-1 itérations, où N est la longueur de la chaîne.

• Étape 3 - Dans la boucle, vérifiez si le caractère actuel est '0' et le caractère suivant est '1', augmentez la valeur de 'cnt' de 1. Sinon, changez la valeur de 'isOne'. variable à vrai.

• Étape 4 - Si le dernier caractère est « 0 » et que le premier caractère est « 1 », augmentez la valeur de « cnt » de 1.

• Étape 5 - Si la valeur de 'isOne' est fausse, renvoyez 1.

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

La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
int countRemovels(string str, int N){
   // to store the count of 0s
   int cnt = 0;
   
   // to check if there is at least one 1
   bool isOne = false;
   
   // traverse the string
   for (int i = 0; i < N - 1; i++) {
   
      // if the current character is 0, the next is 1, then increment count by 1
      if (str[i] == '0' && str[i + 1] == '1'){
         cnt++;
      }
      else{
      
         // if the current character is 1, then set isOne to true
         isOne = true;
      }
   }
   
   // for circular string, if the last character is 0 and the first is 1, then increment count by 1
   if (str[N - 1] == '0' && str[0] == '1'){
      cnt++;
   }
   
   // if there is no 1 in the string, then return 1
   if (!isOne){
      return 1;
   }
   return cnt; // return cnt
}
int main(){
   string str = "0011001";
   int N = str.size();
   cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N);
   return 0;
}

Sortie

The total number of minimum substrings of consecutive zeros required to remove is - 2

Conclusion

Nous avons vu deux solutions différentes pour résoudre le problème posé. Dans la première méthode, nous comptons le nombre total de paires de zéros consécutives, dans la seconde méthode, nous comptons le nombre total de caractères adjacents sans correspondance.

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!