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 de mettre en œuvre 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 à des 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.
Table de codes Leet commençant à zéro
Dernière fois Leet Code Day 23 "226. Invert Binary Tree" à partir de zéro
En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.
Twitter Je le fais.
Étant donné deux listes concaténées triées, fusionnez-les et renvoyez une nouvelle liste.
Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4
Je voulais le résoudre en utilisant la méthode itérative, donc cette fois je poste deux méthodes, récursive et itérative.
Le premier est la récurrence.
# 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.
Je préfère la récurrence car elle est simple, cohérente et très lisible. C'est aussi plus facile à écrire.
Voici un exemple d'écriture avec la méthode itérative.
# 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.
L'idée de base est de traiter avec un branchement conditionnel alors qu'un élément spécifique existe. Dans cet exemple, le traitement se poursuit pendant que les ListNodes «l1» et «l2» existent, et si les deux existent, les valeurs sont comparées et la plus petite est finalement renvoyée. C'est ainsi que cela s'écrit car il suffit de reculer d'un élément l'élément de ListNode qui n'a aucun élément.
C'est facile à comprendre pour tout le monde, mais en même temps, cela semble un peu redondant. Alors je l'ai réécrit.
# 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.
Ce qui a changé, c'est que la condition de l'instruction while est passée de «ou» à «et», et avec ce changement.
ans.next = l1 or l2
Est ajouté. En faisant cela, la partie redondante a été considérablement réduite. Il comparera tant que "l1" et "l2" sont présents, et si un seul est présent, il remplacera le reste dans le même ordre.
S'il y a une bonne réponse, je l'ajouterai.
Recommended Posts