Maximale Punktzahl nach dem Teilen einer Zeichenfolge

1422. Maximale Punktzahl nach dem Teilen einer Zeichenfolge

Schwierigkeit:Einfach

Themen:String, Präfixsumme

Gegeben eine Zeichenfolge s aus Nullen und Einsen, geben Sie die maximale Punktzahl zurück, nachdem die Zeichenfolge in zwei nicht leere Teilzeichenfolgen aufgeteilt wurde (d. h. linke Teilzeichenfolge und rechts Teilzeichenfolge).

Die Punktzahl nach dem Teilen einer Zeichenfolge ist die Anzahl der Nullen im linken Teilstring plus der Anzahl der Einsen im rechten Teilzeichenfolge.

Beispiel 1:

• Eingabe: s = "011101"
• Ausgabe: 5
• Erklärung: Alle möglichen Möglichkeiten, s in zwei nicht leere Teilzeichenfolgen aufzuteilen, sind:
  • links = „0“ und rechts = „11101“, Punktzahl = 1 4 = 5
  • links = „01“ und rechts = „1101“, Punktzahl = 1 3 = 4
  • links = „011“ und rechts = „101“, Punktzahl = 1 2 = 3
  • links = „0111“ und rechts = „01“, Punktzahl = 1 1 = 2
  • links = „01110“ und rechts = „1“, Punktzahl = 2 1 = 3

Beispiel 2:

• Eingabe: s = "00111"
• Ausgabe: 5
• Erklärung:Wenn links = „00“ und rechts = „111“, erhalten wir die maximale Punktzahl = 2 3 = 5

Beispiel 3:

• Eingabe: s = "1111"
• Ausgabe: 3

Einschränkungen:

• 2
• Die Zeichenfolge s besteht nur aus den Zeichen „0“ und „1“.

Hinweis:

1. Berechnen Sie im Voraus eine Präfixsumme von Einsen ('1').
2. Iterieren Sie von links nach rechts und zählen Sie die Anzahl der Nullen ('0'). Verwenden Sie dann die vorberechnete Präfixsumme zum Zählen von Einsen ('1'). Aktualisieren Sie die Antwort.

Lösung:

Wir können den bereitgestellten Hinweis nutzen, indem wir eine Präfixsumme von Einsen ('1') in der Zeichenfolge vorab berechnen. So können wir die Lösung aufschlüsseln:

Schritte:

1. Präfix-Summe von Einsen: Berechnen Sie vorab ein Array, in dem jedes Element am Index i die Anzahl der Einsen ('1') bis zum Index i in der Zeichenfolge enthält.
2. Über die Zeichenfolge iterieren: Behandeln Sie für jede Position i die Teilzeichenfolge von 0 bis i als „linke“ Teilzeichenfolge und von i 1 bis zum Ende der Zeichenfolge als „rechte“ Teilzeichenfolge.
   • Zählen Sie die Nullen im linken Teilstring, indem Sie sie einfach während der Iteration zählen.
   • Verwenden Sie die Präfixsumme, um die Einsen in der rechten Teilzeichenfolge zu zählen (indem Sie die Präfixsumme am Teilungspunkt von der Gesamtzahl der Einsen in der Zeichenfolge subtrahieren).
3. Berechnen Sie die Punktzahl: Berechnen Sie für jede mögliche Aufteilung die Punktzahl als Anzahl der Nullen im linken Teilstring plus der Anzahl der Einsen im rechten Teilstring.
4. Gibt die maximale Punktzahl zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 1422. Maximale Punktzahl nach dem Teilen einer Zeichenfolge

<?php /**
 * @param String $s
 * @return Integer
 */
function maxScore($s) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
$s1 = "011101";
$s2 = "00111";
$s3 = "1111";

echo "Input: $s1, Output: " . maxScore($s1) . PHP_EOL; // Output: 5
echo "Input: $s2, Output: " . maxScore($s2) . PHP_EOL; // Output: 5
echo "Input: $s3, Output: " . maxScore($s3) . PHP_EOL; // Output: 3
?>

Erläuterung:

1. Präfixsummenberechnung: Wir berechnen die Präfixsumme der Einsen im Array $prefixOneCount, wobei jeder Index die kumulative Anzahl der Einsen bis zu diesem Punkt enthält.

2. Iterieren über mögliche Aufteilungen: Wir beginnen mit der Iteration durch jeden Index i (von 0 bis n-2), wobei die Zeichenfolge in einen linken Teil (von 0 bis i) und einen rechten Teil ( von i 1 bis n-1).

   • Zählen Sie für jede Teilung die Nullen im linken Teilstring ($zeroCountLeft).
   • Verwenden Sie den vorberechneten $prefixOneCount, um zu berechnen, wie viele Einsen in der rechten Teilzeichenfolge enthalten sind.

3. Score-Berechnung: Der Score für jede Teilung wird als Summe der Nullen im linken Teil und der Einsen im rechten Teil berechnet. Wir aktualisieren die maximale Punktzahl, die während dieser Iteration erreicht wurde.

4. Endergebnis: Die Funktion gibt die maximale Punktzahl zurück, die während aller Splits gefunden wurde.

Komplexität:

• Zeitkomplexität: O(n)

  • Das Vorberechnen von Präfixsummen und das Durchlaufen der Zeichenfolge erfordern beide O(n).
  • Das Durchlaufen der Zeichenfolge zur Berechnung der Ergebnisse erfordert ebenfalls O(n).
  • Die Gesamtzeitkomplexität beträgt also O(n), was für die gegebene Eingabegröße (n ≤ 500) effizient ist.

• Raumkomplexität: O(n)

  • Das Präfix-Summen-Array erfordert O(n) zusätzlichen Platz.

Beispiel:

echo maxScore("011101"); // Output: 5
echo maxScore("00111");  // Output: 5
echo maxScore("1111");   // Output: 3

Diese Lösung ist optimal und behandelt das Problem innerhalb der Einschränkungen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonMaximale Punktzahl nach dem Teilen einer Zeichenfolge. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!