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 Tag 23 "226. Binärbaum umkehren" ab Null
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Twitter Ich mache es.
Führen Sie zwei sortierte verkettete Listen zusammen und geben Sie eine neue Liste zurück.
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
Ich wollte es mit der iterativen Methode lösen, also poste ich dieses Mal zwei Methoden, rekursiv und iterativ.
Erstens ist die Wiederholung.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2:
return l1 or l2
if l1.val >= l2.val:
l2.next = self.mergeTwoLists(l1, l2.next)
return l2
else:
l1.next = self.mergeTwoLists(l1.next, l2)
return l1
# Runtime: 32 ms, faster than 89.62% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 13.8 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.
Ich bevorzuge Wiederholungen, weil sie einfach und zusammenhängend und sehr lesbar sind. Es ist auch einfacher zu schreiben.
Als nächstes folgt ein Beispiel für das Schreiben mit der iterativen Methode.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
temp = ans = ListNode(0)
while l1 or l2:
if l1 and l2:
if l1.val < l2.val:
ans.next = l1
l1 = l1.next
else:
ans.next = l2
l2 = l2.next
elif l1:
ans.next = l1
l1 = l1.next
elif l2:
ans.next = l2
l2 = l2.next
ans = ans.next
return temp.next
# Runtime: 28 ms, faster than 97.54% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 13.9 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.
Die Grundidee besteht darin, mit bedingter Verzweigung zu verarbeiten, während ein bestimmtes Element vorhanden ist. In diesem Beispiel wird die Verarbeitung fortgesetzt, während "l1" und "l2" von ListNode vorhanden sind. Wenn beide vorhanden sind, werden die Werte verglichen und der kleinere Wert wird "ans" zugewiesen, der schließlich zurückgegeben wird, und dann So wird es geschrieben, weil es ausreicht, das Element von ListNode, das keine Elemente enthält, um eins zurück zu verschieben.
Dies ist für jeden leicht zu verstehen, fühlt sich aber gleichzeitig etwas überflüssig an. Also habe ich es umgeschrieben.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
temp = ans = ListNode(0)
while l1 and l2:
if l1.val < l2.val:
ans.next = l1
l1 = l1.next
else:
ans.next = l2
l2 = l2.next
ans = ans.next
ans.next = l1 or l2
return temp.next
# Runtime: 36 ms, faster than 70.49% of Python3 online submissions for Merge Two Sorted Lists.
# Memory Usage: 14 MB, less than 6.61% of Python3 online submissions for Merge Two Sorted Lists.
Was sich geändert hat, ist, dass sich der Zustand der while-Anweisung von "oder" zu "und" geändert hat, und mit dieser Änderung.
ans.next = l1 or l2
Hinzugefügt. Auf diese Weise wurde der redundante Teil stark reduziert. Es wird verglichen, während sowohl "l1" als auch "l2" vorhanden sind, und wenn nur eines vorhanden ist, wird der Rest in derselben Reihenfolge ersetzt.
Wenn es eine gute Antwort gibt, werde ich sie hinzufügen.
Recommended Posts