Minimieren Sie die Anzahl der Flips, sodass die Zeichenfolge keine aufeinanderfolgenden Nullenpaare enthält

Hier müssen wir die Binärzeichenfolge so manipulieren, dass sie keine aufeinanderfolgenden Nullen enthält. Wenn wir aufeinanderfolgende Nullen finden, müssen wir jede Null in 1 ändern. Wir müssen also die Gesamtzahl von 0 zählen zu 1-Konvertierung, die wir durchführen sollten, um alle aufeinanderfolgenden Nullen aus der Zeichenfolge zu entfernen.

Problemstellung − Wir erhalten eine Binärzeichenfolge „str“, die nur 0 und 1 enthält. Wir müssen die minimal erforderliche Anzahl von Flips ermitteln, damit die resultierende Zeichenfolge keine aufeinanderfolgenden Nullen enthält.

Beispiel Beispiel

Input –  0101001

Output – 1

Erklärung

Wir müssen nur die vorletzte Null umdrehen.

Input –  str = 00100000100

Output – 4

Erklärung

Wir müssen die 2., 5., 7. und 11. Null umdrehen, um alle aufeinanderfolgenden Nullpaare zu eliminieren.

Input –  0101010101

Output – 0

Erklärung

Wir müssen nicht umdrehen, da die Zeichenfolge keine aufeinanderfolgenden Nullen enthält.

Methode 1

Bei dieser Methode durchlaufen wir die Zeichenfolge vom Anfang bis zum Ende und kehren die Zeichen um, wenn sie aufeinanderfolgende Nullen enthält. Schließlich können wir die minimale Anzahl von Flips ermitteln, die erforderlich sind, um alle aufeinanderfolgenden Nullen aus einer bestimmten Binärzeichenfolge zu entfernen.

Algorithmus

• Schritt 1 - Initialisieren Sie die Variable „cnt“ mit Null und speichern Sie die Gesamtzahl der Flips.

• Schritt 2 - Durchlaufen Sie die Binärzeichenfolge mithilfe der Schleife.

• Schritt 3 − Wenn das Zeichen am Index „I“ und Index „I +1“ 0 ist, kehren Sie das nächste Zeichen um und erhöhen Sie den Wert der Variablen „cnt“ um 1.

• Schritt 4 – Wenn die Iteration der for-Schleife abgeschlossen ist, geben Sie den Wert von „cnt“ zurück.

Beispiel

#include <bits/stdc++.h>
using namespace std;
// Function to get the total number of minimum flips required so the string does not contain any consecutive 0’s
int findCount(string str, int len){

   // initialize the count
   int cnt = 0;
   
   // iterate over the string
   for (int i = 0; i < len - 1; i++){
   
      // If two consecutive characters are the same
      if (str[i] == '0' && str[i + 1] == '0'){
      
         // Flip the next character
         str[i + 1] = '1';
         
         // increment count
         cnt++;           
      }
   }
   return cnt;
}
int main(){
   string str = "00100000100";
   int len = str.length();
   cout << "The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - " << findCount(str, len);
   return 0;
}

Ausgabe

The minimum numbers of flips required so that string doesn't contain any pair of consecutive zeros - 4

Zeitkomplexität − O(N), während wir die Binärzeichenfolge durchlaufen.

Raumkomplexität − O(1), da wir konstanten Raum zum Speichern der Gesamtzahlen verwenden.

Fazit

Wir haben gelernt, die Mindestanzahl von Flips zu berechnen, die erforderlich sind, um aufeinanderfolgende Nullenpaare aus einer bestimmten Binärzeichenfolge zu entfernen. Der Benutzer kann versuchen, die minimale Anzahl von Flips zu berechnen, die erforderlich sind, um ein aufeinanderfolgendes Paar aus einer bestimmten Binärzeichenfolge zu entfernen.

Das obige ist der detaillierte Inhalt vonMinimieren Sie die Anzahl der Flips, sodass die Zeichenfolge keine aufeinanderfolgenden Nullenpaare enthält. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!