[PYTHON] Lassen Sie Code Tag 30 von vorne beginnen "234. Palindrome Linked List"

Überblick

Es scheint, dass Codierungstests in Ingenieurinterviews im Ausland durchgeführt werden, und in vielen Fällen besteht die Hauptsache darin, bestimmte Funktionen und Klassen entsprechend dem Thema zu implementieren.

Als Gegenmaßnahme scheint eine Website namens Let Code Maßnahmen zu ergreifen.

Eine Site, die algorithmische Leistung trainiert, die Codierungstests standhält, über die früh gesprochen wird.

Ich denke, es ist besser, die Algorithmuskraft eines Menschen zu haben, also werde ich das Problem unregelmäßig lösen und die Methode, die ich damals dachte, als Memo aufschreiben.

Leetcode

Leet Code-Tabelle ab Null

Letztes Mal Leet Code Day 29 "46. Permutationen" ab Null

Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.

Twitter Ich mache es.

Problem

234. Palindrome Linked List

Sie erhalten eine unidirektionale verkettete Liste. Überprüfen Sie daher, ob es sich um ein Rundschreiben handelt.

Example 1:

Input: 1->2 Output: false

Example 2:

Input: 1->2->2->1 Output: true

Lösung

Am einfachsten ist es, "True" zurückzugeben, wenn es mit der gespiegelten Version einer bestimmten verketteten Liste übereinstimmt, oder "False", wenn dies nicht der Fall ist.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        value = []
        while head:
            value.append(head.val)
            head = head.next
        return value == value[::-1]
# Runtime: 92 ms, faster than 15.28% of Python3 online submissions for Palindrome Linked List.
# Memory Usage: 24.1 MB, less than 11.54% of Python3 online submissions for Palindrome Linked List.

Diesmal hatte ich keine Zeit, also bringe ich die Antwort eines anderen aus der Diskussion.

Zum Beispiel die Antwort auf O (1).

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head):
        rev = None
        fast = head
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, head = head, rev, head.next
        tail = head.next if fast else head
        isPali = True
        while rev:
            isPali = isPali and rev.val == tail.val
            head, head.next, rev = rev, head, rev.next
            tail = tail.next
        return isPali
# Runtime: 92 ms, faster than 15.28% of Python3 online submissions for Palindrome Linked List.
# Memory Usage: 24.1 MB, less than 11.54% of Python3 online submissions for Palindrome Linked List.

https://leetcode.com/problems/palindrome-linked-list/discuss/64500/11-lines-12-with-restore-O(n)-time-O(1)-space

Der Inhalt dieser Diskussion wird als leicht verständliche Erklärung empfohlen. Es ist erstaunlich, dass es visuell leicht zu verstehen ist ...

https://leetcode.com/problems/palindrome-linked-list/discuss/324358/O(n)-time-and-O(1)-space-with-explanation-(Python-and-C)

Später gab es im Kapitel Verkettete Liste dieses Buches mehrere Lösungen.

150 Fragen zum Trainieren Ihrer Programmierkenntnisse in der Welt

Wenn Sie Zeit haben, können Sie es überprüfen.