Machen Sie binäre Zeichenfolgen gleich, indem Sie das zweite Bit wiederholt ersetzen

In diesem Problem müssen wir die Zeichenfolge bin1 in die Zeichenfolge bin2 konvertieren, indem wir das zweite Zeichen der Zeichenfolge bin1 durch den minimalen oder maximalen Wert zwischen dem ersten und zweiten Zeichen ersetzen und das erste Zeichen löschen.

Da wir das erste Zeichen entfernen müssen, müssen wir sicherstellen, dass die letzten len2 − 1 Zeichen in den beiden Zeichenfolgen gleich sind. Darüber hinaus müssen wir sicherstellen, dass wir das erste Zeichen der zweiten Zeichenfolge erhalten können, indem wir die angegebene Operation am Startzeichen der bin1-Zeichenfolge ausführen.

Problemstellung – Wir erhalten bin1- und bin2-Binärzeichenfolgen mit der Länge len1 bzw. len2. Wir müssen prüfen, ob wir die Zeichenfolge „bin1“ in die Zeichenfolge „bin2“ konvertieren können, indem wir den folgenden Vorgang ausführen.

• Aktualisieren Sie das zweite Zeichen der bin1-Zeichenfolge mit dem Mindest- oder Maximalwert des ersten und zweiten Zeichens der bin1-Zeichenfolge.

• Entfernen Sie das erste Zeichen der bin1-Zeichenfolge und die Zeichenfolgengröße wird jedes Mal um 1 reduziert.

Beispiel

Eintreten

bin1 = "0101011"; bin2 = "011";

Ausgabe

Yes

Anleitung – Wir können Folgendes tun, um die Zeichenfolge „bin1“ in die Zeichenfolge „bin2“ zu konvertieren.

• Wir können das zweite Zeichen durch min(0,1) ersetzen und das erste Zeichen löschen. Daher wird die Zeichenfolge zu 001011.

• Wir führen den gleichen Vorgang noch einmal durch und die Zeichenfolge wird zu 01011.

• In den nächsten paar Operationen wird die Zeichenfolge zu 0011 bzw. 011.

Eintreten

bin1 = "1110"; bin2 = "1110";

Ausgabe

Yes

Erklärung – Die angegebenen Zeichenfolgen sind bereits gleich.

Eintreten

bin1 = "101101"; bin2 = "1110";

Ausgabe

No

Erläuterung – Wir können die Zeichenfolge „bin1“ nicht in die Zeichenfolge „bin2“ konvertieren, indem wir die angegebene Operation ausführen.

Methode 1

Wenn die Länge der Zeichenfolge „bin1“ kleiner ist, können wir sie nicht in die Zeichenfolge „bin2“ konvertieren.

In anderen Fällen bleiben die letzten len2 − 1 Zeichen der bin1-Zeichenfolge unverändert, da wir keine Operationen daran ausführen. Daher sollten die letzten len2 − 1 Zeichen in beiden Zeichenfolgen gleich sein.

Wenn das erste Zeichen der Zeichenfolge bin2 „0“ ist, sollten wir außerdem das Startzeichen der Zeichenfolge bin1 min() verwenden, und es sollte mindestens eine „0“ enthalten.

Wenn das erste Zeichen in der bin2-Zeichenfolge „1“ ist, sollten wir die max()-Operation für das Startzeichen der bin2-Zeichenfolge ausführen und es sollte mindestens eine „1“ enthalten.

Algorithmus

Schritt 1 - Wenn die Länge von bin1 kleiner als die Länge der Zeichenfolge bin2 ist, geben Sie „false“ zurück.

Schritt 2 – Durchqueren Sie die bin2-Zeichenfolge ab der zweiten Position.

Schritt 3 – Wenn bin2[p] nicht gleich bin1[p + len1 – len2] ist, geben Sie „false“ zurück, da die letzten len2 -1 Zeichen nicht gleich sind.

Schritt 4 – Durchlaufen Sie die ersten Zeichen len1 – len2 + 1 und prüfen Sie, ob sie bin2[0]-Zeichen enthalten. Wenn ja, geben Sie true zurück.

Schritt 5 – Geben Sie am Ende der Funktion false zurück.

Beispiel

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

bool convertAtoB(string bin1, string bin2) {
    int len1 = bin1.size(), len2 = bin2.size();
    // When length 1 is less than length 2
    if (len1 < len2) {
        return false;
    }
    // Check whether substring bin1[p + len1 - len2]... bin1[len1] and bin2[1]... bin2[len2]
    for (int p = 1; p < len2; p++) {
        if (bin1[p + len1 - len2] != bin2[p]) {
            return false;
        }
    }
    // Check whether substring bin1[0... len1 - len2 - 1] contains bin2[0]
    for (int p = 0; p < len1 - len2 + 1; p++) {
        if (bin1[p] == bin2[0]) {
            return true;
        }
    }
    return false;
}
int main() {
    string bin1 = "0101011";
    string bin2 = "011";
    bool res = convertAtoB(bin1, bin2);
    if (res == true) {
        cout << "YES, It is possible to convert bin1 to bin2.";
    } else {
        cout << "NO, It is not possible to convert bin1 to bin2.";
    }
}

Ausgabe

YES, It is possible to convert bin1 to bin2.

Zeitkomplexität – O(N), um Zeichenfolgenzeichen abzugleichen.

Raumkomplexität – O(1), da wir keinen dynamischen Raum verwenden.

Wir haben gelernt, die erste Binärzeichenfolge in die zweite Binärzeichenfolge umzuwandeln, indem wir der angegebenen Operation folgen. Ein Programmierer könnte versuchen zu prüfen, ob eine Zeichenfolge in eine andere konvertiert werden kann, indem er das letzte Zeichen durch den minimalen oder maximalen Wert des letzten und letzten zweiten Zeichens ersetzt und das letzte Zeichen entfernt.

Das obige ist der detaillierte Inhalt vonMachen Sie binäre Zeichenfolgen gleich, indem Sie das zweite Bit wiederholt ersetzen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!