Traduisez ce qui suit en chinois : minimisez le nombre de fois où des caractères identiques non adjacents sont supprimés afin que la chaîne donnée devienne une chaîne vide.

Dans cet article, nous allons approfondir un problème fascinant de manipulation de chaînes en C++. L'énoncé du problème est "Réduire au minimum la suppression des caractères non adjacents pour rendre la chaîne donnée vide". Cette question est un excellent moyen d'améliorer votre compréhension des chaînes, de la suppression de caractères et de la pensée algorithmique.

Énoncé du problème

Étant donné une chaîne, la tâche consiste à minimiser le nombre d'opérations de suppression de caractères adjacents non égaux nécessaires pour rendre la chaîne donnée vide. En une seule opération, vous pouvez supprimer deux caractères adjacents qui ne sont pas égaux.

Approche de solution C++

La solution à ce problème consiste à utiliser une structure de données de pile. Nous parcourons les caractères de la chaîne et pour chaque caractère, si la pile n'est pas vide et que le caractère supérieur de la pile n'est pas égal au caractère actuel, nous retirons le caractère supérieur de la pile. Sinon, poussez le caractère actuel sur la pile. Le nombre d'opérations requises est le nombre de caractères restant sur la pile finale.

Exemple

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int minimizeRemovals(string str) {
   stack<char> s;
   for (char c : str) {
      if (!s.empty() && s.top() != c) {
         s.pop();
      } else {
         s.push(c);
      }
   }
   return s.size();
}

int main() {
   string str = "abba";
   int operations = minimizeRemovals(str);
   cout << "The minimum number of removal operations is: " << operations << endl;
   return 0;
}

Sortie

The minimum number of removal operations is: 0

Explication avec un cas de test

Lorsque nous transmettons cette chaîne à la fonction minimiseRemovals, elle parcourt les caractères de la chaîne. Le processus est le suivant −

• Il pousse « a » sur la pile.

• Ensuite, il pousse « b » sur la pile car « b » n'est pas égal à l'élément en haut de la pile (« a »).

• Lorsque le « b » suivant est rencontré, il voit que le haut de la pile est également « b », il n'effectue donc pas d'opération de suppression et « b » est poussé sur la pile.

• Maintenant, le haut de la pile est « b » et le caractère suivant est « a ». Puisque « a » n'est pas égal à « b », il effectue une opération de suppression en faisant apparaître le haut de la pile. de la pile est 'b'.

• Enfin, le caractère 'a' qui n'est pas égal à l'élément supérieur de la pile ('b') est rencontré dans la chaîne. Par conséquent, il effectue une opération de suppression et fait apparaître l’élément supérieur de la pile.

À la fin de la fonction, il ne reste plus de caractères dans la pile, ce qui indique que tous les caractères adjacents non égaux ont été supprimés de la chaîne. Par conséquent, la fonction renvoie 0, qui est le nombre minimum d'opérations de suppression requises pour effectuer. la chaîne donnée vide.

Conclusion

Cette question offre une excellente opportunité d'utiliser les structures de données de pile pour les opérations sur les chaînes. C'est une excellente question pour mettre en pratique vos compétences en codage C++ et comprendre comment utiliser la pile pour résoudre des problèmes.

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!