Convertit la chaîne binaire donnée en une autre chaîne binaire, avec un minimum d'opérandes retournant tous les bits sauf un

Dans ce problème, nous devons convertir une chaîne binaire en une autre chaîne binaire en retournant les caractères de la chaîne. Nous pouvons sauvegarder tous les bits définis et inverser d'autres bits, et nous devons calculer le total des opérations pour implémenter une autre chaîne en faisant cela.

Nous pouvons résoudre le problème en fonction du nombre total de paires « 01 » et « 10 » dans la chaîne donnée.

Énoncé du problème- On nous donne deux chaînes de même longueur, nommées str1 et str2, contenant les caractères "0" et "1", représentant des chaînes binaires. Nous devons convertir la chaîne str1 en str2 en procédant comme suit.

• Nous pouvons sélectionner n'importe quel bit défini et retourner tous les autres bits. Inverser les bits signifie convertir « 0 » en « 1 » et « 1 » en « 0 ».

• Si str1 ne peut pas être converti en str2, imprimez -1.

Exemple

Entrez

str1 = "001001111", str2 = "011111000";

Sortie

3

Explication−

• Dans la première opération, nous gardons le "1" du deuxième index inchangé et retournons tous les autres caractères dans str1. Par conséquent, str1 sera 111110000.

• Dans la deuxième opération, nous gardons le "1" au 0ème index inchangé et retournons tous les autres caractères. Par conséquent, str1 sera 100001111.

• Lors de la dernière opération, on sauvegarde "1" au 5ème indice. Par conséquent, str1 deviendra 011111000.

Entrez

 str1 = "0000", str2 = "1111";

Sortie

-1

Explication- Impossible de convertir str1 en str2 car str1 ne contient aucun caractère "1" à enregistrer.

Entrez

 str1 = "0111", str2 = "1000";

Sortie

-1

Explication- Impossible de convertir str1 en str2.

Méthode 1

Nous pouvons résoudre des problèmes en observant. L'observation est que lorsque nous maintenons un seul bit défini et effectuons 2 opérations, nous obtenons la même chaîne. Par conséquent, nous devons choisir un index 1 différent pour apporter des modifications à la chaîne.

De plus, nous devons effectuer 2 opérations pour convertir la paire 01 en 10. Par exemple, laissez "1" dans "01". Nous obtenons donc "11". Après cela, gardez "1" au 0ème index de "11" pour obtenir "10".

Pour obtenir la réponse, 01 (0 -> str1, 1 -> str2) et 10 (1 -> str1, 0 -> str2) devraient être identiques. Sinon, on peut dire que la réponse n'existe pas.

Notre objectif principal est de minimiser les paires "01" et "10", puisque nous pouvons convertir "01" en "10" en 2 opérations.

Algorithme

Étape 1- Définissez la fonction totalOperations() pour calculer le nombre d'opérations nécessaires pour convertir str1 en str2.

Étape 1.2 - Initialisez les variables count10 et count01 pour stocker les paires "01" et "10" dans une chaîne.

Étape 1.3 - Parcourez les chaînes et comptez les paires de 01 et 10 dans les deux chaînes.

Étape 1.4− Si count10 et count01 sont identiques, renvoyez 2*count10. Sinon, -1 est renvoyé.

Étape 2- Définissez la fonction minimumOperations() pour calculer les opérations minimales requises pour convertir str1 en str2.

Étape 3- Initialisez "ans" avec la valeur maximale.

Étape 4- Appelez la fonction totalOperations() en utilisant la chaîne d'origine et stockez le résultat dans la variable "opération1". Si la valeur de retour n'est pas égale à -1, la valeur minimale de ans et de l'opération 1 est stockée dans ans.

Étape 5- Maintenant, nous allons modifier la chaîne pour minimiser les paires de 01 et 10. Par conséquent, définissez la fonction stringModification().

Étape 5.1 - Dans la fonction, on trouve la première paire de "1ch" dans la chaîne et on passe "ch" comme paramètre, qui peut être "0" ou "1". La paire devrait donc ressembler à 1 -> str1 et ch -> str.

