Saitenkompression III

3163. Saitenkomprimierung III

Schwierigkeit:Mittel

Themen:String

Komprimieren Sie ein gegebenes Zeichenfolgenwort mit dem folgenden Algorithmus:

• Beginnen Sie mit einer leeren Zeichenfolgenkomposition. Während das Wort nicht leer ist, verwenden Sie die folgende Operation:
  • Entfernen Sie ein Wortpräfix mit maximaler Länge, das aus einem einzelnen Zeichen besteht und höchstens 9 Mal wiederholt wird.
  • Fügen Sie die Länge des Präfixes gefolgt von c an comp. an.

Gib die Zeichenfolge comp zurück.

Beispiel 1:

• Eingabe: word = "abcde"
• Ausgabe: „1a1b1c1d1e“
• Erklärung: Zunächst comp = "". Wenden Sie die Operation fünfmal an und wählen Sie bei jeder Operation „a“, „b“, „c“, „d“ und „e“ als Präfix.
  • Fügen Sie für jedes Präfix „1“ gefolgt vom zu komponierenden Zeichen hinzu.

Beispiel 2:

• Eingabe:word = "aaaaaaaaaaaaaabb"
• Ausgabe: „9a5a2b“
• Erklärung: Zunächst comp = "". Wenden Sie die Operation dreimal an und wählen Sie bei jeder Operation „aaaaaaaaa“, „aaaaa“ und „bb“ als Präfix.
  • Für das Präfix „aaaaaaaa“ hängen Sie „9“ gefolgt von „a“ an comp. an.
  • Für das Präfix „aaaaa“ hängen Sie „5“ gefolgt von „a“ an comp. an.
  • Für das Präfix „bb“ hängen Sie „2“ gefolgt von „b“ an comp an.

Einschränkungen:

• 1 <= Wortlänge <= 2 * 10⁵
• Wort besteht nur aus englischen Kleinbuchstaben.

Hinweis:

1. Schneiden Sie jedes Mal das gleiche Zeichen maximal 9 Mal im Präfix aus. Es ist immer besser, ein größeres Präfix zu schneiden.

Lösung:

Wir können einen gierigen Ansatz verwenden, um die Zeichenfolge zu komprimieren, indem wir das längstmögliche Präfix aus sich wiederholenden Zeichen nehmen (bis zu 9 Vorkommen gleichzeitig) und dann die Länge des Präfixes zusammen mit dem Zeichen an das Ergebnis anhängen.

Hier ist die Schritt-für-Schritt-Lösung:

1. Variablen initialisieren:

   • comp (die komprimierte Zeichenfolge) beginnt als leere Zeichenfolge.
   • Verwenden Sie einen Zeiger oder Index i, um die Position im Wort zu verfolgen.

2. Wort durchgehen:

   • Solange im Wort noch Zeichen übrig sind, finden Sie das längste Präfix sich wiederholender Zeichen, das 9 Zeichen nicht überschreitet.
   • Zählen Sie, wie oft sich das aktuelle Zeichen nacheinander wiederholt, bis zu einem Maximum von 9.

3. An komprimierte Zeichenfolge anhängen:

   • Fügen Sie die Anzahl gefolgt vom Zeichen zur Komp. hinzu.
   • Bewegen Sie den Zeiger i um die Anzahl der verarbeiteten Zeichen vorwärts.

4. Ergebnis zurückgeben:

   • Nachdem die gesamte Zeichenfolge verarbeitet wurde, geben Sie die komprimierte Zeichenfolge comp zurück.

Lassen Sie uns diese Lösung in PHP implementieren: 3163. Saitenkomprimierung III

  
  
  Erläuterung:




Zählschleife: Wir verwenden eine While-Schleife innerhalb der Hauptschleife, um aufeinanderfolgende Zeichen (bis zu 9) für jedes einzelne Zeichen im Wort zu zählen.

Ergebnisse anhängen: Nach dem Zählen jeder Sequenz hängen wir die Anzahl und das Zeichen direkt an comp an.

Zeigeraktualisierung: Der Hauptschleifenzeiger i bewegt sich um die Anzahl der gezählten Zeichen vorwärts, wodurch die Größe der verbleibenden Zeichenfolge in jeder Iteration effektiv reduziert wird.



  
  
  Komplexitätsanalyse




Zeitkomplexität: O(n), wobei n die Länge des Wortes ist. Jedes Zeichen wird einmal verarbeitet.

Raumkomplexität: O(n) für das in comp. gespeicherte komprimierte Ergebnis.


Diese Lösung ist effizient und verarbeitet Randfälle, wie zum Beispiel Sequenzen, die kürzer als 9 Zeichen sind oder ein einzelnes Vorkommen jedes Zeichens.

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 vonSaitenkompression III. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!