Konvertiert die angegebene Binärzeichenfolge in eine andere Binärzeichenfolge, wobei bei minimalen Operanden alle Bits außer einem umgedreht werden

In diesem Problem müssen wir eine Binärzeichenfolge in eine andere Binärzeichenfolge umwandeln, indem wir die Zeichen der Zeichenfolge umdrehen. Wir können alle gesetzten Bits speichern und andere Bits umdrehen und müssen auf diese Weise die Gesamtzahl der Operationen berechnen, um eine weitere Zeichenfolge zu implementieren.

Wir können das Problem basierend auf der Gesamtzahl der Paare „01“ und „10“ in der angegebenen Zeichenfolge lösen.

Problemstellung- Wir erhalten zwei Zeichenfolgen gleicher Länge mit den Namen str1 und str2, die die Zeichen „0“ und „1“ enthalten und binäre Zeichenfolgen darstellen. Wir müssen die Zeichenfolge str1 in str2 konvertieren, indem wir Folgendes tun.

• Wir können jedes gesetzte Bit auswählen und alle anderen Bits umdrehen. Bits umdrehen bedeutet, „0“ in „1“ und „1“ in „0“ umzuwandeln.

• Wenn str1 nicht in str2 konvertiert werden kann, geben Sie -1 aus.

Beispiel

Eintreten

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

Ausgabe

3

Erklärung−

• In der ersten Operation behalten wir die „1“ des zweiten Index unverändert bei und spiegeln alle anderen Zeichen in str1 um. Daher ist str1 111110000.

• In der zweiten Operation behalten wir die „1“ am 0. Index unverändert bei und kehren alle anderen Zeichen um. Daher ist str1 100001111.

• Im letzten Vorgang speichern wir „1“ beim 5. Index. Daher wird str1 zu 011111000.

Eintreten

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

Ausgabe

-1

Erklärung – Str1 kann nicht in str2 konvertiert werden, da str1 kein „1“-Zeichen zum Speichern enthält.

Eintreten

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

Ausgabe

-1

Erklärung – Str1 kann nicht in str2 konvertiert werden.

Methode 1

Wir können Probleme durch Beobachtung lösen. Die Beobachtung ist, dass wir dieselbe Zeichenfolge erhalten, wenn wir ein einzelnes gesetztes Bit halten und zwei Operationen ausführen. Daher müssen wir einen anderen Index 1 wählen, um Änderungen an der Zeichenfolge vorzunehmen.

Außerdem müssen wir zwei Operationen durchführen, um das Paar 01 in 10 umzuwandeln. Belassen Sie beispielsweise „1“ in „01“. Wir erhalten also „11“. Behalten Sie danach „1“ am 0. Index in „11“ bei, sodass wir „10“ erhalten.

Um die Antwort zu erhalten, sollten 01 (0 -> str1, 1 -> str2) und 10 (1 -> str1, 0 -> str2) gleich sein. Andernfalls können wir sagen, dass die Antwort nicht existiert.

Unser Hauptziel ist es, die Paare „01“ und „10“ zu minimieren, da wir „01“ in 2 Vorgängen in „10“ umwandeln können.

Algorithmus

Schritt 1 – Definieren Sie die Funktion totalOperatrions(), um die Anzahl der Operationen zu berechnen, die zum Konvertieren von str1 in str2 erforderlich sind.

Schritt 1.2 - Initialisieren Sie die Variablen count10 und count01, um die Paare „01“ und „10“ in einer Zeichenfolge zu speichern.

Schritt 1.3 - Durchlaufen Sie die Saiten und zählen Sie Paare von 01 und 10 in beiden Saiten.

Schritt 1.4− Wenn count10 und count01 gleich sind, geben Sie 2*count10 zurück. Andernfalls wird -1 zurückgegeben.

Schritt 2 – Definieren Sie die Funktion „minimumOperations()“, um die minimalen Operationen zu berechnen, die zum Konvertieren von str1 in str2 erforderlich sind.

Schritt 3 – Initialisieren Sie „ans“ mit dem Maximalwert.

Schritt 4- Rufen Sie die Funktion totalOperations() mit der Originalzeichenfolge auf und speichern Sie das Ergebnis in der Variablen „operation1“. Wenn der Rückgabewert ungleich -1 ist, wird der Mindestwert von ans und Operation 1 in ans gespeichert.

Schritt 5 – Jetzt ändern wir die Zeichenfolge, um die Paare von 01 und 10 zu minimieren. Definieren Sie daher die Funktion stringModification().

Schritt 5.1 - In der Funktion finden wir das erste Paar von „1ch“ im String und übergeben „ch“ als Parameter, der „0“ oder „1“ sein kann. Das Paar sollte also wie folgt aussehen: 1 -> str1 und ch -> str.

Schritt 5.2- Geben Sie false zurück, wenn kein „1ch“-Paar gefunden wird.

Schritt 5.3 − Wenn ein „1ch“-Paar gefunden wird, lassen Sie das Paar unverändert und tauschen Sie die anderen Zeichen von str1 aus.

Schritt 6 – Führen Sie die stringModification-Funktion aus, um das „11“-Paar unverändert zu lassen und die anderen Zeichen umzudrehen. Danach wird die Funktion totalOperations() erneut aufgerufen, um die Operationen zu finden, die zum Konvertieren von str1 in str2 erforderlich sind.

Schritt 7− Wenn Operation 2 nicht gleich -1 ist, speichern Sie den Mindestwert in „ans“ oder „1 + Operation 2“ in „ans“. Hier haben wir 1 hinzugefügt, weil wir die Zeichenfolge mit einer Operation geändert haben.

Schritt 8 – Ändern Sie die Zeichenfolge, indem Sie das erste „10“-Paar unverändert lassen, und berechnen Sie die Operanden. Weisen Sie „ans“ erneut den Mindestwert zu.

Schritt 9− Wenn „ans“ gleich INT_MAX ist, geben Sie −1 zurück. Andernfalls senden Sie eine Antwort zurück.

Beispiel

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

Ausgabe

Minimum number of operations required are: 3

Zeitkomplexität− O(N), weil wir in den Funktionen stringModification() und totalOperations() über den String iterieren.

Raumkomplexität− O(1), da wir dieselbe Zeichenfolge ändern, ohne zusätzlichen Raum zu verbrauchen.

Im Code besteht unser Hauptzweck darin, die Anzahl der 01- und 10-Paare in der angegebenen Zeichenfolge zu reduzieren, nachdem wir die Zeichenfolge geändert haben, um Vorgänge zu minimieren. Programmierer können verschiedene Eingaben nutzen und versuchen, die Antwort zu verstehen.

Das obige ist der detaillierte Inhalt vonKonvertiert die angegebene Binärzeichenfolge in eine andere Binärzeichenfolge, wobei bei minimalen Operanden alle Bits außer einem umgedreht werden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!