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.
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Letztes Mal Leet Code Day4 ab Null "938. Bereichssumme von BST"
1266. Minimum Time Visiting All Points
Da die Liste mehrere x- und y-Achsenkoordinaten enthält, besteht das Problem darin, die kürzeste Zeit zu finden, um alle Koordinaten zu besuchen.
Als Regel, Sie können eine Einheit vertikal, horizontal oder diagonal pro Sekunde bewegen. Die Koordinaten müssen in der angegebenen Reihenfolge erreicht werden Es gibt eine Einschränkung.
In Beispiel 1 wissen Sie möglicherweise nicht, wie Sie die kürzeste Route in der Grafik finden, aber als wichtige Idee, um dieses Problem vorerst zu lösen, finden Sie die kürzeste Route. Der Punkt ist, dass Sie einfach vom numerischen Wert mit der größeren Differenz von jeder gegebenen Koordinate subtrahieren können. Das Wichtigste dabei ist nicht, den Unterschied so zu bekommen, wie er ist, sondern den absoluten Wert.
Python hat eine eingebaute Funktion "abs ()", so dass Sie es einfach verwenden können.
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
sec = 0
x1,y1 = points.pop()
while points:
x2,y2 = points.pop()
sec += max(abs(x2-x1),abs(y2-y1))
x1,y1 = x2,y2
return sec
# Runtime: 56 ms, faster than 84.71% of Python3 online submissions for Minimum Time Visiting All Points.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Minimum Time Visiting All Points.
Erstens ist "sec" eine Abkürzung für "second" und bereitet eine Variable zum Hinzufügen der Reisezeit vor.
Und diesmal habe ich den Pop des Stapels benutzt. Python Pop entfernt das nachfolgende (letzte) Element, wenn kein Argument angegeben ist.
Im Testfall der Antwort wird "[[1,1], [3,4], [-1,0]]" verwendet, daher wird in diesem Fall x1, y1 durch -1,0 ersetzt. 3 und 4 sind x2 bzw. y2 zugeordnet. Verwenden Sie dann nach dem Subtrahieren von x1 von x2 und y1 von y2 die Funktion max, um den größeren Wert zu extrahieren und ihn "sec" zuzuweisen. Danach werden x2 und y2 x1 und y1 zugewiesen, eine Schleife ausgeführt, bis die Anzahl der Elemente von Punkten erschöpft ist, und schließlich wird "sec", die die Summe der Maximalwerte der Differenz ist, zurückgegeben.
Ich denke, die Antwort ist einfach wie oben.
Sie können auch eine Antwort mit einem for-Satz geben.
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
sec = 0
current = points[0]
for point in points[1:]:
sec += max(abs(current[0] - point[0]), abs(current[1] - point[1]))
current = point
return sec
# Runtime: 64 ms, faster than 32.15% of Python3 online submissions for Minimum Time Visiting All Points.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Minimum Time Visiting All Points.
Dies ist jedoch etwas langsam.
Es wäre schön, Ersteres zu studieren, wenn Sie auch den Stapel studieren würden.
Recommended Posts