Maison > développement back-end > C++ > le corps du texte

Séparez les 1 et les 0 d'une chaîne binaire en moitiés distinctes

王林
Libérer: 2023-08-27 16:45:04
avant
825 Les gens l'ont consulté

Séparez les 1 et les 0 dune chaîne binaire en moitiés distinctes

Dans ce tutoriel, nous devons diviser tous les 1 et 0 de la chaîne binaire donnée en deux moitiés. Ici, nous devons prendre une sous-chaîne de la chaîne donnée et l'inverser pour séparer les différentes parties de 0 et 1. En fin de compte, nous devons calculer le nombre total d’inversions requises pour que la sous-chaîne divise le 1 et le 0 en deux.

Énoncé du problème - On nous donne une chaîne binaire de longueur paire. Nous devons prendre n'importe quelle sous-chaîne de la chaîne donnée plusieurs fois et l'inverser pour la diviser en deux moitiés. Nous devons imprimer le nombre total d’inversions requises à la fin.

Exemple

Input –  str = 0011
Copier après la connexion
Output – 0
Copier après la connexion

Instructions

Nous avons besoin de 0 inversion car la chaîne est divisée en deux.

Input –  str = 0011101000
Copier après la connexion
Output – 2
Copier après la connexion
Copier après la connexion

Instructions

  • Tout d’abord, prenez la sous-chaîne de longueur 2 à partir du 5ème index et inversez-la. La chaîne résultante sera 0011110000.

  • Après cela, prenez une chaîne de longueur 6 depuis le début et inversez-la. La chaîne résultante sera 1111000000

Input –  str = 010101
Copier après la connexion
Output – 2
Copier après la connexion
Copier après la connexion

Instructions

  • Inversez une chaîne de longueur 2 à partir du premier index. La chaîne résultante sera 001101.

  • Maintenant, inversez la chaîne de longueur 3 à partir du deuxième index. La chaîne finale sera 000111.

Méthode 1

Cette méthode comptera le nombre total d’éléments adjacents distincts. Après cela, on peut dire que le nombre total d’inversions nécessaires est de / 2.

Comprenons-le en débogant un exemple d'entrée.

Input –  str = 00111010
Copier après la connexion

Ainsi, le nombre total d’éléments adjacents différents est de 4. Ici, str[1] != str[2], str[4] != str[5], str[5] != str[6] et str[6] != str[7].

Donc, la valeur de comptage est 4 et la réponse est count/2, qui est égale à 2.

Algorithme

  • Étape 1 - Initialisez la variable "cnt" à 0.

  • Étape 2 - Utilisez une boucle for et parcourez la chaîne.

  • Étape 3 - Dans la boucle for, si l'élément actuel n'est pas égal à l'élément précédent, augmentez la valeur de la variable 'cnt' de 1.

  • Étape 4 - Si la valeur de 'cnt' est un nombre impair, renvoyez (cnt -1) /2. Sinon, retournez cnt/2.

La traduction chinoise de

Exemple

est :

Exemple

#include <bits/stdc++.h>
using namespace std;
//  function to find the minimum number of reversals required to segregate 1s and 0s in a separate half
int minimumReversal(string str, int len){
   int cnt = 0; // initialize count with zero
   for (int i = 1; i < len; i++){
   
      // if the adjacent elements are not the same, then the increment count
      if (str[i] != str[i - 1]){
         cnt++;
      }
   }
   
   // For odd count
   if (cnt % 2 == 1){
      return (cnt - 1) / 2;
   }
   return cnt / 2; // For even count
}
int main(){
   string str = "00111010";
   int len = str.size();
   cout << "Minimum number of operations required is : " << minimumReversal(str, len);
   return 0;
}
Copier après la connexion

Sortie

Minimum number of operations required is : 2
Copier après la connexion

Complexité temporelle - O(N) puisque nous parcourons la chaîne.

Complexité spatiale - O(N) car nous utilisons un espace constant pour stocker le décompte.

Ici, nous avons utilisé une logique qui doit être inversée chaque fois que deux éléments adjacents différents sont trouvés. De plus, en une seule opération inverse, nous pouvons définir deux éléments, nous renvoyons donc count/2 comme valeur de résultat.

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!

Étiquettes associées:
source:tutorialspoint.com
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
Tutoriels populaires
Plus>
Derniers téléchargements
Plus>
effets Web
Code source du site Web
Matériel du site Web
Modèle frontal