Le nombre minimum de suppressions qui fait d'une chaîne une chaîne de 0 suivie d'une chaîne de 1

La question "Suppression minimale pour la concaténation de chaînes de 0 sous-chaînes" implique un travail sur la manipulation des chaînes. Étant donné en entrée une chaîne de 0 et de 1, le résultat est un entier reflétant le nombre minimum de 0 qui doivent être éliminés afin de générer une sous-chaîne de 0 consécutifs.

En d'autres termes, le problème peut être reformulé comme suit : étant donné une chaîne composée de 0 et de 1, combien de 0 doivent être éliminés pour que la chaîne restante contienne une période continue de 0.

Algorithme

Étape 1 : Initialisation des variables

• Définissez une variable de comptage pour enregistrer la longueur de la séquence zéro actuelle.

• Définissez une variable max_count pour garder une trace de la plus longue séquence de zéros rencontrée jusqu'à présent.

• Réglez les deux variables sur 0.

Étape 2 : Traversée de chaînes

Utilisez une boucle pour parcourir chaque caractère de la chaîne.

Troisième étape : zéro détection

Si le caractère actuel est zéro, incrémentez la variable count.

Étape 4 : Un test

• Si le caractère actuel est 1, comparez la variable count avec la variable max_count.

• Si la variable count est supérieure à la variable max_count, définissez la variable max_count égale à la variable count.

• Réinitialisez la variable de comptage à 0.

Étape 5 : Boucle terminée

Répétez ce processus jusqu'à ce que tous les caractères de la chaîne aient été traités.

Étape 6 : Calcul de la suppression minimale

Le nombre minimum de suppressions requises pour supprimer tous les zéros afin que les zéros restants ne soient séparés par aucun zéro peut être calculé en soustrayant max_count de la longueur de la chaîne.

Étape 7 : Sortie du résultat

Imprimez les résultats sur la console.

Méthode à suivre

• Méthodes dynamiques

• Méthode d'itération

Méthode 1 : Méthode dynamique

La programmation dynamique peut être utilisée pour résoudre ce problème efficacement. Pour créer une sous-chaîne de 0 consécutifs, nous pouvons créer un tableau dp[], où dp[i] représente le nombre minimum de 0 qui doivent être éliminés de la sous-chaîne s[0...i]. Le nombre minimum de 0 à éliminer d'une sous-chaîne vide est 0, nous pouvons donc initialiser dp[0] à 0.

Nous pouvons ensuite parcourir la chaîne s et mettre à jour dp[i] en −

• Si s[i] vaut "0", alors dp[i] = dp[i-1], car nous pouvons inclure s[i] dans une sous-chaîne de 0 consécutifs ou les supprimer.

• Lorsque s[i] vaut "1", nous devons obtenir l'index j le plus proche de i qui contient une sous-chaîne de 0 consécutifs. Cela peut être fait en itérant de i-1 à 0 et en voyant si la sous-chaîne s[ji...i] contient des 0 consécutifs. Si l'index j est trouvé, alors dp[i] = dp[j-1] + (i-j+1), où dp[j-1] représente le nombre minimum de 0 qui doivent être éliminés de la sous-chaîne s[. .j-1] et (i-j+1) sont le nombre total de 1 qui doivent être éliminés pour obtenir la sous-chaîne s[ji...i] de 0 consécutifs. Si aucun index j n'est trouvé, alors dp[i] = dp[i-1], puisque nous ne pouvons pas contenir s[i] dans une sous-chaîne de 0 consécutifs.

  Enfin, afin d'obtenir une sous-chaîne de 0 consécutifs, le nombre minimum de 0 qui doivent être supprimés de la chaîne entière s est donné par dp[n-1], où n est la longueur de la chaîne s.

Exemple 1

Le programme suivant utilise la méthode dont nous avons parlé ci-dessus, en lisant d'abord la chaîne d'entrée à partir de l'entrée standard, puis en identifiant toutes les sous-chaînes de 0. Calculez ensuite la longueur de la sous-chaîne 0 la plus longue et la longueur de la chaîne générée en concaténant chaque sous-chaîne 0. Pour déterminer le nombre minimum d'éliminations requises, il soustrait finalement la longueur de la sous-chaîne 0 la plus longue de la somme de toutes les sous-chaînes 0 et affiche le résultat sur la sortie standard.

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

int main() {
   string s = "100100011000110"; // constant input string

   vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s

   int start = -1;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         if (start == -1) {
         start = i;
         }
      } else {
         if (start != -1) {
         substrings.push_back(make_pair(start, i - 1));
         start = -1;
         }
      }
   }
   if (start != -1) {
      substrings.push_back(make_pair(start, s.length() - 1));
   }

   int totalLength = 0;
   for (auto& p : substrings) {
      totalLength += p.second - p.first + 1;
   }

   int maxLength = 0;
   for (auto& p : substrings) {
      int len = p.second - p.first + 1;
      if (len > maxLength) {
         maxLength = len;
      }
   }

   int removals = totalLength - maxLength;
   cout << "Input string: " << s << endl;
   cout << "Minimum removals: " << removals << endl;

   return 0;
}

Sortie

Input string: 100100011000110
Minimum removals: 6

Méthode 2 : Méthode itérative

Cette méthode utilise une méthode d'itération simple pour parcourir la chaîne donnée caractère par caractère tout en mettant à jour les valeurs des deux variables count et max_count. Cette méthode met à jour la valeur des variables count et max_count selon que le caractère actuel est 0 ou 1. Il fournit ensuite la différence entre max_count et la longueur de la sous-chaîne 0 la plus longue.

La traduction chinoise de

Exemple 2

est :

Exemple 2

Ce code est un logiciel C++ qui calcule le nombre minimum d'éliminations nécessaires pour supprimer tous les zéros d'une chaîne binaire afin que le reste ne soit séparé par aucun zéro. La fonction min_deletions prend une chaîne binaire en entrée et utilise une boucle pour parcourir chaque caractère de la chaîne. La boucle incrémente la variable de comptage chaque fois qu'elle rencontre zéro et la réinitialise à zéro lorsqu'elle en rencontre un. La valeur maximale de la variable count est enregistrée dans max_count, et enfin la longueur de la chaîne est soustraite de max_count pour obtenir le nombre minimum de suppressions requis. Les résultats sont ensuite affichés à l'utilisateur.

#include <iostream> 
#include <string> 
using namespace std; 
 
int min_deletions(string str) { 
   int count = 0, max_count = 0; 
   for (char c : str) { 
      if (c == '0') { 
         count++; 
      } else { 
         max_count = max(max_count, count); 
         count = 0; 
      } 
   } 
    return str.length() - max_count; 
} 
 
int main() { 
   string str = "100010011000110"; 
   int deletions = min_deletions(str); 
   cout << "Minimum deletions needed: " << deletions << endl; 
   return 0; 
} 

Sortie

Minimum deletion needed: 12 

Conclusion

Déterminer toutes les sous-chaînes de 0, calculer la longueur de la chaîne produite en concaténant chaque sous-chaîne de 0 et déterminer la longueur de la sous-chaîne la plus longue de 0 sont les trois étapes pour résoudre le problème donné. La longueur de la plus grande sous-chaîne 0 peut ensuite être soustraite de la somme de toutes les sous-chaînes 0 pour obtenir le nombre minimum de suppressions requis.

La méthode que nous utilisons pour obtenir la réponse est simple, efficace et fonctionne en temps linéaire, ce qui la rend adaptée aux entrées volumineuses. Mais cela peut être encore amélioré en appliquant des méthodes plus sophistiquées telles que la programmation dynamique.

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!