Mindestanzahl an Zügen, die erforderlich sind, um alle Nullen vor Einsen in einer Binärzeichenfolge zu platzieren

Problemstellung

Wir erhalten eine binäre Zeichenfolge str und werden gebeten, die Mindestanzahl an Zeichen aus der Zeichenfolge zu entfernen, damit wir alle Nullen vor Einsen setzen können.

Beispiel

Eintreten

str = ‘00110100111’

Ausgabe

3

Anleitung

Hier können wir Output 3 auf zwei Arten erreichen.

Wir können arr[2], arr[3] und arr[5] oder arr[4], arr[6] und arr[7] aus der Zeichenfolge entfernen.

Eintreten

str = ‘001101011’

Ausgabe

2

Anleitung

Wir können arr[4] und arr[6] entfernen und alle Nullen vor Einsen setzen.

Eintreten

str = ‘000111’

Ausgabe

0

Anleitung

In der angegebenen Zeichenfolge wurden alle Nullen vor 1 platziert, sodass wir kein Zeichen aus der angegebenen Zeichenfolge entfernen müssen.

Methode 1

Bei der ersten Methode verwenden wir zwei Arrays. Das erste Array speichert alle Einsen auf der linken Seite und das andere Array speichert alle Nullen auf der rechten Seite. Danach können wir die Elemente am i-ten Index in beiden Arrays hinzufügen und die Mindestsumme ermitteln.

Algorithmus

• Schritt 1 – Definieren Sie eine benannte Liste von Nullen und Einsen der Länge n, wobei n die Länge der Zeichenfolge ist, die wir mit der Methode size() erhalten können.

• Schritt 2 – Wenn das erste Zeichen in der angegebenen Zeichenfolge „1“ ist, speichern Sie 1 am 0. Index des „Einsen“-Arrays, andernfalls speichern Sie 0.

• Schritt 3 – Verwenden Sie eine for-Schleife, um ab dem zweiten Element der Zeichenfolge zu iterieren. In der for-Schleife wird Ones[i] mit dem Wert initialisiert, der durch Addition von Ones[i-1] zu 1 oder 0 basierend auf dem Zeichen der Zeichenfolge am Index i erhalten wird.

• Schritt 4 – Speichern Sie 1 oder 0 bei Nullen[n-1], abhängig vom letzten Zeichen in der angegebenen Zeichenfolge.

• Schritt 5 – Verwenden Sie eine for-Schleife, um die Zeichenfolge ab dem letzten zweiten Zeichen zu durchlaufen und den Wert der Nullliste basierend auf den Zeichenfolgenzeichen zu aktualisieren.

• Schritt 6 – Definieren Sie die Variable „min_zeros_to_remove“ und initialisieren Sie sie mit dem maximalen ganzzahligen Wert.

• Schritt 7 – Gehen Sie nun die Listen „Null“ und „Eins“ durch. Greifen Sie auf Werte aus dem Index „i+1“ in der Nullliste und dem Index „I“ in der Liste „Eins“ zu. Fügen Sie anschließend diese beiden Elemente hinzu.

• Schritt 8 – Wenn der Wert von „min_zeros_to_remove“ kleiner ist als der aktuelle Wert der Variablen „min_zeros_to_remove“, ändern Sie ihren Wert in die Summe der beiden Array-Elemente.

• Schritt 9 – Ergebniswert zurückgeben.

Beispiel

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

