Geben Sie eine Lauflänge codierte Zeichenfolge an, z. B. "A3B1C2D1E1", dekodieren Sie die Zeichenfolge an Ort und Stelle. Die Antwort für die codierte Zeichenfolge ist "AAABCCDE". Es wird angenommen, dass das codierte Array groß genug ist, um die decodierte Zeichenfolge aufzunehmen, d. H., Sie können annehmen, dass die Array-Größe = MAX [Länge (codiertes Signal), Länge (decodiertes Signal)].
Dies scheint nicht trivial zu sein, da nur die Dekodierung von A3 als "AAA" zum Überschreiben von "B" der ursprünglichen Zeichenkette führt.
Man kann auch nicht annehmen, dass die dekodierte Kette immer größer ist als die kodierte Kette. ZB: Codierte Zeichenkette - 'A1B1', Decodierte Zeichenkette ist 'AB'. Irgendwelche Gedanken?
Und es wird immer ein Buchstaben-Ziffern-Paar sein, d. h. Sie werden nicht aufgefordert, 0515 in 0000055555
Dies ist eine sehr vage Frage, obwohl es nicht besonders schwierig ist, wenn Sie darüber nachdenken. Wie du sagst, dekodiert 1 als 1 und schreibt sie einfach an Ort und Stelle überschreibt die Zeichen 2 und A3BCCDE . Warum also nicht einfach die weiter vorne im Array bewegen?
Wenn Sie zum Beispiel %code% gelesen haben, wissen Sie, dass Sie Platz für ein zusätzliches Zeichen benötigen, wenn es %code% war, würden Sie zwei brauchen, und so weiter. Um dies zu erreichen, würden Sie das Ende der Zeichenfolge im Array finden (tun Sie dies im Voraus und speichern Sie den Index).
Wiederholen Sie die Schleife und verschieben Sie die Zeichen in ihre neuen Slots:
Um zu beginnen: %code% Haben Sie eine Variable namens %code% , die den Index 5 speichert, d. H. Den letzten, nicht leeren Eintrag.
Sie würden das erste Paar lesen, indem Sie eine Variable namens %code% verwenden, um Ihre aktuelle Position zu speichern - also nach dem Einlesen von %code% und %code% wäre es auf 1 gesetzt (der Slot mit der 3 ).
Pseudocode für den Umzug:
var n = Feld [Cursor] - 2; // n = 1, die 3 aus A3 und dann minus 2, um das Paar zu berücksichtigen.
für (i = Ende; i & gt; Cursor; i ++) { Array [i + n] = Array [i]; }
Dies würde dich verlassen mit:
%code%
Jetzt ist %code% schon einmal da, also wollen Sie jetzt %code% %code% beginnend mit dem in %code% gespeicherten Index schreiben:
%Vor%Geben:
%code%
Dann zeigen Sie auf den Anfang des nächsten Wertepaars und sind bereit, erneut zu gehen. Mir ist klar, dass es in dieser Antwort einige Lücken gibt, obwohl dies beabsichtigt ist, da es sich um eine Interviewfrage handelt! In den Randfällen, die Sie beispielsweise %code% angegeben haben, benötigen Sie eine andere Schleife, um nachfolgende Zeichen rückwärts statt vorwärts zu bewegen.
Geben Sie eine Lauflänge codierte Zeichenfolge an, z. B. "A3B1C2D1E1", dekodieren Sie die Zeichenfolge an Ort und Stelle. Die Antwort für die codierte Zeichenfolge ist "AAABCCDE". Es wird angenommen, dass das codierte Array groß genug ist, um die decodierte Zeichenfolge aufzunehmen, d. H., Sie können annehmen, dass die Array-Größe = MAX [Länge (codiertes Signal), Länge (decodiertes Signal)].
Dies scheint nicht trivial zu sein, da nur die Dekodierung von A3 als "AAA" zum Überschreiben von "B" der ursprünglichen Zeichenkette führt.
Man kann auch nicht annehmen, dass die dekodierte Kette immer größer ist als die kodierte Kette. ZB: Codierte Zeichenkette - 'A1B1', Decodierte Zeichenkette ist 'AB'. Irgendwelche Gedanken?
Und es wird immer ein Buchstaben-Ziffern-Paar sein, d. h. Sie werden nicht aufgefordert, %code% in %code%
umzuwandelnEs folgt eine weitere O (n ^ 2) -Lösung.
Da die Komplexität der Antwort nicht begrenzt ist, scheint diese einfache Lösung perfekt zu funktionieren.
%Vor%Wo:
Die freie Speicherplatzgröße ist die Anzahl der leeren Elemente im Array.
Ein erweiterbares Element ist ein Element, das:
%Vor%Der Punkt ist, dass im Prozess des Erreichens von dem Lauflängencode zu der expandierten Zeichenkette bei jedem Schritt mindestens ein Element, das erweitert werden kann (leicht zu beweisen).
Wenn wir es noch nicht wissen, sollten wir zuerst die Ziffern durchgehen, um die Länge der dekodierten Zeichenkette zu berechnen.
Es wird immer ein Buchstaben-Ziffern-Paar sein, daher können Sie das %code% s aus der Zeichenkette ohne jegliche Verwirrung löschen.
%Vor%wird
%Vor%Hier ist etwas Code in C ++, um die %code% s aus der Zeichenkette (O (n) -Komplexität) zu entfernen.
%Vor%Nun ist diese Zeichenfolge garantiert kürzer oder gleich lang wie die endgültige decodierte Zeichenfolge. Wir können diesen Anspruch auf die ursprüngliche Zeichenfolge nicht geltend machen, aber wir können es über diese modifizierte Zeichenfolge machen.
(Ein optionaler, trivialer Schritt besteht jetzt darin, jedes %code% durch den vorherigen Buchstaben zu ersetzen. %code% , aber das müssen wir nicht tun).
Jetzt können wir vom Ende anfangen zu arbeiten. Wir haben die Länge der dekodierten Zeichenfolge bereits berechnet und wissen daher genau, wo das letzte Zeichen sein wird. Wir können einfach die Zeichen vom Ende unserer kurzen Zeichenfolge an ihren endgültigen Ort kopieren.
Wenn wir während dieses Kopiervorgangs von rechts nach links auf eine Ziffer stoßen, müssen wir mehrere Kopien des Buchstabens erstellen, der sich genau links von der Ziffer befindet. Sie könnten befürchten, dass dies zu viele Daten überschreiben könnte. Aber wir haben früher bewiesen, dass unsere codierte Zeichenkette oder eine Teilzeichenkette davon niemals länger als ihre entsprechende decodierte Zeichenkette sein wird; das bedeutet, dass immer genug Platz ist.
Die folgende Lösung ist %code% und in-place. Der Algorithmus sollte nicht auf Speicher zugreifen, den er nicht lesen und schreiben sollte. Ich habe ein Debugging durchgeführt, und es scheint korrekt zu den Beispieltests zu passen, die ich fütterte.
Übersicht auf hoher Ebene:
Die folgende Lösung ist O(n) und in-place. Der Algorithmus sollte nicht auf Speicher zugreifen, den er nicht lesen und schreiben sollte. Ich habe ein Debugging durchgeführt, und es scheint korrekt zu den Beispieltests zu passen, die ich fütterte.
Übersicht auf hoher Ebene:
Dies ist eine sehr vage Frage, obwohl es nicht besonders schwierig ist, wenn Sie darüber nachdenken. Wie du sagst, dekodiert A3 als AAA und schreibt sie einfach an Ort und Stelle überschreibt die Zeichen B und 1 . Warum also nicht einfach die weiter vorne im Array bewegen?
Wenn Sie zum Beispiel A3 gelesen haben, wissen Sie, dass Sie Platz für ein zusätzliches Zeichen benötigen, wenn es A4 war, würden Sie zwei brauchen, und so weiter. Um dies zu erreichen, würden Sie das Ende der Zeichenfolge im Array finden (tun Sie dies im Voraus und speichern Sie den Index).
Wiederholen Sie die Schleife und verschieben Sie die Zeichen in ihre neuen Slots:
Um zu beginnen: A|3|B|1|C|2|||||||
Haben Sie eine Variable namens end , die den Index 5 speichert, d. H. Den letzten, nicht leeren Eintrag.
Sie würden das erste Paar lesen, indem Sie eine Variable namens cursor verwenden, um Ihre aktuelle Position zu speichern - also nach dem Einlesen von A und 3 wäre es auf 1 gesetzt (der Slot mit der 3 ).
Pseudocode für den Umzug:
var n = Feld [Cursor] - 2; // n = 1, die 3 aus A3 und dann minus 2, um das Paar zu berücksichtigen.
für (i = Ende; i & gt; Cursor; i ++) { Array [i + n] = Array [i]; }
Dies würde dich verlassen mit:
A|3|A|3|B|1|C|2|||||
Jetzt ist A schon einmal da, also wollen Sie jetzt n + 1 A beginnend mit dem in cursor gespeicherten Index schreiben:
Geben:
A|A|A|A|B|1|C|2|||||
Dann zeigen Sie auf den Anfang des nächsten Wertepaars und sind bereit, erneut zu gehen. Mir ist klar, dass es in dieser Antwort einige Lücken gibt, obwohl dies beabsichtigt ist, da es sich um eine Interviewfrage handelt! In den Randfällen, die Sie beispielsweise A1B1 angegeben haben, benötigen Sie eine andere Schleife, um nachfolgende Zeichen rückwärts statt vorwärts zu bewegen.
Es folgt eine weitere O (n ^ 2) -Lösung.
Da die Komplexität der Antwort nicht begrenzt ist, scheint diese einfache Lösung perfekt zu funktionieren.
%Vor%Wo:
Die freie Speicherplatzgröße ist die Anzahl der leeren Elemente im Array.
Ein erweiterbares Element ist ein Element, das:
%Vor%Der Punkt ist, dass im Prozess des Erreichens von dem Lauflängencode zu der expandierten Zeichenkette bei jedem Schritt mindestens ein Element, das erweitert werden kann (leicht zu beweisen).
Tags und Links c encoding compression decompression