Das Problem wird wie folgt angegeben: Bei einer Zeichenfolge, die nur die Ziffern 0-9 und einen Zielwert enthält, geben Sie alle Ausdrücke zurück, die durch Hinzufügen einiger binärer Operatoren (+, - oder *) zwischen den Ziffern erstellt wurden der Zielwert. In einigen Fällen gibt es möglicherweise keine binären Operatoren, die gültige Ausdrücke erstellen. In diesem Fall sollte die Funktion ein leeres Array zurückgeben. Die Zahlen in den neuen Ausdrücken dürfen keine führenden Nullen enthalten.
Die Funktion sollte alle gültigen Ausdrücke, die ausgewertet werden sollen, lexikografisch sortiert zurückgeben.
Zum Beispiel:
digits = "123" und target = 6 sollten zurückkehren: ["1*2*3", "1+2+3"]
Mein aktueller Algorithmus ist unten. Es ist ein bisschen langsam, also suche ich nach einem effizienteren Weg, um das Problem anzugehen. Mein derzeitiger Algorithmus erzeugt alle Kombinationen der Operanden und Operatoren. Für das obige Beispiel wird
erzeugtOperanden:
%Vor%Operatoren:
%Vor%Es kombiniert dann alle möglichen Kombinationen von Operanden und Operatoren und wertet jede aus.
Die Ziffern haben eine Beschränkung von 2 ≤ digits.length ≤ 10. Also ist es nicht so schlimm, aber mit diesem Algo dauert es etwa 4,3 Sekunden für eine Ziffer mit der Länge 10, wo es nur 4 Sekunden (maximal) dauern sollte.
Ich habe auch versucht, die Funktion eval () mit den folgenden Alternativen zu beschleunigen:
%Vor%oder
%Vor%oder
%Vor%Alle von ihnen benötigen immer noch etwa die gleiche Zeit mit Python 3.
Code:
%Vor%Code mit einer Taschenrechnerfunktion (no eval ()), hat fast die gleiche Geschwindigkeit:
%Vor%Mit dieser Art von Programmierproblemen beginne ich, indem ich versuche, die Fragen zu beantworten:
Probleme, die wie kleine Programmiersprachen aussehen, lassen mich eher an Lisp denken. Das Problem besteht darin, uns zu bitten, die Serie zu generieren:
%Vor% Ein binärer Ausdruck im Grunde ein 3-Tupel von (operator, left, right) , wobei links und rechts auch Ausdrücke sein können. Die Reihenfolge der Komponenten spielt keine Rolle. Python hat Tupel und im Modul operator Funktionen für die verschiedenen binären Ops. Also würde ich planen, Ausdrücke in der folgenden Form zu erstellen:
Dies kann dann mit einer (meist) einfachen rekursiven Funktion ausgewertet werden:
%Vor%Aus der Problembeschreibung geht hervor, dass es eine exponentielle Anzahl möglicher Ausdrücke pro eingegebener Ziffer geben wird. Können wir einige dieser Teile eliminieren, indem wir alle Permutationen erstellen?
Nehmen Sie zum Beispiel eine sechsstellige Eingabe und das Zielergebnis 5 . Stellen Sie sich beim Erstellen der Permutationen vor, dass der folgende Ausdruck aus den ersten vier Ziffern erstellt wurde und zwei noch zu behandeln sind:
3696 ist eine große Zahl, ist einer der Ausdrücke von diesem Punkt sogar in der Lage, ein Ergebnis von nur 5 zu erhalten? Können wir sie komplett überspringen?
Leider können die Ziffern am Ende noch große Änderungen vornehmen:
%Vor%Es kann einige Zweige geben, die wir vermeiden könnten, aber wir müssen die meisten Ausdrücke berücksichtigen.
Okay, vorausgesetzt, wir müssen tatsächlich das Ergebnis einer sehr großen Anzahl von Ausdrücken erhalten, gibt es eine andere Möglichkeit, Aufwand zu sparen?
Stellen wir uns vor, wir sind Teilweise durch die Erzeugung einer Sequenz mit diesen drei abschließenden Ausdrücken, die nacheinander erzeugt werden:
%Vor% Sie geben alle unterschiedliche Ergebnisse an, [12, 13, 11] , aber dieser innere Teil (- 8 (* 3 6)) ist derselbe und wird immer 12 sein. Unsere Lösung sollte versuchen, dies zu nutzen.
Für alle, die Spoiler brauchen, habe ich Filialen für Initialimplementierung , die jeden Ausdruck von oben berechnet, a eine kleine Änderung, die die Berechnung enthält , und eine letzte, die precomputes Ergebnisse , da die Ausdrücke generiert werden plus einige kleine Verbesserungen .
17.40s elapsed 6180k max mem Original von Frage 20.60s elapsed 6284k max mem ohne Bewertung von Frage 4.65s elapsed 5356k max mem my initial 2.71s elapsed 5316k max mem my memoised 1.50s elapsed 5356k max mem mein vorberechnetes Einige Anmerkungen zu meiner Implementierung. Die Funktion generate() erstellt die Kandidatenausdrücke, indem jeder Punkt in der Zeichenfolge berücksichtigt und die möglichen nächsten Zustände erstellt werden. Zum Beispiel bewegen beide den Marker zu Beginn und teilen die erste Zahl ab:
Jeder ausstehende Status wird an eine Liste gesendet, und die aktuelle, die berücksichtigt werden soll, wird jedes Mal durch die Schleife gelöscht. Von dem Zustand am Ende ausgehend, bewegen die nächsten Möglichkeiten den Marker erneut und teilen eine Zahl auf, um einen der drei Ausdrücke zu bilden.
%Vor%Ich habe bis jetzt eine Falte mit Operatorpräzedenz angegeben. Bei der Multiplikation müssen wir möglicherweise einen vorhandenen Ausdruck neu schreiben. Überlegen Sie:
%Vor% Für Addition und Subtraktion ist das in Ordnung, Ordnung spielt keine Rolle. % Co_de% muss jedoch vor 2 * 3 passieren. Kurz gesagt, wir müssen die Multiplikation nach innen schieben:
Es gibt gute Möglichkeiten, dies zu handhaben, indem Sie etwas mehr Informationen über Ihre Operationen speichern als nur die Funktion, um sie auszuführen. Für dieses Problem ist das nicht wirklich erforderlich, noch sind andere mögliche Transformationen wie das Kombinieren mehrerer Ausdrücke oder das Ausschließen irrelevanter Teile möglich.
Endgültiger Implementierungshinweis, nur um schwierig zu sein Ich habe sowohl die Richtung der Iteration als auch (anfangs) das Layout der Ausdrücke rückwärts gemacht.
Tags und Links python algorithm combinations