Minimisez le nombre de 0 qui doivent être supprimés pour maximiser la longueur de la sous-chaîne 1 consécutive la plus longue

Dans cet article, nous aborderons un problème intéressant impliquant les opérations sur les chaînes C++. Le problème que nous allons étudier aujourd'hui est de savoir comment "minimiser le nombre de 0 qui doivent être supprimés pour maximiser la longueur de la plus longue sous-chaîne continue de 1". Ce problème est un excellent moyen de perfectionner vos compétences en manipulation de chaînes et en programmation dynamique.

Énoncé du problème

Étant donné une chaîne binaire, la tâche consiste à minimiser le nombre de 0 qui doivent être supprimés afin de maximiser la longueur de la sous-chaîne 1 la plus longue.

Solution C++

Pour résoudre ce problème, nous pouvons utiliser la méthode de la fenêtre coulissante. Nous conserverons deux pointeurs, le pointeur gauche et le pointeur droit. Initialement, les deux pointeurs pointent vers le premier élément. Ensuite, nous continuerons à déplacer le pointeur droit vers la droite. Si un « 0 » est rencontré, nous incrémentons un compteur. Si le compteur devient supérieur au nombre autorisé de suppressions nulles, nous déplaçons le pointeur gauche vers la droite jusqu'à ce que nous rencontrions un « 0 » et décrémentons le compteur.

Nous conserverons également une variable maxLen pour stocker la longueur maximale de la sous-chaîne que nous avons vue jusqu'à présent.

Exemple

C'est le code C++ qui résout le problème -

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

int maxSubstring(string str, int k) {
   int zeroCount = 0;
   int left = 0;
   int maxLen = 0;
   
   for (int right = 0; right < str.size(); right++) {
      if (str[right] == '0') {
         zeroCount++;
      }
      while (zeroCount > k) {
         if (str[left] == '0') {
               zeroCount--;
         }
         left++;
      }
      maxLen = max(maxLen, right - left + 1);
   }
   return maxLen;
}

int main() {
   string str = "110100110";
   int k = 2; // number of zeros that can be removed
   int result = maxSubstring(str, k);
   cout << "The maximum length of the substring of 1s is: " << result << endl;
   return 0;
}

Sortie

The maximum length of the substring of 1s is: 5

Description du cas de test

Prenons la chaîne binaire "110100110", on peut supprimer 2 zéros.

Lorsque nous transmettons cette chaîne et la valeur de k à la fonction maxSubstring, elle commence l'analyse par la gauche. Chaque fois qu'il rencontre un « 0 », il incrémente zeroCount. Lorsque zeroCount dépasse k, il commence à déplacer le pointeur gauche vers la droite jusqu'à ce qu'il rencontre un « 0 » et décrémente zeroCount.

Dans ce processus, il met continuellement à jour maxLen, qui est la longueur maximale de sous-chaîne de 1 s. Pour la chaîne donnée, la longueur maximale de la sous-chaîne de 1 sans supprimer au plus 2 zéros est de 5, c'est-à-dire la sous-chaîne "11111" après avoir supprimé le deuxième et le troisième "0".

La fonction renverra donc 5.

Conclusion

Cette question montre comment utiliser efficacement la technologie des fenêtres coulissantes pour résoudre des problèmes complexes de manipulation de chaînes en C++. C'est une excellente question pour comprendre et pratiquer les techniques de programmation dynamique et de traitement de chaînes. Continuez à pratiquer des questions comme celles-ci pour améliorer vos compétences en codage C++.

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!