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.
Input – str = 0011
Output – 0
Nous avons besoin de 0 inversion car la chaîne est divisée en deux.
Input – str = 0011101000
Output – 2
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
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.
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.
É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.
#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; }
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!