Étape 5.2- Renvoyez false si aucune paire "1ch" n'est trouvée.

Étape 5.3 − Si une paire "1ch" est trouvée, laissez la paire inchangée et retournez les autres caractères de str1.

Étape 6- Exécutez la fonction stringModification pour conserver la paire "11" inchangée et inverser les autres caractères. Après cela, la fonction totalOperations() est à nouveau appelée pour rechercher les opérations nécessaires pour convertir str1 en str2.

Étape 7− Si l'opération 2 n'est pas égale à -1, stockez la valeur minimale dans "ans" ou "1 + opération 2" dans "ans". Ici, nous avons ajouté 1 car nous avons modifié la chaîne en une seule opération.

Étape 8- Modifiez la chaîne en laissant la première paire "10" inchangée et calculez les opérandes. Attribuez à nouveau la valeur minimale à "ans".

Étape 9− Si « ans » est égal à INT_MAX, renvoyez −1. Sinon, retournez ans.

Exemple

#include <bits/stdc++.h>
using namespace std;

// counting 01 and 10 pairs
int totalOperations(string str1, string str2) {
    int len = str1.size();
    int count10 = 0, count01 = 0;
    for (int p = 0; p < len; p++) {
        // If characters at p index are not same
        if (str1[p] != str2[p]) {
            // Increase count01 if 0(str1)-1(str2), else count10 if 1(str1)-0(str2)
            if (str1[p] == '0')
                count01++;
            else
                count10++;
        }
    }
    // If we have euqal number of 01 and 10 pairs, we need 2 operations to flip one pair.
    if (count01 == count10)
        return 2 * count01;
    return -1;
}
bool StringModification(string &temp1, string &temp2, char ch) {
    int len = temp1.size();
    int index = -1;
    // Find the pair of 1c character. (1 -> temp1, c -> temp2)
    for (int p = 0; p < len; p++) {
        if (temp1[p] == '1' && temp2[p] == ch) {
            index = p;
            break;
        }
    }
    // return 0 if pair is not found
    if (index == -1)
        return false;
    // Flip other characters in both strings
    for (int p = 0; p < len; p++) {
        if (p != index) {
            if (temp1[p] == '1')
                temp1[p] = '0';
            else
                temp1[p] = '1';
        }
    }
    return true;
}
// finding minimum operations
int minimumOperations(string str1, string str2) {
    int ans = INT_MAX;
    // first case with initial strings
    int operation1 = totalOperations(str1, str2);
    if (operation1 != -1)
        ans = min(ans, operation1);
    string temp1 = str1, temp2 = str2;
    // Case 2, modification for 11 pair
    if (StringModification(temp1, temp2, '1')) {
        // get operations after modification
        int operation2 = totalOperations(temp1, temp2);
        // adding 1 to operation2 as we have done one modification initially
        if (operation2 != -1)
            ans = min(ans, 1 + operation2);
    }
    // Case 3 modification for 10 pair
    temp1 = str1, temp2 = str2;
    if (StringModification(temp1, temp2, '0')) {
        int operation3 = totalOperations(temp1, temp2);
        if (operation3 != -1)
            ans = min(ans, 1 + operation3);
    }
    if (ans == INT_MAX)
        return -1;
    else
        return ans;
}
int main() {
    string str1 = "001001111";
    string str2 = "011111000";
    int ans = minimumOperations(str1, str2);
    if (ans == -1){
        cout << "S1 to S2 conversion is not possible";
    }
    else{
        cout << "Minimum number of operations required are: " << ans << "\n";
    }
    return 0;
}

Sortie

Minimum number of operations required are: 3

Complexité temporelle− O(N) car nous parcourons la chaîne dans les fonctions stringModification() et totalOperations().

Complexité spatiale− O(1) puisque nous modifions la même chaîne sans utiliser d'espace supplémentaire.

Dans le code, notre objectif principal est de réduire le nombre de paires de 01 et 10 dans la chaîne donnée après avoir modifié la chaîne pour minimiser les opérations. Les programmeurs peuvent utiliser diverses entrées et essayer de comprendre les réponses.

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!