Soit Code Jour 22 à partir de zéro "141. Cycle de liste liée"

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

Leetcode

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.

problème

141. Linked List Cycle

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.

Solution

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

Soit Code Jour 22 à partir de zéro "141. Cycle de liste liée"
Let Code Day 30 à partir de zéro "234. Palindrome Linked List"
Soit Code Jour 84 à partir de zéro "142. Cycle de liste liée II"
Soit Code Day78 à partir de zéro "206. Liste liée inversée"
Soit Code Day75 à partir de zéro "15.3 Sum"
Let Code Day 29 "46. Permutations" à partir de zéro
Soit Code Day3 à partir de zéro "1313. Decompress Run-Length Encoded List"
Let Code Day 27 "101. Symmetric Tree" à partir de zéro
Let Code Day 41 "394. Decode String" à partir de zéro
Let Code Day 25 "70. Grimper les escaliers" à partir de zéro
Laissez Code Day69 à partir de zéro "279. Perfect Squares"
Let Code Day 34 à partir de zéro "118. Le triangle de Pascal"
Laissez Code Day85 à partir de zéro "6. Conversion en zigzag"
Laissez Code Day20 partir de zéro "134. Station-service"
Let Code Day 88 "139. Word Break" à partir de zéro
Let Code Day 28 "198. House Robber" à partir de zéro
Let Code Day 39 "494. Target Sum" à partir de zéro
Let Code Day 36 "155. Min Stack" à partir de zéro
Let Code Day 17 "169. Majority Element" à partir de zéro
Let Code Day 33 "1. Two Sum" à partir de zéro
Let Code Day 23 "226. Invert Binary Tree" en partant de zéro
Let Code Day8 À partir de zéro "1302. Somme des feuilles les plus profondes"
Soit Code Day 40 à partir de zéro "114. Aplatir l'arbre binaire à la liste liée"
Let Code Day 32 "437. Path Sum III" à partir de zéro
Soit Code Day68 à partir de zéro "709. To Lower Case"
Let Code Day 26 à partir de zéro "94. Traversée en ordre de l'arbre binaire"
Soit Code Day 46 à partir de zéro "406. Reconstruction de file d'attente par hauteur"
Let Code Day 31 "581. Le sous-tableau continu non trié le plus court" à partir de zéro
Let Code Day 38 à partir de zéro "208. Implémenter Trie (Prefix Tree)"
Soit Code Day 65 "560. Subarray Sum Equals K" à partir de zéro
Soit Code Day4 à partir de zéro "938. Range Sum of BST"
Let Code Day 77 "1502. Peut faire une progression arithmétique à partir de la séquence" à partir de zéro
Soit Code Jour 76 à partir de zéro "3. Sous-chaîne la plus longue sans caractères répétitifs"
Let Code Day 35 "160. Intersection de deux listes liées" à partir de zéro
Soit Code Day58 à partir de zéro "20. Parenthèses valides"
Soit Code Day16 à partir de zéro "344. Reverse String"
Soit Code Day49 à partir de zéro "1323. Maximum 69 Number"
Let Code Day89 "62. Chemins uniques" à partir de zéro
Let Code Day 55 "22. Générer des parenthèses" à partir de zéro
Soit Code Day18 à partir de zéro "53. Maximum Subarray"
Let Code Day 13 "338. Comptage des bits" à partir de zéro
Let Code Day71 À partir de zéro "1496. Traversée de chemin"
Let Code Day 61 "7. Integer Integer" à partir de zéro
Let Code Day 82 "392. Is Subsequence" Partant de zéro
Let Code Day51 "647. Sous-chaînes palindromiques" à partir de zéro
Let Code Day 50 "739. Températures quotidiennes" à partir de zéro
Let Code Day 15 "283. Move Zeroes" à partir de zéro
Soit Code Day14 à partir de zéro "136. Numéro unique"
Let Code Day 9 "701. Insérer dans un arbre de recherche binaire" à partir de zéro
Let Code Day 80 "703. Kth plus grand élément d'un flux" à partir de zéro
Let Code Day 66 "438. Find All Anagrams in a String" en partant de zéro
Let Code Day 43 à partir de zéro "5. Le plus long substrat palindromique"
Soit Code Day74 à partir de zéro "12. Integer to Roman"
Let Code Day 42 "2. Add Two Numbers" en partant de zéro
Let Code Day57 À partir de zéro "35. Rechercher Insérer la position"
Soit Code Day47 à partir de zéro "14. Préfixe commun le plus long"
Let Code Day 90 à partir de zéro "101 1. Capacité à expédier les colis dans les D jours"
Soit Code Day 44 "543. Diamètre de l'arbre binaire" à partir de zéro
Soit Code Jour 64 à partir de zéro "287. Trouver le numéro en double"
Let Code Day24 À partir de zéro "21. Fusionner deux listes triées"
Laissez Code Day12 partir de zéro "617. Fusionner deux arbres binaires"