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.
Letztes Mal Leet Code Day21 ab Null "448. Alle in einem Array verschwundenen Zahlen finden"
Grundsätzlich möchte ich die einfache Akzeptanz in absteigender Reihenfolge lösen.
Twitter Ich mache es.
Der Schwierigkeitsgrad ist einfach. Auszug aus den 100 beliebtesten Fragen.
Es ist ein Problem, das Grundkenntnisse über verkettete Listen erfordert.
Stellen Sie anhand einer verketteten Liste fest, ob sich ein Zyklus darin befindet.
Verwenden Sie die Ganzzahl pos, die an der Position der verketteten Liste endet (ab 0), um die Verbreitung der angegebenen verketteten Liste darzustellen. Wenn pos -1 ist, wird angenommen, dass es keine Zirkulation gibt.
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.
Da es eine seltene Lösung gab, implementierte ich sie basierend auf der Idee von HashTable und MotoiHashMap, die dort geschrieben wurden.
# 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.
Das Element "Kopf" wird der vorbereiteten "Hashmap" zugewiesen, bis das Element "Kopf" leer ist, und das nächste Element wird "Kopf" zugewiesen.
Befindet sich das head-Element in der Hashmap, bedeutet dies, dass es einen kreisförmigen Punkt gibt, sodass True zurückgegeben wird. Wenn es auch nach dem Überprüfen bis zum Ende nicht vorhanden ist, wird False zurückgegeben.
Ich schrieb es auch unter Bezugnahme auf zwei Zeiger, die in Lösung waren.
# 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.
Die Geschwindigkeit ändert sich nicht so sehr.
Apropos konsolidierte Liste, dies ist die Bibel des berühmten Coding-Interviews in Übersee [150 Fragen zur Ausbildung von Programmierkenntnissen für den Kampf in der Welt ~ Buch, um Programmierer von Top-IT-Unternehmen zu werden ~ (japanisches) Buch (Softcover)](https://www.amazon.co.jp/gp/product/4839942390 / ref = dbs_a_def_rwt_bibl_vppi_i2) In dem Buch wurde geschrieben, dass es viele Leute gibt, die nicht gut mit verketteten Listen umgehen können, weil es viele Wiederholungsprozesse gibt, aber die Lösung hat sicherlich einige Zeit in Anspruch genommen, da ich verkettete Listen in meiner üblichen Entwicklung nicht häufig verwende.
Das obige Buch ist übrigens alt und jetzt gibt es eine neue Ausgabe. Wenn Sie es also kaufen möchten, klicken Sie hier 189 Fragen dieses Codierungsinterviews, um die Programmierfähigkeit des Kampfes in der Welt und ihre Lösung zu trainieren Ich empfehle Ihnen, es zu kaufen.
Wenn es einen guten Weg gibt, es zu schreiben, werde ich es hinzufügen.
Recommended Posts