Mindestanzahl von Präfixwechseln, die erforderlich sind, um eine Binärzeichenfolge in eine andere umzuwandeln

In diesem Problem müssen wir die erste Binärzeichenfolge in die zweite Binärzeichenfolge umwandeln, indem wir ihr Präfix umdrehen. Um die minimale Anzahl an Präfixumdrehungen zu erhalten, müssen wir das Ende der Zeichenfolgen durchlaufen. Wenn in beiden Zeichenfolgen ein nicht übereinstimmendes Zeichen gefunden wird, müssen wir das Präfix der ersten Zeichenfolge umdrehen.

Problemstellung − Wir erhalten zwei verschiedene Binärzeichenfolgen mit den Namen „erste“ und „zweite“. Die beiden binären Zeichenfolgen haben die gleiche Länge N. Wir müssen die erste Zeichenfolge in die zweite Zeichenfolge umwandeln, indem wir ihr Präfix umdrehen. Hier müssen wir die Gesamtzahl der Präfixwechsel berechnen, die erforderlich sind, um eine Zeichenfolge in eine andere umzuwandeln. Umdrehen bedeutet, „0“ in „1“ und „1“ in „0“ umzuwandeln.

Beispiele

Input –  first = "001", second = "000"

Output – 2

Erklärung

• Zuerst müssen wir das Präfix der Länge 3 für die erste Zeichenfolge umdrehen, und die resultierende Zeichenfolge ist 110.

• Danach müssen wir das Präfix der Länge 2 umdrehen und die resultierende Zeichenfolge ist 000, gleich der zweiten Zeichenfolge.

Input –  first = "10", second = "01"

Output – 1

Erklärung

Wir müssen das Präfix der Länge 2 umdrehen und die resultierende Zeichenfolge ist „01“, was der zweiten Zeichenfolge entspricht.

Input –  first = "11", second = "11"

Output – 0

Erklärung

Da beide Saiten gleich sind, müssen wir nichts umdrehen.

Ansatz 1

Bei dieser Methode iterieren wir vom Ende der Zeichenfolge und wenn wir ein nicht übereinstimmendes Zeichen finden, spiegeln wir alle Zeichen im Präfix der Länge „I + 1“ um. Dies ist eine einfache Möglichkeit, das Problem zu lösen.

Algorithmus

• Schritt 1 – Variable „cnt“ definieren und auf 0 initialisieren.

• Schritt 2 − Beginnen Sie mit dem Durchqueren der Schnur vom Ende mithilfe der Schleife.

• Schritt 3 − Wenn erstes[i] und zweites[i] nicht gleich sind, müssen wir alle Zeichen des Präfixes umdrehen, dessen Länge gleich I + 1 ist.

• Schritt 4 - Verwenden Sie die Nest-for-Schleife, um das Präfix mit der Länge I + 1 zu durchlaufen und jedes Zeichen davon umzudrehen, indem Sie die Funktion flipBits() ausführen.

• Schritt 4.1 − Wir geben „0“ zurück, wenn das aktuelle Zeichen „1“ ist, und „1“, wenn das aktuelle Zeichen „0“ in der Funktion flipBits() ist.

• Schritt 5 - Erhöhen Sie den Wert der Variablen „cnt“ um 1, wenn wir das Präfix umdrehen.

• Schritt 6 – Geben Sie den Wert der Variablen „cnt“ zurück.

Beispiel

