[PYTHON] Let Code Day 35 "160. Intersection de deux listes liées" à partir de zéro

Aperçu

Il semble que des tests de codage soient menés à l'étranger lors d'entretiens d'ingénieurs, et dans de nombreux cas, l'essentiel est d'implémenter des fonctions et des classes spécifiques en fonction du thème.

En guise de contre-mesure, il semble qu'un site appelé Let Code prendra des mesures.

Un site qui forme une puissance algorithmique capable de résister aux tests de codage dont on parle très tôt.

Je pense qu'il vaut mieux avoir la puissance de l'algorithme d'un être humain, donc je vais résoudre le problème de manière irrégulière et écrire la méthode que j'ai pensé à ce moment-là sous forme de mémo.

Leetcode

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 34 "118. Pascal's Triangle" partant de zéro

En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.

Twitter Je le fais.

problème

160. Intersection of Two Linked Lists

C'est l'avant-dernière question de la question facile dans les 100 questions les plus appréciées.

Le problème est de trouver le nœud où commence la partie commune des deux listes concaténées unidirectionnelles.

Un exemple est expliqué dans la figure, et il n'est pas possible de l'afficher directement ici en raison de diverses circonstances, nous apprécierions donc que vous puissiez vérifier chacun d'eux.

Solution

Si vous écrivez ceci au début

# 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

Puisque le temps a expiré, j'ai essayé de réécrire pendant et plus tard dans la notation d'inclusion comme indiqué ci-dessous.

# 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.

Vous pouvez utiliser BruteForce, HashMap ou Two Pointer pour résoudre l'explication officielle de ce problème! Il est. Si vous êtes intéressé, je vous recommande de le vérifier.

Cette façon d'écrire est meilleure! Je l'ai écrit dans cette langue! Si vous avez des questions, n'hésitez pas à commenter.