[PYTHON] Soit Code Day78 à partir de zéro "206. Liste liée inversé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.

Apparemment, de nombreux ingénieurs prennent des mesures sur le site appelé LetCode.

C'est un site qui forme la puissance algorithmique qui peut résister au test de codage effectué au début de l'histoire, et c'est une voie inévitable pour ceux qui veulent faire carrière dans une entreprise de technologie à l'étranger.

Je l'ai écrit en grand, mais je n'ai pas l'intention d'avoir une telle interview pour le moment.

Cependant, en tant qu'ingénieur informatique, il serait préférable d'avoir le même niveau de puissance d'algorithme qu'un être humain, donc j'aimerais résoudre le problème de manière irrégulière et écrire la méthode que je pensais à l'époque sous forme de mémo.

Leetcode

Je le résolve avec Python3.

Table de codes Leet commençant à zéro

Dernière fois Leet Code Day 77 à partir de zéro "1502. Peut faire une progression arithmétique à partir de la séquence"

À l'heure actuelle, je donne la priorité au moyen des 100 questions les plus appréciées. Easy a été résolu, donc si vous êtes intéressé, veuillez vous rendre à la table.

Twitter Je le fais.

** Blog technique Commencé! !! ** ** Je pense que la technologie écrira sur LetCode, Django, Nuxt, etc. ** C'est plus rapide à mettre à jour **, merci pour votre coopération!

problème

206. Reverse Linked List Le niveau de difficulté est facile.

Le problème est que vous ne faites que retourner une liste concaténée unidirectionnelle donnée.

Example:

Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL

Solution

Pour le moment, des choses itératives.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre,cur = None,head
        while cur != None:
            nex = cur.next
            cur.next = pre
            pre = cur
            cur = nex
        return pre
# Runtime: 44 ms, faster than 26.15% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.3 MB, less than 67.33% of Python3 online submissions for Reverse Linked List.

Préparez trois variables, pre, cur et nex, et conservez les éléments précédent, actuel et suivant et remplacez-les. Je pense que vous devriez le considérer comme une image de préparation de variables et de création de lieux d'évasion temporaires pour chacun.

Cependant, si tel est le cas, quelle que soit l'échelle, si le nombre de variables augmente, la quantité de traitement augmentera et il sera difficile d'écrire. Après tout, je veux m'amuser.

Maintenant, voici la réponse en utilisant stack.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head:
            return None
        
        stack = []
        
        while head.next:
            stack.append(head)
            head = head.next
            
        while stack:
            cur = stack.pop()
            cur.next.next = cur
            cur.next = None
            
        return head
# Runtime: 40 ms, faster than 46.28% of Python3 online submissions for Reverse Linked List.
# Memory Usage: 15.1 MB, less than 96.42% of Python3 online submissions for Reverse Linked List.

J'aime celui-ci parce que je peux l'écrire proprement sans gâcher. Et un peu, la vitesse s'est améliorée.

J'ai écrit deux exemples de réponses, mais qu'en est-il?

N'est-ce pas plus intelligent et meilleur? Si vous avez une opinion, je vous serais reconnaissant de bien vouloir commenter.