[PYTHON] Lassen Sie Code Tag 35 "160. Schnittpunkt zweier verknüpfter Listen" von vorne beginnen

Überblick

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.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Day 34 "118. Pascals Dreieck" ab Null

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Twitter Ich mache es.

Problem

160. Intersection of Two Linked Lists

Dies ist die vorletzte Frage der Easy-Frage in den Top 100 Liked Questions.

Das Problem besteht darin, den Knoten zu finden, an dem der gemeinsame Teil der beiden unidirektionalen verketteten Listen beginnt.

In der Abbildung wird ein Beispiel erläutert, das aufgrund verschiedener Umstände nicht direkt hier veröffentlicht werden kann. Wir würden uns freuen, wenn Sie jedes Beispiel überprüfen könnten.

Lösung

Wenn Sie dies zuerst schreiben

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        
        LNA = headA
        LNB = headB
        while LNA != LNB:
            if LNA == None:
                LNA = headB
            else:
                LNA.next
            
            if LNB == None:
                LNB == headA
            else:
                LNB.next
        return LNA
# Time Limit Exceeded

Da die Zeit abgelaufen ist, habe ich versucht, während und später in der Einschlussnotation wie unten gezeigt neu zu schreiben.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        if headA == None or headB == None:
            return None
        
        LNA = headA
        LNB = headB
        while LNA != LNB:
            LNA = headB if LNA == None else LNA.next
            LNB = headA if LNB == None else LNB.next
        return LNA
# Runtime: 168 ms, faster than 75.08% of Python3 online submissions for Intersection of Two Linked Lists.
# Memory Usage: 29.1 MB, less than 100.00% of Python3 online submissions for Intersection of Two Linked Lists.

Sie können BruteForce, HashMap oder Two Pointer verwenden, um die offizielle Erklärung dieses Problems zu lösen! Es ist. Wenn Sie interessiert sind, empfehle ich Ihnen, es zu überprüfen.

Diese Art zu schreiben ist besser! Ich habe es in dieser Sprache geschrieben! Wenn Sie Fragen haben, können Sie diese gerne kommentieren.