Table des matières
Énoncé du problème
Solution C++
Exemple
Sortie
Description du cas de test
Conclusion
Maison développement back-end C++ 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

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

Sep 03, 2023 pm 08:25 PM
Réduire la suppression Maximiser la sous-chaîne continue continu le plus long

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;
}
Copier après la connexion

Sortie

The maximum length of the substring of 1s is: 5
Copier après la connexion

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!

Déclaration de ce site Web
Le contenu de cet article est volontairement contribué par les internautes et les droits d'auteur appartiennent à l'auteur original. Ce site n'assume aucune responsabilité légale correspondante. Si vous trouvez un contenu suspecté de plagiat ou de contrefaçon, veuillez contacter admin@php.cn

Outils d'IA chauds

Undresser.AI Undress

Undresser.AI Undress

Application basée sur l'IA pour créer des photos de nu réalistes

AI Clothes Remover

AI Clothes Remover

Outil d'IA en ligne pour supprimer les vêtements des photos.

Undress AI Tool

Undress AI Tool

Images de déshabillage gratuites

Clothoff.io

Clothoff.io

Dissolvant de vêtements AI

AI Hentai Generator

AI Hentai Generator

Générez AI Hentai gratuitement.

Article chaud

R.E.P.O. Crystals d'énergie expliqués et ce qu'ils font (cristal jaune)
2 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Repo: Comment relancer ses coéquipiers
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: Comment obtenir des graines géantes
4 Il y a quelques semaines By 尊渡假赌尊渡假赌尊渡假赌
Combien de temps faut-il pour battre Split Fiction?
3 Il y a quelques semaines By DDD

Outils chauds

Bloc-notes++7.3.1

Bloc-notes++7.3.1

Éditeur de code facile à utiliser et gratuit

SublimeText3 version chinoise

SublimeText3 version chinoise

Version chinoise, très simple à utiliser

Envoyer Studio 13.0.1

Envoyer Studio 13.0.1

Puissant environnement de développement intégré PHP

Dreamweaver CS6

Dreamweaver CS6

Outils de développement Web visuel

SublimeText3 version Mac

SublimeText3 version Mac

Logiciel d'édition de code au niveau de Dieu (SublimeText3)

Quels sont les types de valeurs renvoyées par les fonctions du langage C? Qu'est-ce qui détermine la valeur de retour? Quels sont les types de valeurs renvoyées par les fonctions du langage C? Qu'est-ce qui détermine la valeur de retour? Mar 03, 2025 pm 05:52 PM

Cet article détaille les types de retour de la fonction C, englobant de base (int, float, char, etc.), dérivé (tableaux, pointeurs, structures) et types de vide. Le compilateur détermine le type de retour via la déclaration de fonction et l'instruction de retour, appliquant

Gulc: Cibliothèque C construite à partir de zéro Gulc: Cibliothèque C construite à partir de zéro Mar 03, 2025 pm 05:46 PM

Gulc est une bibliothèque C haute performance priorisant les frais généraux minimaux, l'inclinaison agressive et l'optimisation du compilateur. Idéal pour les applications critiques de performance comme le trading à haute fréquence et les systèmes intégrés, sa conception met l'accent sur la simplicité, le module

Quelles sont les définitions et les règles d'appel des fonctions du langage C et quelles sont les Quelles sont les définitions et les règles d'appel des fonctions du langage C et quelles sont les Mar 03, 2025 pm 05:53 PM

Cet article explique la déclaration de la fonction C par rapport à la définition, l'argument passant (par valeur et par pointeur), les valeurs de retour et les pièges communs comme les fuites de mémoire et les décalages de type. Il souligne l'importance des déclarations de modularité et de provi

C Fonction Langue Format de lettre ÉTAPES DE CONVERSION DE CAS C Fonction Langue Format de lettre ÉTAPES DE CONVERSION DE CAS Mar 03, 2025 pm 05:53 PM

Cet article détaille les fonctions C pour la conversion de cas de chaîne. Il explique l'utilisation de Toupper () et Tolower () de Ctype.h, itérant à travers les cordes et manipulant des terminateurs nuls. Les pièges communs comme oublier Ctype.h et modifier les littéraux de chaîne sont

Où est la valeur de retour de la fonction de langue C stockée en mémoire? Où est la valeur de retour de la fonction de langue C stockée en mémoire? Mar 03, 2025 pm 05:51 PM

Cet article examine le stockage de valeur de retour de la fonction C. De petites valeurs de retour sont généralement stockées dans les registres pour la vitesse; Des valeurs plus importantes peuvent utiliser des pointeurs vers la mémoire (pile ou tas), impactant la durée de vie et nécessitant une gestion manuelle de la mémoire. ACC directement

Utilisation distincte et partage de phrases Utilisation distincte et partage de phrases Mar 03, 2025 pm 05:51 PM

Cet article analyse les utilisations à multiples facettes de l'adjectif "distinct" "explorant ses fonctions grammaticales, des phrases communes (par exemple," distinctes de "" "distinctement différentes") et une application nuancée en formelle vs informelle informelle

Comment utiliser efficacement les algorithmes du STL (trier, trouver, transformer, etc.)? Comment utiliser efficacement les algorithmes du STL (trier, trouver, transformer, etc.)? Mar 12, 2025 pm 04:52 PM

Cet article détaille l'utilisation efficace de l'algorithme STL en c. Il met l'accent sur le choix de la structure des données (vecteurs vs listes), l'analyse de la complexité des algorithmes (par exemple, STD :: Srieur vs std :: partial_sort), l'utilisation des itérateurs et l'exécution parallèle. Pièges communs comme

Comment fonctionne la bibliothèque de modèle standard C (STL)? Comment fonctionne la bibliothèque de modèle standard C (STL)? Mar 12, 2025 pm 04:50 PM

Cet article explique la bibliothèque de modèles standard C (STL), en se concentrant sur ses composants principaux: conteneurs, itérateurs, algorithmes et fonctors. Il détaille comment ces interagissent pour permettre la programmation générique, l'amélioration de l'efficacité du code et de la lisibilité

See all articles