Typescript Coding Chronicles: String-Komprimierung

Problemstellung:

Komprimieren Sie ein gegebenes Array von Zeichen mit dem folgenden Algorithmus:

• Beginnen Sie mit einer leeren Zeichenfolge s.
• Für jede Gruppe aufeinanderfolgender sich wiederholender Zeichen in Zeichen:
  • Wenn die Gruppenlänge 1 beträgt, hängen Sie das Zeichen an s.
  an
  • Andernfalls hängen Sie das Zeichen gefolgt von der Länge der Gruppe an.

Die komprimierten Zeichenfolgen sollten nicht separat zurückgegeben, sondern im Eingabezeichen-Array chars gespeichert werden. Beachten Sie, dass Gruppenlängen von 10 oder mehr in chars.

Nachdem Sie mit der Änderung des Eingabearrays fertig sind, geben Sie die neue Länge des Arrays zurück.

Sie müssen einen Algorithmus schreiben, der nur konstanten zusätzlichen Speicherplatz verwendet.

Beispiel 1:

• Eingabe: chars = ["a", "a", "b", "b", "c", "c", "c"]
• Ausgabe: Geben Sie 6 zurück, und die ersten 6 Zeichen des Eingabearrays sollten sein: [„a“, „2“, „b“, „2“, „c“, „3“]
• Erklärung: Die Gruppen sind „aa“, „bb“ und „ccc“. Dies wird zu „a2b2c3“ komprimiert.

Beispiel 2:

• Eingabe: chars = ["a"]
• Ausgabe: Gibt 1 zurück und das erste Zeichen des Eingabearrays sollte sein: ["a"]
• Erklärung: Die einzige Gruppe ist „a“, die unkomprimiert bleibt, da es sich um ein einzelnes Zeichen handelt.

Beispiel 3:

