Buchstabenverschiebung II

2381. Buchstabenverschiebung II

Schwierigkeit:Mittel

Themen:Array, String, Präfixsumme

Sie erhalten eine Zeichenfolge s aus englischen Kleinbuchstaben und ein 2D-Integer-Array „shifts“, wobei „shifts[i] = [start_i, end_i, Direction_{i]. Für jedes i} verschiebendie Zeichen in s vom Indexanfangi _{zum Indexende}i ₍einschließlich) nach vorne, wenn Richtungi _{= 1, oder verschieben Sie die Zeichen nach hinten, wenn Richtung}i _{= 0.}

Ein Zeichen

nach vorne zu verschieben bedeutet, es durch den nächsten Buchstaben im Alphabet zu ersetzen (umbrechend, sodass aus „z“ „a“ wird). Ebenso bedeutet das Verschieben eines Zeichens nach hinten, dass es durch den vorherigen Buchstaben im Alphabet ersetzt wird (umbrochen, sodass aus „a“ „z“ wird).

Gib

die letzte Zeichenfolge zurück, nachdem alle derartigen Verschiebungen zu s angewendet wurden.

Beispiel 1:

• Eingabe: s = „abc“, Verschiebungen = [[0,1,0],[1,2,1],[0,2,1]]
• Ausgabe: „Ass“
• Erklärung: Verschieben Sie zunächst die Zeichen von Index 0 nach Index 1 nach hinten. Jetzt ist s = „zac“.
  Zweitens verschieben Sie die Zeichen von Index 1 nach Index 2 nach vorne. Jetzt s = "zbd".
  Zuletzt verschieben Sie die Zeichen von Index 0 nach Index 2 nach vorne. Jetzt ist s = „Ass“.

Beispiel 2:

• Eingabe: s = "dztz", Verschiebungen = [[0,0,0],[1,1,1]]
• Ausgabe: „catz“
• Erklärung: Verschieben Sie zunächst die Zeichen von Index 0 nach Index 0 nach hinten. Jetzt ist s = „cztz“.
  Zuletzt verschieben Sie die Zeichen von Index 1 nach Index 1 nach vorne. Jetzt ist s = „catz“.

Einschränkungen:

1 4 shifts[i].length == 3
0 i i 0 i s besteht aus englischen Kleinbuchstaben.

Hinweis:

Anstatt jeden Charakter in jeder Schicht zu verschieben, könnten Sie den Überblick darüber behalten, welche Charaktere über alle Schichten hinweg um wie viel verschoben werden?
Versuchen Sie, den Beginn und das Ende jeder Schicht zu markieren, und führen Sie dann eine Präfixsumme der Schichten durch.

Lösung:

Wir müssen vermeiden, die Zeichen bei jeder Verschiebung einzeln zu verschieben, da dies für große Eingaben zu langsam wäre. Stattdessen können wir einen optimaleren Ansatz verwenden, indem wir eine Technik namens

Präfixsumme nutzen.

Schritte:

1. Markieren Sie die Verschiebungsgrenzen: Anstatt jedes Zeichen sofort zu verschieben, markieren wir die Verschiebungseffekte am Anfang und Ende jedes Bereichs.
2. Präfixsumme anwenden: Nachdem wir alle Verschiebungen markiert haben, können wir die kumulativen Verschiebungen bei jedem Zeichen mithilfe der Präfixsummentechnik berechnen. Dadurch können wir die kumulativen Verschiebungen effizient auf jedes Zeichen anwenden.
3. Führen Sie die Verschiebungen durch: Sobald wir die Gesamtverschiebung für jedes Zeichen kennen, können wir die Verschiebungen (entweder vorwärts oder rückwärts) auf die Zeichenfolge anwenden.

Lassen Sie uns diese Lösung in PHP implementieren: 2381. Buchstabenverschiebung II

<?php /**
 * @param String $s
 * @param Integer[][] $shifts
 * @return String
 */
function shiftingLetters($s, $shifts) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test the function
$s1 = "abc";
$shifts1 = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
echo shiftingLetters($s1, $shifts1) . "\n";  // Output: "ace"

$s2 = "dztz";
$shifts2 = [[0, 0, 0], [1, 1, 1]];
echo shiftingLetters($s2, $shifts2) . "\n";  // Output: "catz"
?>

Erläuterung:

1. Für jede Schicht [Anfang, Ende, Richtung] erhöhen wir ein Schichtarray am Anfang und dekrementieren am Ende 1. Dadurch können wir den Anfang und das Ende des Schichtbereichs verfolgen.
2. Nachdem wir alle Verschiebungen verarbeitet haben, wenden wir eine Präfixsumme auf das Verschiebungsarray an, um die kumulative Verschiebung an jedem Index zu erhalten.
3. Zuletzt wenden wir die kumulative Verschiebung auf jedes Zeichen in der Zeichenfolge an.

Erklärung des Codes:

1. Eingabeanalyse: Wir konvertieren die Eingabezeichenfolge s zur einfacheren Handhabung in ein Array von Zeichen.
2. Shift Array: Wir initialisieren ein Shift Array der Größe n 1 auf Null. Dieses Array wird verwendet, um die Verschiebungseffekte zu verfolgen. Für jede Schicht [Start, Ende, Richtung] passen wir die Werte bei Schicht[Start] und Schicht[Ende 1] an, um den Beginn und das Ende der Schicht widerzuspiegeln.
3. Präfixsumme: Wir berechnen die Gesamtverschiebung für jedes Zeichen, indem wir über das Verschiebungsarray iterieren und eine kumulative Summe der Verschiebungen beibehalten.
4. Zeichenverschiebung: Für jedes Zeichen in der Zeichenfolge berechnen wir das endgültig verschobene Zeichen mithilfe der Formel (ord(currentChar) - ord('a') totalShift) % 26, was die kreisförmige Natur des Zeichens berücksichtigt Alphabet.
5. Rückgabeergebnis: Die endgültige Zeichenfolge wird erhalten, indem das Zeichenarray zurück in eine Zeichenfolge umgewandelt und zurückgegeben wird.

Zeitkomplexität:

• Zeitkomplexität: O(n·m), wobei n die Länge der Zeichenfolge s und m die Anzahl der Verschiebungen ist. Dies liegt daran, dass wir die Zeichenfolge und die Liste der Schichten jeweils einmal durchlaufen.
• Raumkomplexität: O(n), wobei n die Länge der Zeichenfolge s ist, aufgrund des für das Schiebearray benötigten Platzes.

Diese Lösung bewältigt das Problem effizient, selbst wenn die Obergrenzen der Eingabebeschränkungen gelten.

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