Séparez les 1 et les 0 d'une 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

Output – 0

Instructions

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

Input –  str = 0011101000

Output – 2

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

Output – 2

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

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;
}

Sortie

Minimum number of operations required is : 2

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!