• Eingabe: chars = ["a", "b", "b", "b", "b", "b", "b", "b", "b", "b", "b". ","b","b"]
• Ausgabe: Geben Sie 4 zurück, und die ersten 4 Zeichen des Eingabearrays sollten sein: ["a", "b", "1", "2"]
• Erklärung: Die Gruppen sind „a“ und „bbbbbbbbbbbb“. Dies wird auf „ab12“ komprimiert.

Einschränkungen:

• 1 <= chars.length <= 2000
• chars[i] ist ein englischer Kleinbuchstabe, ein englischer Großbuchstabe, eine Ziffer oder ein Symbol.

Erster Denkprozess:

Um dieses Problem zu lösen, müssen wir das Array durchlaufen und dabei das aktuelle Zeichen und seine Anzahl im Auge behalten. Wenn wir auf ein neues Zeichen stoßen, hängen wir das aktuelle Zeichen und seine Anzahl (falls größer als 1) an das Array an. Wir müssen sicherstellen, dass wir dies vor Ort tun, um den Anforderungen an die Platzkomplexität gerecht zu werden.

Grundlegende Lösung (Brute Force):

Die Brute-Force-Lösung besteht darin, ein neues Array zu erstellen, um die komprimierte Version des Eingabearrays zu speichern. Dies ist nicht platzsparend, hilft uns aber, die erforderlichen Schritte zu verstehen.

Code:

function compressBruteForce(chars: string[]): number {
    const n = chars.length;
    let compressed: string[] = [];
    let i = 0;

    while (i < n) {
        let char = chars[i];
        let count = 0;

        while (i < n && chars[i] === char) {
            i++;
            count++;
        }

        compressed.push(char);
        if (count > 1) {
            compressed.push(...count.toString().split(''));
        }
    }

    for (let j = 0; j < compressed.length; j++) {
        chars[j] = compressed[j];
    }

    return compressed.length;
}

Zeitkomplexitätsanalyse:

• Zeitkomplexität: O(n), wobei n die Länge des Arrays ist. Wir durchlaufen das Array einmal, um Zeichen zu zählen, und einmal, um das Ergebnis zu schreiben.
• Raumkomplexität: O(n), da wir zusätzlichen Platz für das komprimierte Array verwenden.

Einschränkungen:

Die Brute-Force-Lösung ist nicht platzsparend und erfüllt nicht die Einschränkung, nur ständig zusätzlichen Platz zu nutzen.

Optimierte Lösung:

Die optimierte Lösung besteht darin, das Eingabearray an Ort und Stelle zu ändern, um die komprimierte Version zu speichern. Wir verwenden zwei Zeiger: einen zum Lesen des Eingabearrays und einen zum Schreiben der komprimierten Ausgabe.

Code:

function compress(chars: string[]): number {
    let writeIndex = 0;
    let i = 0;

    while (i < chars.length) {
        let char = chars[i];
        let count = 0;

        // Count the number of consecutive repeating characters
        while (i < chars.length && chars[i] === char) {
            i++;
            count++;
        }

        // Write the character
        chars[writeIndex] = char;
        writeIndex++;

        // Write the count if greater than 1
        if (count > 1) {
            let countStr = count.toString();
            for (let j = 0; j < countStr.length; j++) {
                chars[writeIndex] = countStr[j];
                writeIndex++;
            }
        }
    }

    return writeIndex;
}




<h3>
  
  
  Zeitkomplexitätsanalyse:
</h3>

<ul>
<li>
<strong>Zeitkomplexität:</strong> O(n), wobei n die Länge des Arrays ist. Wir durchlaufen das Array einmal, um Zeichen zu zählen, und einmal, um das Ergebnis zu schreiben.</li>
<li>
<strong>Raumkomplexität:</strong> O(1), da wir nur eine konstante Menge zusätzlichen Raums für Variablen verwenden.</li>
</ul>

<h3>
  
  
  Verbesserungen gegenüber der Basislösung:
</h3>

<ul>
<li>Die optimierte Lösung reduziert die Platzkomplexität auf O(1), indem sie das Eingabearray an Ort und Stelle ändert.</li>
</ul>

<h2>
  
  
  Randfälle und Tests:
</h2>

<h3>
  
  
  Randfälle:
</h3>

<ol>
<li>Das Array enthält nur ein Zeichen.</li>
<li>Das Array enthält keine aufeinanderfolgenden sich wiederholenden Zeichen.</li>
<li>Das Array enthält eine große Anzahl aufeinanderfolgender sich wiederholender Zeichen.</li>
</ol>

<h3>
  
  
  Testfälle:
</h3>



<pre class="brush:php;toolbar:false">console.log(compressBruteForce(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compressBruteForce(["a"])); // 1, ["a"]
console.log(compressBruteForce(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compressBruteForce(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compressBruteForce(["a","b","c"])); // 3, ["a","b","c"]

console.log(compress(["a","a","b","b","c","c","c"])); // 6, ["a","2","b","2","c","3"]
console.log(compress(["a"])); // 1, ["a"]
console.log(compress(["a","b","b","b","b","b","b","b","b","b","b","b","b"])); // 4, ["a","b","1","2"]
console.log(compress(["a","a","a","a","a","a","a","a","a","a"])); // 3, ["a","1","0"]
console.log(compress(["a","b","c"])); // 3, ["a","b","c"]

Allgemeine Problemlösungsstrategien:

1. Verstehen Sie das Problem:Lesen Sie die Problemstellung sorgfältig durch, um die Anforderungen und Einschränkungen zu verstehen.
2. Schlüsseloperationen identifizieren: Bestimmen Sie die erforderlichen Schlüsseloperationen, z. B. das Zählen aufeinanderfolgender Zeichen und das Ändern des Arrays an Ort und Stelle.
3. Optimierung für Effizienz:Verwenden Sie effiziente Algorithmen und Datenstrukturen, um die zeitliche und räumliche Komplexität zu minimieren.
4. Gründlich testen:Testen Sie die Lösung mit verschiedenen Fällen, einschließlich Randfällen, um die Richtigkeit sicherzustellen.

Identifizieren ähnlicher Probleme:

1. String-Manipulation:

   • Probleme, bei denen Sie Zeichenfolgen basierend auf bestimmten Bedingungen ändern müssen.
   • Beispiel: Duplikate aus einer Zeichenfolge entfernen.

2. In-Place-Algorithmen:

   • Probleme, bei denen Vorgänge vor Ort mit begrenztem zusätzlichem Platz durchgeführt werden müssen.
   • Beispiel: Elemente aus einem Array ohne zusätzlichen Platz entfernen.

Abschluss:

• Das Problem der Komprimierung eines Zeichenarrays kann sowohl mit einem Brute-Force-Ansatz als auch mit einem optimierten In-Place-Ansatz effizient gelöst werden.
• Es ist entscheidend, das Problem zu verstehen und es in überschaubare Teile zu zerlegen.
• Durch die Verwendung effizienter Algorithmen wird sichergestellt, dass die Lösung für große Eingaben optimal ist.
• Tests mit verschiedenen Randfällen stellen die Robustheit sicher.
• Das Erkennen von Mustern in Problemen kann dabei helfen, ähnliche Lösungen auf andere Herausforderungen anzuwenden.

Durch das Üben solcher Probleme und Strategien können Sie Ihre Problemlösungsfähigkeiten verbessern und besser auf verschiedene Programmierherausforderungen vorbereitet sein.

Das obige ist der detaillierte Inhalt vonTypescript Coding Chronicles: String-Komprimierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!