Heim > Artikel > Backend-Entwicklung > Übersetzen Sie Folgendes ins Chinesische: Minimieren Sie die Entfernung von 0-Teilzeichenfolgen, um alle Vorkommen von 0 aus einer Schleifen-Binärzeichenfolge zu entfernen
In diesem Problem müssen wir alle Nullen aus der gegebenen Binärzeichenfolge entfernen. Gleichzeitig müssen wir aufeinanderfolgende Nullenpaare auf einmal entfernen und die Gesamtzahl der entfernten Nullenpaare zählen.
Wir können das Problem lösen, indem wir die Anzahl der Paare aufeinanderfolgender Nullen in der angegebenen Zeichenfolge zählen. In diesem Tutorial lernen wir zwei verschiedene Lösungen zur Lösung des Problems.
Problemstellung − Wir erhalten eine zirkuläre Binärzeichenfolge str der Länge N. Wir müssen die Mindestanzahl aufeinanderfolgender Nullen ermitteln, die erforderlich ist, um alle Nullen aus der Zeichenfolge zu entfernen.
Input – str = "0011001"
Output – 2
Wir können str[0] und str[1] zusammen löschen. Danach können wir str[4] und str[5] löschen. Wir müssen also zwei Paare aufeinanderfolgender Nullen entfernen.
Input – str = ‘0000000’
Output – 1
Wir können alle Nullen auf einmal entfernen.
Input – str = ‘00110010’
Output – 2
Wir können str[0], str[1] und str[7] zusammen entfernen, da die Binärzeichenfolge kreisförmig ist. Als nächstes können wir str[5] und str[6] zusammen entfernen.
Mit dieser Methode ermitteln wir die Gesamtzahl aufeinanderfolgender Nullpaare in der angegebenen Zeichenfolge, die die angegebene Frage beantworten.
Schritt 1 – Initialisieren Sie die Variable „cnt“ auf Null.
Schritt 2 – Initialisieren Sie die Variable „isOne“ auf den Wert „false“, um die Nummer 1 in der angegebenen Zeichenfolge zu verfolgen.
Schritt 3 – Mit einer Schleife über die Zeichenfolge iterieren. Wenn in der Schleife das aktuelle Zeichen „0“ ist, erhöhen Sie den Wert von „cnt“ um 1.
Schritt 4 - Verwenden Sie eine While-Schleife, um zu iterieren, bis wir weiterhin das nächste Zeichen finden, das „0“ ist, und den Wert von „I“ um 1 erhöhen.
Schritt 5 – Wenn das aktuelle Zeichen „1“ ist, ändern Sie den Wert der Variablen „isOne“ in „true“, um anzuzeigen, dass die Zeichenfolge mindestens eine „1“ enthält.
Schritt 6 - Sobald die Iteration der Schleife abgeschlossen ist, bedeutet dies, dass der Wert von „isOne“ in solchen Fällen nur Nullen enthält.
Schritt 7 − Wenn das erste und das letzte Zeichen „0“ sind, verringern Sie den Wert von „cnt“ um 1, da die Zeichenfolge kreisförmig ist.
Schritt 8 - Geben Sie den Wert von „cnt“ zurück.
#include <bits/stdc++.h> using namespace std; int countRemovels(string str, int N){ // to store the count of 0s int cnt = 0; bool isOne = false; // Iterate over the string for (int i = 0; i < N; i++){ // If the current character is 0, increment the count of 0s if (str[i] == '0'){ cnt++; // traverse the string until a 1 is found while (str[i] == '0'){ i++; } } else{ // If the current character is 1, then set isOne as true isOne = true; } } // If string contains only 0s, then return 1. if (!isOne) return 1; // If the first and last character is 0, then decrement the count, as the string is circular. if (str[0] == '0' && str[N - 1] == '0'){ cnt--; } // return cnt return cnt; } int main(){ string str = "0011001"; int N = str.size(); cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N); return 0; }
The total number of minimum substrings of consecutive zeros required to remove is - 2<font face="sans-serif"><span style="font-size: 16px; background-color: rgb(255, 255, 255);">.</span></font></p><p>
Raumkomplexität – O(1)
Bei dieser Methode berechnen wir die Mindestanzahl der Nullen entfernenden Teilzeichenfolgen, die erforderlich sind, um alle Nullen zu entfernen, indem wir die Differenz benachbarter Elemente zählen.
Schritt 1 − Definieren Sie die Variablen „cnt“ und „isOne“ und initialisieren Sie sie mit 0 bzw. false.
Schritt 2 − Verwenden Sie die for-Schleife, um N-1 Iterationen durchzuführen, wobei N die Länge der Zeichenfolge ist.
Schritt 3 − Überprüfen Sie in der Schleife, ob das aktuelle Zeichen „0“ und das nächste Zeichen „1“ ist, erhöhen Sie den Wert von „cnt“ um 1. Ändern Sie andernfalls den Wert von „isOne“. variabel zu wahr.
Schritt 4 – Wenn das letzte Zeichen „0“ und das erste Zeichen „1“ ist, erhöhen Sie den Wert von „cnt“ um 1.
Schritt 5 – Wenn der Wert von „isOne“ falsch ist, geben Sie 1 zurück.
Schritt 6 – Geben Sie den Wert der Variablen „cnt“ zurück.
#include <bits/stdc++.h> using namespace std; int countRemovels(string str, int N){ // to store the count of 0s int cnt = 0; // to check if there is at least one 1 bool isOne = false; // traverse the string for (int i = 0; i < N - 1; i++) { // if the current character is 0, the next is 1, then increment count by 1 if (str[i] == '0' && str[i + 1] == '1'){ cnt++; } else{ // if the current character is 1, then set isOne to true isOne = true; } } // for circular string, if the last character is 0 and the first is 1, then increment count by 1 if (str[N - 1] == '0' && str[0] == '1'){ cnt++; } // if there is no 1 in the string, then return 1 if (!isOne){ return 1; } return cnt; // return cnt } int main(){ string str = "0011001"; int N = str.size(); cout << "The total number of minimum substrings of consecutive zeros required to remove is - " << countRemovels(str, N); return 0; }
The total number of minimum substrings of consecutive zeros required to remove is - 2
Wir haben zwei verschiedene Lösungen zur Lösung des gegebenen Problems gesehen. Bei der ersten Methode zählen wir die Gesamtzahl der aufeinanderfolgenden Nullpaare, bei der zweiten Methode zählen wir die Gesamtzahl der nicht übereinstimmenden benachbarten Zeichen.
Das obige ist der detaillierte Inhalt vonÜbersetzen Sie Folgendes ins Chinesische: Minimieren Sie die Entfernung von 0-Teilzeichenfolgen, um alle Vorkommen von 0 aus einer Schleifen-Binärzeichenfolge zu entfernen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!