int minimumZeroRemoval(string str){
   int n = str.size();
   // arrays to store the prefix sums of zeros and ones
   vector<int> zeros(n);
   vector<int> ones(n);
   // compute total number of 1s at the left of each index
   ones[0] = (str[0] == '1') ? 1 : 0;
   for (int i = 1; i < n; i++) {
      ones[i] = ones[i - 1] + ((str[i] == '1') ? 1 : 0);
   }
   // compute total number of 0s at the right of each index
   zeros[n - 1] = (str[n - 1] == '0') ? 1 : 0;
   for (int i = n - 2; i >= 0; i--){
      zeros[i] = zeros[i + 1] + ((str[i] == '0') ? 1 : 0);
   }
   // do the sum of zeros and ones for each index and return the minimum value
   int min_zeros_to_remove = INT_MAX;
   for (int i = 0; i < n - 1; i++){
      min_zeros_to_remove = min(min_zeros_to_remove, zeros[i + 1] + ones[i]);
   }
   return min_zeros_to_remove;
}
int main() {
   string str = "00110100111";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Ausgabe

The minimum number of zeros required to remove from the given string is - 3

• Zeitkomplexität - O(N), weil wir eine for-Schleife benötigen, um über Zeichenfolgen und Listen der Größe N zu iterieren.

• Raumkomplexität – O(N), da wir zwei Listen verwenden, um die Zählungen von 1 und 0 zu speichern.

Methode 2

Diese Methode ist eine optimierte Version der ersten Methode. Hier verwenden wir zwei Variablen, um die Anzahl von 1 und 0 anstelle einer Liste zu speichern.

Algorithmus

• Schritt 1 - Definieren Sie die Variable „zeros_right“ und initialisieren Sie sie mit 0.

• Schritt 2 – Durchlaufen Sie die Zeichenfolge, zählen Sie die Gesamtzahl der „0“-Zeichen in der angegebenen Zeichenfolge und aktualisieren Sie den Wert der Variablen „zero_right“ entsprechend.

• Schritt 3 – Definieren Sie die Variable „ones_left“ und initialisieren Sie sie auf 0.

• Schritt 4 – Verwenden Sie eine for-Schleife, um über die Zeichenfolge zu iterieren. Wenn das Zeichen am Index i in der Zeichenfolge „1“ ist, erhöhen Sie den Wert der Variablen „ones_left“ um 1. Andernfalls reduzieren Sie den Wert der Variablen „zeros_right“ um 1.

• Schritt 5 – Wenn „Nullen_rechts + Einsen_links“ kleiner als der aktuelle Wert der Variablen „res“ ist, aktualisieren Sie den Wert der Variablen „res“.

Beispiel

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

// function to remove zeros from the string to place all zeros before 1.
int minimumZeroRemoval(string str){
   // counting the total number of zeros in the given string
   int zeros_right = 0;
   for (int i = 0; i < str.size(); i++) {
      if (str[i] == '0')
      zeros_right += 1;
   }
   // variable to store the number of ones from left
   int ones_left = 0;
   // Size of the string
   int len = str.size();
   // variable to store the final result
   int result = INT_MAX;
   // Traverse the string from left to right
   for (int i = 0; i < len; i++){
      // If the current character is '1', then increment ones_left by 1 else, decrement zeros_right by 1
      if (str[i] == '1') {
         ones_left += 1;
      } else {
         zeros_right -= 1;
      }
      // Store the minimum result and zeros_right + ones_left in result
      result = min(result, zeros_right + ones_left);
   }
   // Return the final result
   return result;
}
int main() {
   string str = "001101011";
   int count = minimumZeroRemoval(str);
   cout << "The minimum number of zeros required to remove from the given string is - " << count;
   return 0;
}

Ausgabe

The minimum number of zeros required to remove from the given string is - 2

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

• Raumkomplexität – O(1), da wir nur konstanten Raum verwenden.

Fazit

Der Benutzer hat zwei Möglichkeiten kennengelernt, um die Mindestanzahl von Zeichen aus einer bestimmten Binärzeichenfolge zu entfernen. Der Code für den zweiten Ansatz ist besser lesbar, da wir Variablen verwenden, um die Anzahl der Nullen und Einsen zu speichern, anstatt eine Liste zu verwenden.

Das obige ist der detaillierte Inhalt vonMindestanzahl an Zügen, die erforderlich sind, um alle Nullen vor Einsen in einer Binärzeichenfolge zu platzieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!