Interviewer hat in einem Interview eine Frage gestellt, um schnell & amp; effizienter Algorithmus für die untere Funktion,
Problem: Schreiben Sie eine Funktion, um eine gegebene Zeichenfolge für die unten angegebenen Regeln & amp; erzeuge die letzte analysierte Zeichenkette als Ausgabe
schreibe eine Funktion, die einen String als Eingabe akzeptiert, Stringlänge liegt zwischen [0..2000000000]
string sollte nur aus 'A', 'B' & amp; 'C' Zeichen wie 'AAA', 'ABCABC', 'AAAABBBBABAAACCCA'
1) "AB" - & gt; "AA"
2) "AC" - & gt; "AA"
3) "AA" - & gt; 'A'
4) "CC" - & gt; "C"
5) "BC" - & gt; "BB"
6) "BB" - & gt; 'B'
Übernehmen Sie alle oben genannten 6 Regeln nach dem Zufallsprinzip auf jeden gegebenen String und machen Sie den letzten transformierten String als Ausgabe
Zum Beispiel ist die Eingabe in Function: 'ABCAAB' string
ABCAAB - & gt; AACAAB [AB = AA]
AACAAB - & gt; ACAAB [AA = A]
ACAAB - & gt; AAAAB [AC = AA]
AAAAB - & gt; AAAB [AA = A]
AAAB - & gt; AAB [AA = A]
AAB - & gt; AB [AA = A]
AB - & gt; AA [AB = AA]
AA - & gt; A [AA = A]
Endergebnis: 'A'
Weil wir jetzt keine Regeln mehr auf die Zeichenfolge anwenden können.
Meine Antwort war wie (Pseudocode):
%Vor%Kann jemand einen besseren Algorithmus vorschlagen? Ansatz für das oben genannte Problem?
Regeln 1 bis 3 werden jedes Zeichen nach einem A. verwerfen
Die Regeln 5 und 6 verwerfen B und C nach einem B.
Regel 4 verwirft jedes C nach einem C. Die Reihenfolge der Substitutionen spielt keine Rolle.
Nach der Verarbeitung wird der String also C, CB, CA, CBA, B, BA, A sein.
Ein einzelner Scan der Zeichenfolge genügt. Wenn du ein C siehst, behalte es und überspringe die nächsten C's; Wenn du ein B siehst, behalte es und überspringe die nächsten B's. dann, wenn du ein A siehst, halte es und hör auf.
Das angegebene Beispiel ABCAAB liefert sofort A.
Lösungen mit expliziter Anwendung der Regeln und Mehrfachdurchgänge sind inakzeptabel, da ihr Verhalten O(N²) oder sogar O(N³) sein kann, während N=2000000000 .
Die Antwort von Yves Daoust ist richtig, macht keinen Sinn, es zu simulieren. Scheint wie eine Trickfrage und das solltest du erkennen und das Verhalten verstehen und direkt umsetzen.
Yves 'Methode funktioniert, aber hier ist eine tatsächliche Implementierung eines ähnlichen:
%Vor% Ich suche nach dem ersten 'A' und suche dann nach einem 'B' links davon (oder in der ganzen Zeichenfolge, wenn es kein 'A' gibt). Das sagt mir, ob 'B' und 'A' in die Ausgabe gehören. Für 'C' muss ich nur den Anfang der Zeichenfolge überprüfen. Während ich die gesamte Saite möglicherweise zweimal scanne, anstatt nur einmal, wie Yves es vorschlägt, macht es die find -Funktion ziemlich schnell, ungefähr 100 mal schneller, als nur die Saite "von Hand" zu durchlaufen und nur nach einem 'A' zu suchen. (was nur am Ende meines Teststrings ist):
Sie können dies mit nur einem Scan tun, indem Sie lstrip('C') verwenden, um das erste Nicht-C-Zeichen zu finden, und zwar schneller als von Hand, aber mit zusätzlichem Speicher und immer noch langsamer als find :
Reguläre Ausdrücke könnten das wahrscheinlich auch tun, aber selbst wenn ich nur nach dem 'A' suche, dauert es länger als mein ganzes transform :