Trennen Sie Einsen und Nullen in einer Binärzeichenfolge in separate Hälften

In diesem Tutorial müssen wir alle Einsen und Nullen der gegebenen Binärzeichenfolge in zwei Hälften aufteilen. Hier müssen wir einen Teilstring aus dem gegebenen String nehmen und ihn umkehren, um verschiedene Teile von 0 und 1 zu trennen. Letztendlich müssen wir die Gesamtzahl der Inversionen berechnen, die erforderlich sind, damit der Teilstring die 1 und die 0 in zwei Hälften teilt.

Problemstellung – Wir erhalten eine Binärzeichenfolge gerader Länge. Wir müssen jeden Teilstring aus dem gegebenen String mehrmals nehmen und ihn umkehren, um ihn in zwei Hälften zu teilen. Am Ende müssen wir die Gesamtzahl der erforderlichen Umkehrungen ausdrucken.

Beispiel

Input –  str = 0011

Output – 0

Anleitung

Wir benötigen 0 Umkehrungen, da die Zeichenfolge in zwei Hälften geteilt ist.

Input –  str = 0011101000

Output – 2

Anleitung

• Nehmen Sie zunächst den Teilstring der Länge 2 ab dem 5. Index und kehren Sie ihn um. Die resultierende Zeichenfolge lautet 0011110000.

• Nehmen Sie danach eine Zeichenfolge der Länge 6 vom Anfang und kehren Sie sie um. Die resultierende Zeichenfolge lautet 1111000000

Input –  str = 010101

Output – 2

Anleitung

• Kehren Sie eine Zeichenfolge der Länge 2 ab dem ersten Index um. Die resultierende Zeichenfolge lautet 001101.

• Kehren Sie nun die Zeichenfolge der Länge 3 ab dem zweiten Index um. Die letzte Zeichenfolge lautet 000111.

Methode 1

Diese Methode zählt die Gesamtzahl unterschiedlicher benachbarter Elemente. Danach können wir sagen, dass die Gesamtzahl der erforderlichen Umkehrungen Anzahl / 2 beträgt.

Lassen Sie es uns verstehen, indem wir die Beispieleingabe debuggen.

Input –  str = 00111010

Die Gesamtzahl der verschiedenen angrenzenden Elemente beträgt also 4. Hier str[1] != str[2], str[4] != str[5], str[5] != str[6] und str[6] != str[7].

Der Zählwert ist also 4 und die Antwort ist count/2, was gleich 2 ist.

Algorithmus

• Schritt 1 – Initialisieren Sie die Variable „cnt“ auf 0.

• Schritt 2 – Verwenden Sie eine for-Schleife und durchlaufen Sie die Zeichenfolge.

• Schritt 3 − Wenn in der for-Schleife das aktuelle Element nicht mit dem vorherigen Element übereinstimmt, erhöhen Sie den Wert der Variablen „cnt“ um 1.

• Schritt 4 − Wenn der Wert von 'cnt' eine ungerade Zahl ist, geben Sie (cnt -1) /2 zurück. Andernfalls geben Sie cnt/2 zurück.

Beispiel

Beispiel

#include <bits/stdc++.h>
using namespace std;
//  function to find the minimum number of reversals required to segregate 1s and 0s in a separate half
int minimumReversal(string str, int len){
   int cnt = 0; // initialize count with zero
   for (int i = 1; i < len; i++){
   
      // if the adjacent elements are not the same, then the increment count
      if (str[i] != str[i - 1]){
         cnt++;
      }
   }
   
   // For odd count
   if (cnt % 2 == 1){
      return (cnt - 1) / 2;
   }
   return cnt / 2; // For even count
}
int main(){
   string str = "00111010";
   int len = str.size();
   cout << "Minimum number of operations required is : " << minimumReversal(str, len);
   return 0;
}

Ausgabe

Minimum number of operations required is : 2

Zeitkomplexität – O(N), da wir über die Zeichenfolge iterieren.

Raumkomplexität – O(N), weil wir konstanten Raum zum Speichern der Zählung verwenden.

Hier haben wir eine Logik verwendet, die immer dann umgekehrt werden muss, wenn zwei verschiedene benachbarte Elemente gefunden werden. Darüber hinaus können wir in einer einzelnen Umkehroperation zwei Elemente festlegen, sodass wir count/2 als Ergebniswert zurückgeben.

Das obige ist der detaillierte Inhalt vonTrennen Sie Einsen und Nullen in einer Binärzeichenfolge in separate Hälften. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!