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

Video Face Swap

Video Face Swap

Échangez les visages dans n'importe quelle vidéo sans effort grâce à notre outil d'échange de visage AI entièrement gratuit !

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)

C Structure des données du langage: représentation des données et fonctionnement des arbres et des graphiques C Structure des données du langage: représentation des données et fonctionnement des arbres et des graphiques Apr 04, 2025 am 11:18 AM

C Structure des données du langage: La représentation des données de l'arborescence et du graphique est une structure de données hiérarchique composée de nœuds. Chaque nœud contient un élément de données et un pointeur vers ses nœuds enfants. L'arbre binaire est un type spécial d'arbre. Chaque nœud a au plus deux nœuds enfants. Les données représentent StrustReenode {intdata; structTreenode * gauche; structureReode * droite;}; L'opération crée une arborescence d'arborescence arborescence (prédécision, ordre dans l'ordre et ordre ultérieur) Le nœud d'insertion de l'arborescence des arbres de recherche de nœud Graph est une collection de structures de données, où les éléments sont des sommets, et ils peuvent être connectés ensemble via des bords avec des données droites ou peu nombreuses représentant des voisins.

La vérité derrière le problème de fonctionnement du fichier de langue C La vérité derrière le problème de fonctionnement du fichier de langue C Apr 04, 2025 am 11:24 AM

La vérité sur les problèmes de fonctionnement des fichiers: l'ouverture des fichiers a échoué: les autorisations insuffisantes, les mauvais chemins de mauvais et les fichiers occupés. L'écriture de données a échoué: le tampon est plein, le fichier n'est pas écrivatif et l'espace disque est insuffisant. Autres FAQ: traversée de fichiers lents, encodage de fichiers texte incorrect et erreurs de lecture de fichiers binaires.

Quelles sont les exigences de base pour les fonctions de langue C Quelles sont les exigences de base pour les fonctions de langue C Apr 03, 2025 pm 10:06 PM

Les fonctions de langue C sont la base de la modularisation du code et de la construction de programmes. Ils se composent de déclarations (en-têtes de fonction) et de définitions (corps de fonction). Le langage C utilise des valeurs pour transmettre les paramètres par défaut, mais les variables externes peuvent également être modifiées à l'aide d'adresse Pass. Les fonctions peuvent avoir ou ne pas avoir de valeur de retour et le type de valeur de retour doit être cohérent avec la déclaration. La dénomination de la fonction doit être claire et facile à comprendre, en utilisant un chameau ou une nomenclature de soulignement. Suivez le principe de responsabilité unique et gardez la simplicité de la fonction pour améliorer la maintenabilité et la lisibilité.

Comment calculer C-SUBScript 3 Indice 5 C-SUBScript 3 Indice Indice 5 Tutoriel d'algorithme Comment calculer C-SUBScript 3 Indice 5 C-SUBScript 3 Indice Indice 5 Tutoriel d'algorithme Apr 03, 2025 pm 10:33 PM

Le calcul de C35 est essentiellement des mathématiques combinatoires, représentant le nombre de combinaisons sélectionnées parmi 3 des 5 éléments. La formule de calcul est C53 = 5! / (3! * 2!), Qui peut être directement calculé par des boucles pour améliorer l'efficacité et éviter le débordement. De plus, la compréhension de la nature des combinaisons et la maîtrise des méthodes de calcul efficaces est cruciale pour résoudre de nombreux problèmes dans les domaines des statistiques de probabilité, de la cryptographie, de la conception d'algorithmes, etc.

Définition du nom de la fonction dans le langage C Définition du nom de la fonction dans le langage C Apr 03, 2025 pm 10:03 PM

La définition du nom de fonction du langage C comprend: Type de valeur de retour, nom de fonction, liste de paramètres et corps de fonction. Les noms de fonction doivent être clairs, concis et unifiés dans le style pour éviter les conflits avec les mots clés. Les noms de fonction ont des lunettes et peuvent être utilisés après la déclaration. Les pointeurs de fonction permettent de passer des fonctions ou d'attribuer des arguments. Les erreurs communes incluent les conflits de dénomination, l'inadéquation des types de paramètres et les fonctions non déclarées. L'optimisation des performances se concentre sur la conception et la mise en œuvre des fonctions, tandis que le code clair et facile à lire est crucial.

C Programmation multithread du langage: Guide du débutant et dépannage C Programmation multithread du langage: Guide du débutant et dépannage Apr 04, 2025 am 10:15 AM

C Guide de programmation multithreading Language: Création de threads: Utilisez la fonction PTHREAD_CREATE () pour spécifier l'ID de thread, les propriétés et les fonctions de thread. Synchronisation des threads: empêchez la concurrence des données via des mutex, des sémaphores et des variables conditionnelles. Cas pratique: utilisez le multi-lancement pour calculer le numéro Fibonacci, attribuer des tâches à plusieurs threads et synchroniser les résultats. Dépannage: résoudre des problèmes tels que les accidents de programme, les réponses d'arrêt de fil et les goulots d'étranglement des performances.

Concept de fonction de langue C Concept de fonction de langue C Apr 03, 2025 pm 10:09 PM

Les fonctions de langue C sont des blocs de code réutilisables. Ils reçoivent des entrées, effectuent des opérations et renvoient les résultats, ce qui améliore modulairement la réutilisabilité et réduit la complexité. Le mécanisme interne de la fonction comprend le passage des paramètres, l'exécution de la fonction et les valeurs de retour. L'ensemble du processus implique une optimisation telle que la fonction en ligne. Une bonne fonction est écrite en suivant le principe de responsabilité unique, un petit nombre de paramètres, des spécifications de dénomination et une gestion des erreurs. Les pointeurs combinés avec des fonctions peuvent atteindre des fonctions plus puissantes, telles que la modification des valeurs de variables externes. Les pointeurs de fonctions passent les fonctions comme des paramètres ou des adresses de magasin, et sont utilisées pour implémenter les appels dynamiques aux fonctions. Comprendre les fonctionnalités et les techniques des fonctions est la clé pour écrire des programmes C efficaces, maintenables et faciles à comprendre.

Comment produire un compte à rebours dans le langage C Comment produire un compte à rebours dans le langage C Apr 04, 2025 am 08:54 AM

Comment produire un compte à rebours en C? Réponse: Utilisez des instructions de boucle. Étapes: 1. Définissez la variable N et stockez le numéro de compte à rebours à la sortie; 2. Utilisez la boucle while pour imprimer en continu n jusqu'à ce que n soit inférieur à 1; 3. Dans le corps de la boucle, imprimez la valeur de n; 4. À la fin de la boucle, soustrayez N par 1 pour sortir le prochain plus petit réciproque.

See all articles