Mindestanzahl an Entfernungen, damit eine Zeichenfolge aus einer Zeichenfolge aus Nullen, gefolgt von einer Zeichenfolge aus Einsen, besteht

Die Frage „Mindestlöschung für String-Verkettung von 0 Teilstrings“ beinhaltet Arbeiten zur Manipulation von Strings. Wenn als Eingabe eine Zeichenfolge aus Nullen und Einsen gegeben wird, ist das Ergebnis eine Ganzzahl, die die Mindestanzahl an Nullen widerspiegelt, die eliminiert werden muss, um eine Teilzeichenfolge aufeinanderfolgender Nullen zu generieren.

Mit anderen Worten, das Problem lässt sich folgendermaßen umformulieren: Wie viele Nullen müssen bei einer aus Nullen und Einsen bestehenden Zeichenfolge entfernt werden, damit die verbleibende Zeichenfolge eine fortlaufende Periode von Nullen enthält?

Algorithmus

Schritt 1: Variableninitialisierung

• Definieren Sie eine Zählvariable, um die Länge der aktuellen Nullsequenz aufzuzeichnen.

• Definieren Sie eine max_count-Variable, um die längste bisher gefundene Folge von Nullen zu verfolgen.

• Setzen Sie beide Variablen auf 0.

Schritt 2: String-Traversierung

Verwenden Sie eine Schleife, um jedes Zeichen in der Zeichenfolge zu durchlaufen.

Schritt drei: Nullerkennung

Wenn das aktuelle Zeichen Null ist, erhöhen Sie die Zählvariable.

Schritt 4: Ein Test

• Wenn das aktuelle Zeichen 1 ist, vergleichen Sie die Zählvariable mit der Variablen max_count.

• Wenn die Zählvariable höher ist als die Variable max_count, setzen Sie die Variable max_count gleich der Zählvariablen.

• Setzen Sie die Zählvariable auf 0 zurück.

Schritt 5: Schleife abgeschlossen

Wiederholen Sie diesen Vorgang, bis alle Zeichen in der Zeichenfolge verarbeitet wurden.

Schritt 6: Berechnung der Mindestlöschung

Die Mindestanzahl an Löschvorgängen, die erforderlich sind, um alle Nullen zu entfernen, sodass die verbleibenden Einsen nicht durch Nullen getrennt sind, kann berechnet werden, indem max_count von der Zeichenfolgenlänge abgezogen wird.

Schritt 7: Ergebnisausgabe

Drucken Sie die Ergebnisse auf der Konsole.

Zu befolgende Methode

• Dynamische Methoden

• Iterationsmethode

Methode 1: Dynamische Methode

Dynamische Programmierung kann verwendet werden, um dieses Problem effizient zu lösen. Um eine Teilzeichenfolge aufeinanderfolgender Nullen zu erstellen, können wir ein Array dp[] erstellen, wobei dp[i] die minimale Anzahl von Nullen darstellt, die aus der Teilzeichenfolge s[0...i] entfernt werden müssen. Die Mindestanzahl von Nullen, die aus einem leeren Teilstring entfernt werden müssen, ist 0, sodass wir dp[0] auf 0 initialisieren können.

Wir können dann über die Zeichenfolge s iterieren und dp[i] auf −

• Wenn s[i] „0“ ist, dann ist dp[i] = dp[i-1], weil wir s[i] in eine Teilzeichenfolge aufeinanderfolgender Nullen einschließen oder diese entfernen können.

• Wenn s[i] „1“ ist, müssen wir den Index j ermitteln, der i am nächsten kommt und eine Teilzeichenfolge aufeinanderfolgender Nullen enthält. Dies kann erreicht werden, indem von i-1 bis 0 iteriert wird und geprüft wird, ob die Teilzeichenfolge s[j...i] aufeinanderfolgende Nullen enthält. Wenn der Index j gefunden wird, gilt dp[i] = dp[j-1] + (i-j+1), wobei dp[j-1] die minimale Anzahl von Nullen darstellt, die aus der Teilzeichenfolge s[ entfernt werden müssen. .j-1] und (i-j+1) sind die Gesamtzahl der Einsen, die eliminiert werden müssen, um die Teilzeichenfolge s[j...i] aufeinanderfolgender Nullen zu erhalten. Wenn kein solcher Index j gefunden wird, dann ist dp[i] = dp[i-1], da wir s[i] nicht in einer Teilzeichenfolge aufeinanderfolgender Nullen enthalten können.

  Um schließlich eine Teilzeichenfolge aufeinanderfolgender Nullen zu erhalten, wird die Mindestanzahl der Nullen, die aus der gesamten Zeichenfolge s entfernt werden müssen, durch dp[n-1] angegeben, wobei n die Länge der Zeichenfolge s ist.

Beispiel 1

