Minimieren Sie die Anzahl der Nullen, die entfernt werden müssen, um die Länge der längsten aufeinanderfolgenden 1-Teilzeichenfolge zu maximieren

In diesem Artikel werden wir uns mit einem interessanten Problem befassen, das C++-String-Operationen betrifft. Das Problem, das wir heute untersuchen werden, besteht darin, „die Anzahl der Nullen zu minimieren, die gelöscht werden müssen, um die Länge der längsten fortlaufenden 1-Teilzeichenfolge zu maximieren“. Dieses Problem ist eine großartige Möglichkeit, Ihre Fähigkeiten in der String-Manipulation und dynamischen Programmierung zu verbessern.

Problemstellung

Bei einer gegebenen Binärzeichenfolge besteht die Aufgabe darin, die Anzahl der Nullen zu minimieren, die entfernt werden müssen, um die Länge der längsten 1-Teilzeichenfolge zu maximieren.

C++-Lösung

Um dieses Problem zu lösen, können wir die Schiebefenstermethode verwenden. Wir behalten zwei Zeiger bei, den linken Zeiger und den rechten Zeiger. Zunächst zeigen beide Zeiger auf das erste Element. Dann bewegen wir den rechten Zeiger weiter nach rechts. Wenn eine „0“ angetroffen wird, erhöhen wir einen Zähler. Wenn der Zähler größer wird als die zulässige Anzahl von Nullentfernungen, bewegen wir den linken Zeiger nach rechts, bis wir auf eine „0“ stoßen, und dekrementieren den Zähler.

Wir werden auch eine Variable maxLen pflegen, um die maximale Länge des 1 Teilstrings zu speichern, den wir bisher gesehen haben.

Beispiel

Dies ist der C++-Code, der das Problem löst -

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

int maxSubstring(string str, int k) {
   int zeroCount = 0;
   int left = 0;
   int maxLen = 0;
   
   for (int right = 0; right < str.size(); right++) {
      if (str[right] == '0') {
         zeroCount++;
      }
      while (zeroCount > k) {
         if (str[left] == '0') {
               zeroCount--;
         }
         left++;
      }
      maxLen = max(maxLen, right - left + 1);
   }
   return maxLen;
}

int main() {
   string str = "110100110";
   int k = 2; // number of zeros that can be removed
   int result = maxSubstring(str, k);
   cout << "The maximum length of the substring of 1s is: " << result << endl;
   return 0;
}

Ausgabe

The maximum length of the substring of 1s is: 5

Testfallbeschreibung

Nehmen wir die Binärzeichenfolge „110100110“, wir können 2 Nullen entfernen.

Wenn wir diese Zeichenfolge und den Wert von k an die Funktion maxSubstring übergeben, beginnt sie mit dem Scannen von links. Immer wenn es auf eine „0“ trifft, erhöht es den Wert „ZeroCount“. Wenn ZeroCount k überschreitet, beginnt es, den linken Zeiger nach rechts zu bewegen, bis es auf eine „0“ trifft und ZeroCount dekrementiert.

In diesem Prozess wird maxLen kontinuierlich aktualisiert, was die maximale Teilstringlänge von 1s ist. Für die angegebene Zeichenfolge beträgt die maximale Teilzeichenfolgenlänge von 1s ohne Entfernen von höchstens 2 Nullen 5, d. h. die Teilzeichenfolge „11111“ nach Entfernen der zweiten und dritten „0“.

Die Funktion gibt also 5 zurück.

Fazit

Diese Frage zeigt, wie man die Schiebefenstertechnologie effektiv nutzt, um komplexe String-Manipulationsprobleme in C++ zu lösen. Dies ist eine hervorragende Frage zum Verstehen und Üben dynamischer Programmier- und String-Verarbeitungstechniken. Üben Sie weiterhin Fragen wie diese, um Ihre C++-Programmierkenntnisse zu verbessern.

Das obige ist der detaillierte Inhalt vonMinimieren Sie die Anzahl der Nullen, die entfernt werden müssen, um die Länge der längsten aufeinanderfolgenden 1-Teilzeichenfolge zu maximieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!