#include <bits/stdc++.h>
using namespace std;
char flipBits(char ch){
   // if the bit is '0', flip it to '1', else flip it to '0'.
   return (ch == '0') ? '1' : '0';
}
int minimumFlips(string first, string second, int n){
   // to store the count of flips
   int cnt = 0;
   
   // Traverse the string
   for (int i = n - 1; i >= 0; i--){
   
      // If first[i] is not equal to second[i]
      if (first[i] != second[i]){
      
         // flip the bits
         for (int j = 0; j <= i; j++){
            first[j] = flipBits(first[j]);
         }
         cnt++;
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Ausgabe

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Ansatz 2

Bei diesem Ansatz verwenden wir die „invertierte“ Variable, um zu verfolgen, ob das aktuelle Bit umgedreht wird oder nicht, anstatt jedes Mal jedes Präfixbit umzudrehen. Bei diesem Ansatz haben wir auch die zeitliche Komplexität des Codes optimiert.

Algorithmus

• Schritt 1 - Definieren Sie die Variable „cnt“ und initialisieren Sie sie mit „0“. Definieren Sie außerdem die Variable „invertiert“ und initialisieren Sie sie mit einem falschen Wert.

• Schritt 2 – Durchqueren Sie die Saite vom Ende beginnend. Wenn das erste [i] und das zweite [i] Zeichen nicht übereinstimmen, führen Sie die folgenden Schritte aus.

• Schritt 2.1 − Wenn der Wert der Variable „invertiert“ falsch ist, erhöhen Sie den Wert der Variablen „cnt“ um 1 und ändern Sie den Wert der Variablen „invertiert“ in „wahr“.

• Schritt 3 − Wenn beide Zeichen übereinstimmen und der Wert von „invertiert“ wahr ist, müssen wir das Bit erneut umdrehen. Erhöhen Sie also den Wert von „cnt“ um 1 und ändern Sie den Wert von „invertiert“. ' zu falsch.

Beispiel

Lassen Sie uns den obigen Algorithmus anhand des Beispiels debuggen.

Input – first = ‘001’, second = ‘000’

• Im ersten Schritt stimmen die erste [2] und die zweite [2] nicht überein und der Wert von „invertiert“ ist falsch. Daher wird der Wert von „cnt“ zu 1 und „inverted“ zu „true“. Indem wir hier den Wert von „inverted“ auf „true“ ändern, gehen wir davon aus, dass wir das Präfix praktisch invertiert haben.

• Danach stimmen der erste[1] und der zweite[1] überein, aber der Wert von „invertiert“ ist wahr. Der Wert von „cnt“ wird also zu 2 und der Wert von „invertiert“ ist falsch.

• Als nächstes stimmen die erste[0] und die zweite[0] überein und der Wert von „invertiert“ ist falsch. Wir müssen also keine Operation ausführen.

• Schließlich wird „cnt“ zurückgegeben, das den Wert 2 hat.

#include <bits/stdc++.h>
using namespace std;
// Function to find the minimum number of flips of prefixes required to convert the first binary string to the second
int minimumFlips(string first, string second, int N){

   // number of flips
   int cnt = 0;
   
   // to track whether the current bit is already flipped.
   // When we flip a bit 2 times, it becomes the same as the original bit.
   bool inverted = false;
   
   // Traverse the given string
   for (int i = N - 1; i >= 0; i--){
   
      // If A[i] is not equal to B[i]
      if (first[i] != second[i]){
      
         // If the current bit is not already flipped
         if (!inverted){
            cnt++; // Increase the count of flips
            inverted = true; // Invert all prefix bits
         }
      }
      else{
      
         // If A[i] is equal to B[i], but a current bit is flipped, we need to flip it again
         if (inverted){
         
            // Increase the count of flips
            cnt++;
            
            // Update inverted to false
            inverted = false;
         }
      }
   }
   return cnt;
}
int main(){
   string first = "001", second = "000";
   int N = first.size();
   cout << "The minimum number of flips of prefixes required to convert the first binary string to the second is - " << minimumFlips(first, second, N);
   return 0;
}

Ausgabe

The minimum number of flips of prefixes required to convert the first binary string to the second is - 2

Fazit

Wir haben zwei Methoden kennengelernt, um die Mindestanzahl an Präfixwechseln zu ermitteln, die zum Konvertieren einer Zeichenfolge in eine andere erforderlich sind. Die Logik besteht darin, die Zeichenfolge vom Ende an zu durchlaufen und das Präfix umzudrehen, wenn wir ein nicht übereinstimmendes Zeichen finden.

Wir haben den zweiten Codeabschnitt hinsichtlich der zeitlichen Komplexität optimiert, indem wir eine „invertierte“ Variable verwendet haben, um die invertierten Präfixe zu verfolgen, anstatt sie wie beim ersten Ansatz zu invertieren.

Das obige ist der detaillierte Inhalt vonMindestanzahl von Präfixwechseln, die erforderlich sind, um eine Binärzeichenfolge in eine andere umzuwandeln. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!