Das folgende Programm verwendet die oben besprochene Methode, indem es zuerst die Eingabezeichenfolge aus der Standardeingabe liest und dann alle Teilzeichenfolgen von 0 identifiziert. Berechnen Sie dann die Länge der längsten 0-Teilzeichenfolge und die Länge der Zeichenfolge, die durch Verketten jeder 0-Teilzeichenfolge erzeugt wird. Um die erforderliche Mindestanzahl an Eliminierungen zu ermitteln, wird schließlich die Länge des längsten 0-Teilstrings von der Summe aller 0-Teilstrings subtrahiert und das Ergebnis in der Standardausgabe angezeigt.

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

int main() {
   string s = "100100011000110"; // constant input string

   vector<pair<int, int>> substrings; // vector to store start and end indices of each substring of 0s

   int start = -1;
   for (int i = 0; i < s.length(); i++) {
      if (s[i] == '0') {
         if (start == -1) {
         start = i;
         }
      } else {
         if (start != -1) {
         substrings.push_back(make_pair(start, i - 1));
         start = -1;
         }
      }
   }
   if (start != -1) {
      substrings.push_back(make_pair(start, s.length() - 1));
   }

   int totalLength = 0;
   for (auto& p : substrings) {
      totalLength += p.second - p.first + 1;
   }

   int maxLength = 0;
   for (auto& p : substrings) {
      int len = p.second - p.first + 1;
      if (len > maxLength) {
         maxLength = len;
      }
   }

   int removals = totalLength - maxLength;
   cout << "Input string: " << s << endl;
   cout << "Minimum removals: " << removals << endl;

   return 0;
}

Ausgabe

Input string: 100100011000110
Minimum removals: 6

Methode 2: Iterative Methode

Diese Methode verwendet eine einfache Iterationsmethode, um die angegebene Zeichenfolge Zeichen für Zeichen zu durchlaufen und dabei die Werte der beiden Variablen count und max_count zu aktualisieren. Diese Methode aktualisiert den Wert der Variablen count und max_count basierend darauf, ob das aktuelle Zeichen 0 oder 1 ist. Es liefert dann die Differenz zwischen max_count und der Länge der längsten 0-Teilzeichenfolge.

Beispiel 2

Beispiel 2

Bei diesem Code handelt es sich um eine C++-Software, die die Mindestanzahl an Eliminierungen berechnet, die erforderlich sind, um alle Nullen aus einer Binärzeichenfolge zu entfernen, sodass der Rest nicht durch Nullen getrennt ist. Die Funktion min_deletions verwendet eine binäre Zeichenfolge als Eingabe und verwendet eine Schleife, um jedes Zeichen in der Zeichenfolge zu durchlaufen. Die Schleife erhöht die Zählvariable jedes Mal, wenn sie auf Null trifft, und setzt sie auf Null zurück, wenn sie auf Eins trifft. Der Maximalwert der Zählvariablen wird in max_count gespeichert und schließlich wird die Länge der Zeichenfolge von max_count subtrahiert, um die erforderliche Mindestanzahl an Löschungen zu erhalten. Die Ergebnisse werden dann dem Benutzer angezeigt.

#include <iostream> 
#include <string> 
using namespace std; 
 
int min_deletions(string str) { 
   int count = 0, max_count = 0; 
   for (char c : str) { 
      if (c == '0') { 
         count++; 
      } else { 
         max_count = max(max_count, count); 
         count = 0; 
      } 
   } 
    return str.length() - max_count; 
} 
 
int main() { 
   string str = "100010011000110"; 
   int deletions = min_deletions(str); 
   cout << "Minimum deletions needed: " << deletions << endl; 
   return 0; 
} 

Ausgabe

Minimum deletion needed: 12 

Fazit

Das Bestimmen aller Teilzeichenfolgen von 0, das Berechnen der Länge der Zeichenfolge, die durch die Verkettung jeder Teilzeichenfolge von 0 entsteht, und das Bestimmen der Länge der längsten Teilzeichenfolge von 0 sind die drei Schritte zur Lösung des gegebenen Problems. Die Länge der größten 0-Teilzeichenfolge kann dann von der Summe aller 0-Teilzeichenfolgen abgezogen werden, um die erforderliche Mindestanzahl an Löschungen zu erhalten.

Die Methode, mit der wir die Antwort erhalten, ist einfach, effizient und läuft in linearer Zeit, sodass sie für große Eingaben geeignet ist. Es kann jedoch durch die Anwendung ausgefeilterer Methoden wie der dynamischen Programmierung noch weiter verbessert werden.

Das obige ist der detaillierte Inhalt vonMindestanzahl an Entfernungen, damit eine Zeichenfolge aus einer Zeichenfolge aus Nullen, gefolgt von einer Zeichenfolge aus Einsen, besteht. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!