Maximiser le nombre de caractères minoritaires pouvant être supprimés d'une sous-chaîne de chaîne binaire donnée, implémenté en C++

Notre objectif actuel consiste à maximiser le nombre par lequel nous pouvons supprimer toutes les occurrences contenant le ou les caractères minoritaires dans une section entièrement composée de « 0 » ou de « 1 ». L'objectif final est simplement d'atteindre le maximum de suppressions possibles. tout en respectant toutes les règles et contraintes données.

Syntaxe

Pour assurer une compréhension globale des codes à venir, familiarisons-nous d'abord avec la syntaxe de la méthode qui sera utilisée avant d'explorer l'algorithme et les stratégies −

int maximizeDeletions(string binaryString, int startIndex, int endIndex)

Algorithme

L'algorithme qui maximise la suppression de quelques caractères dans une sous-chaîne de chaîne binaire donnée peut être décrit par les étapes suivantes :

• Tout d’abord, commençons par initialiser une variable appelée suppressions à zéro. L'objectif principal de cette variable est de surveiller le nombre d'opérations de suppression effectuées.

• Déterminez la fréquence à laquelle les chiffres « 0 » et « 1 » apparaissent dans une sous-chaîne spécifique d'une chaîne binaire. Chaque occurrence de ces nombres peut être calculée séparément.

• Pour identifier le(s) personnage(s) minoritaire(s), il faut se référer aux décomptes obtenus à l'étape précédente.

• Supprimez tous les caractères avec moins d'occurrences de la sous-chaîne et mettez à jour le nombre de suppressions en conséquence.

• Renvoyer la valeur finale supprimée comme résultat

Méthode 1 : Méthode traversante

L'exécution de notre approche consiste à parcourir la sous-chaîne de chaînes binaires de manière linéaire, puis à supprimer le(s) caractère(s) minoritaire(s) d'un seul coup.

La traduction chinoise de

Exemple

est :

Exemple

#include <iostream>
#include <algorithm>
using namespace std;

int maximizeDeletionsLinear(string binaryString, int startIndex, int endIndex) {
   int countZero = 0;
   int countOne = 0;

   for (int i = startIndex; i <= endIndex; i++) {
      if (binaryString[i] == '0') {
         countZero++;
      } else {
         countOne++;
      }
   }

   int deletions = endIndex - startIndex + 1 - min(countZero, countOne);
   return deletions;
}

int main() {
   string binaryString;
   int startIndex, endIndex;

   cout << "Enter the binary string: ";
   cin >> binaryString;
   cout << "Enter the start index: ";
   cin >> startIndex;
   cout << "Enter the end index: ";
   cin >> endIndex;

   int deletions = maximizeDeletionsLinear(binaryString, startIndex, endIndex);
   cout << "Maximum deletions: " << deletions << endl;
   
   return 0;
}

Sortie

Enter the binary string: 1011010011
Enter the start index: 2
Enter the end index: 8
Maximum deletions: 2

Explication

Dans la méthode 1, nous utilisons le parcours linéaire pour maximiser le nombre de quelques caractères supprimés d'une sous-chaîne de chaîne binaire donnée. En parcourant la sous-chaîne spécifiée, nous pouvons déterminer le nombre d'occurrences de « 0 » et « 1 » pour chaque instance de cette section. Après avoir identifié les caractères les moins fréquents dans cette région ou ce groupe (c'est-à-dire avoir trouvé la « minorité »), nous pouvons calculer le nombre de suppressions possibles en soustrayant leurs comptes respectifs du nombre de tous les caractères dans cette région spécifiée.

Cela conduit à une méthode efficace qui révèle une solution simple mais pratique - ne nécessitant qu'un seul passage sur notre chaîne initiale - ce qui rend cette méthode particulièrement adaptée aux chaînes d'entrée plus courtes.

Méthode 2 : Fenêtre coulissante

La technique de la fenêtre coulissante est une autre approche efficace pour résoudre ce problème. Elle consiste à utiliser une fenêtre de taille fixe pour parcourir la sous-chaîne de la chaîne binaire

. La traduction chinoise de

Exemple

est :

Exemple

#include <iostream>
#include <algorithm>
using namespace std;

int maximizeDeletionsSlidingWindow(string binaryString, int startIndex, int endIndex) {
   int left = startIndex;
   int right = startIndex;
   int countZero = 0;
   int countOne = 0;
   int deletions = 0;

   while (right <= endIndex) {
      if (binaryString[right] == '0') {
         countZero++;
      } else {
         countOne++;
      }

      while (min(countZero, countOne) > 0) {
         if (binaryString[left] == '0') {
            countZero--;
         } else {
            countOne--;
         }
         left++;
      }

      deletions = max(deletions, right - left + 1);
      right++;
   }

   return deletions;
}

int main() {
   string binaryString;
   int startIndex, endIndex;

   cout << "Enter the binary string: ";
   cin >> binaryString;
   cout << "Enter the start index: ";
   cin >> startIndex;
   cout << "Enter the end index: ";
   cin >> endIndex;

   int deletions = maximizeDeletionsSlidingWindow(binaryString, startIndex, endIndex);
   cout << "Maximum deletions: " << deletions << endl;

   return 0;
}

Sortie

Enter the binary string: Enter the start index: Enter the end index: Maximum deletions: 0

Explication

La méthode 2 consiste à utiliser des techniques de fenêtre coulissante pour maximiser la suppression d'un petit nombre de caractères. En utilisant une fenêtre de taille fixe, nous parcourons la sous-chaîne, mettant à jour le nombre de « 0 » et de « 1 » à mesure que la fenêtre se déplace. En ajustant les limites de la fenêtre en fonction du nombre, nous identifions un petit nombre de caractères et calculons le nombre maximum de suppressions possibles. Cette approche réduit le nombre de calculs redondants en faisant glisser efficacement la fenêtre, la rendant plus adaptée aux entrées plus volumineuses et fournissant des solutions plus rapides.

Conclusion

Dans cet article, nous explorons le problème de savoir comment maximiser la suppression d'un petit nombre de caractères d'une sous-chaîne de chaîne binaire donnée. Nous avons discuté de deux approches : la technique du parcours linéaire et de la fenêtre glissante. Les deux méthodes fournissent des solutions efficaces pour obtenir les résultats souhaités. En comprenant les algorithmes et en étudiant les exemples de code exécutable fournis, vous pouvez appliquer ces concepts pour résoudre des problèmes similaires dans vos propres projets. N'oubliez pas d'analyser le problème, de choisir l'approche la plus appropriée et de la mettre en œuvre en conséquence.

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!