Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.
Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.
Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.
Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.
Letztes Mal Leet Code Day24 ab Null "21. Zwei sortierte Listen zusammenführen"
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Twitter Ich mache es.
70. Climbing Stairs Der Schwierigkeitsgrad ist einfach. Auszug aus den 100 beliebtesten Fragen.
Ich denke, dies ist ein bekanntes Problem für diejenigen, die die Junior High School Prüfung abgelegt haben. Eigentlich gibt es eine sehr einfache Lösung, aber ich werde es in der Lösung erklären.
Wenn Sie die Treppe hinaufsteigen, können Sie ein oder zwei Stufen hinaufsteigen. Beantworten Sie angesichts der natürlichen Zahl "n" bitte, wie viele Wege Sie nach oben gelangen können.
Example 1:
Input: 2 output: 2
Im Fall von 2 wird 2 zurückgegeben, da es eine Methode zum Klettern von 2 Stufen auf einer Strecke und eine Methode zum zweimaligen Klettern von 1 Stufe gibt.
Example 2:
Input: 3 Output: 3
Im Fall von 3 wird 3 zurückgegeben, da es drei Methoden gibt: einen Schritt nach dem anderen wiederholen, einen Schritt nach oben und zwei Schritte nach oben und zwei Schritte nach oben und einen Schritt nach oben.
Tatsächlich ist dies ein Problem mit der Fibonacci-Sequenz. Möglicherweise haben Sie es gesehen, als Sie die Anzahl der Fälle untersucht haben.
Die Fibonacci-Zahlenfolge ist übrigens １,１,２,３,５,８,１３,２１,３４,５５, Und so weiter ist es eine Zahlenfolge, in der die Summe der beiden vorherigen Zahlen zur nächsten Zahl wird.
Betrachten wir den Fall, in dem es wie im Beispiel drei Schritte gibt. In diesem Fall kommt es auf den Fall in der ersten Phase an. Es gibt ein Muster, einen oder zwei Schritte zu klettern. Wenn Sie zwei Stufen erklimmen, haben Sie unweigerlich eine Option, da nur noch eine Stufe übrig ist. Wenn Sie dagegen 1 auswählen, bleiben 2 Schritte übrig, dh 2 Möglichkeiten, wie im Beispiel gezeigt. Die Summe dieser Additionen ist die Antwort für jeden Fall, und dies ist ein typisches Beispiel für die oben beschriebene Fibonacci-Sequenz.
Versuchen Sie auch andere Zahlen. Nehmen wir an, es hat 4 Schritte.
Wählen Sie dann zuerst den 1. Schritt und den 2. Schritt. Der erste ist der Fall von 1 Schritt, der Rest sind 3 Schritte. Mit anderen Worten, Sie können die drei Möglichkeiten der vorherigen drei Schritte unverändert verwenden. Bei 2 Schritten beträgt der Rest 2 Schritte. Mit anderen Worten, es gibt zwei Möglichkeiten. Es gibt 3 Wege + 2 Wege, also gibt es 5 Wege.
Wenn ein Schritt hinzugefügt wird, erhöht er sich auf 8, und wenn er um einen weiteren Schritt erhöht wird, erhöht er sich auf 13 ... und so weiter.
Sobald Sie die Struktur dieses Zusatzes verstanden haben, müssen Sie nur noch das Gesetz kodieren.
Als einfaches Beispiel
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
num1, num2 = 0, 1
for i in range(n):
num1, num2 = num2, num1+num2
return num2
# Runtime: 32 ms, faster than 39.40% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.7 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
Dies ist die allgemeine Lösung. Als ich mir die Diskussion ansah, gab es jedoch einen schnelleren Weg, sie zu schreiben.
from functools import lru_cache
class Solution:
@lru_cache(None)
def climbStairs(self, n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
# Runtime: 24 ms, faster than 91.08% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
Es ist wirklich schnell ...
Was ist übrigens "lru_cache"? Also habe ich es leise im [offiziellen Dokument] nachgeschlagen (https://docs.python.org/ja/3/library/functools.html).
@functools.lru_cache(user_function) @functools.lru_cache(maxsize=128, typed=False) Ein Dekorateur, der eine Funktion in ein aufrufbares Objekt für ein Memorandum einbindet und die letzten Aufrufe maximal speichert. Sie können Zeit sparen, wenn Sie regelmäßig teure Funktionen oder Funktionen, die an E / A gebunden sind, mit denselben Argumenten aufrufen.
Da zum Zwischenspeichern der Ergebnisse ein Wörterbuch verwendet wird, müssen die Positions- und Schlüsselwortargumente der Funktion hashbar sein.
Wenn die Argumentmuster unterschiedlich sind, werden sie als unterschiedliche Aufrufe betrachtet und sind separate Cache-Einträge. Zum Beispiel haben f (a = 1, b = 2) und f (b = 2, a = 1) unterschiedliche Reihenfolge von Schlüsselwortargumenten, was zu zwei separaten Cache-Einträgen führt. .....
Der LRU-Cache (zuletzt verwendet) ist am effizientesten, wenn der letzte Anruf am wahrscheinlichsten erneut aufgerufen wird (z. B. ändern sich die beliebtesten Artikel auf dem Nachrichtenserver in der Regel täglich). .. Die Beschränkung der Cache-Größe stellt sicher, dass der Cache nicht über die Grenzen langfristiger Prozesse wie Webserver hinaus wächst.
Im Allgemeinen sollte der LRU-Cache nur verwendet werden, wenn Sie den zuvor berechneten Wert wiederverwenden möchten. Daher ist es nicht sinnvoll, Funktionen mit Nebenwirkungen zwischenzuspeichern, Funktionen, bei denen Sie für jeden Aufruf ein separates veränderbares Objekt erstellen müssen, und unreine Funktionen wie time () und random ().
Mit anderen Worten, es scheint, dass das Ergebnis der aufgerufenen Funktion mithilfe eines Wörterbuchs zwischengespeichert wird. Wenn also das zwischengespeicherte Ergebnis auch beim letzten Aufruf aufgerufen wird, erhöht sich die Effizienz zum Zeitpunkt der Ausführung.
Ich wusste es nicht, also habe ich viel gelernt, aber es ist wichtig, die Diskussion zu sehen.
Recommended Posts