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 Day21 à partir de zéro "448. Find All Numbers Disappeared in an Array"
En gros, je voudrais résoudre l'acceptation facile par ordre décroissant.
Twitter Je le fais.
Le niveau de difficulté est facile. Extrait des 100 questions les plus appréciées.
C'est un problème qui nécessite des connaissances de base sur les listes chaînées.
Étant donné une liste concaténée, déterminez si elle contient un cycle.
Pour représenter la circulation de la liste concaténée spécifiée, utilisez l'entier pos, qui se termine par la position de la liste concaténée (à partir de 0). Si «pos» vaut -1, on suppose qu'il n'y a pas de circulation.
Example1
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where tail connects to the second node.
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where tail connects to the first node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Puisqu'il y avait une solution rare, je l'ai implémentée sur la base de l'idée de HashTable et MotoiHashMap qui y est écrite.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
hashmap = {}
while head != None:
if head in hashmap:
return True
hashmap[head] = head
head = head.next
return False
# Runtime: 80 ms, faster than 9.62% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.
L'élément «head» est assigné à la «hashmap» préparée jusqu'à ce que l'élément «head» soit vide, et l'élément suivant est assigné à «head».
Si l'élément head est dans la hashmap, cela signifie qu'il y a un point circulaire, donc il renvoie True, et s'il n'existe pas même après avoir vérifié jusqu'à la fin, il retourne False.
Je l'ai également écrit en référence à Two Pointers, qui était dans Solution.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if not head or not head.next:
return False
pre,cur = head,head.next
while pre != cur:
if not cur or not cur.next:
return False
pre,cur = pre.next,cur.next.next
return True
# Runtime: 84 ms, faster than 8.98% of Python3 online submissions for Linked List Cycle.
# Memory Usage: 16.9 MB, less than 100.00% of Python3 online submissions for Linked List Cycle.
La vitesse ne change pas beaucoup.
En parlant de liste consolidée, c'est la bible de la célèbre interview de codage à l'étranger [150 questions pour former des compétences en programmation pour combattre dans le monde ~ Livre pour devenir un programmeur des principales sociétés informatiques ~ Livre (japonais) (couverture souple)](https://www.amazon.co.jp/gp/product/4839942390 / ref = dbs_a_def_rwt_bibl_vppi_i2) Il était écrit dans le livre qu'il y a beaucoup de gens qui ne sont pas doués pour les listes concaténées parce qu'il y a beaucoup de processus de récurrence, mais cela a certainement pris du temps à résoudre parce que je n'utilise pas fréquemment les listes concaténées dans mon développement habituel.
Au fait, le livre ci-dessus est ancien, et maintenant il y a une nouvelle édition, donc si vous voulez l'acheter, cliquez ici 189 questions et solutions pour cette interview de codage pour former vos compétences en programmation dans le monde Je vous recommande de l'acheter.
S'il y a une bonne façon de l'écrire, je l'ajouterai.
Recommended Posts