Antwort A: OpenAI GPT-5.2
class LRUCache: class _Node: __slots__ = ("key", "val", "prev", "next") def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None def __init__(self, capacity: int): if capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Doubly-linked list with sentinels: # head <-> ... <-> tail # Most recently used is right after head. # Least recently used is right before tai...
Vollstandige Antwort anzeigen ▼
class LRUCache: class _Node: __slots__ = ("key", "val", "prev", "next") def __init__(self, key=0, val=0): self.key = key self.val = val self.prev = None self.next = None def __init__(self, capacity: int): if capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Doubly-linked list with sentinels: # head <-> ... <-> tail # Most recently used is right after head. # Least recently used is right before tail. self.head = self._Node() self.tail = self._Node() self.head.next = self.tail self.tail.prev = self.head def _remove(self, node: _Node) -> None: p, n = node.prev, node.next p.next = n n.prev = p def _add_to_front(self, node: _Node) -> None: # Insert right after head (mark as most recently used) first = self.head.next node.prev = self.head node.next = first self.head.next = node first.prev = node def _move_to_front(self, node: _Node) -> None: self._remove(node) self._add_to_front(node) def _evict_lru(self) -> None: # Remove node before tail lru = self.tail.prev if lru is self.head: return self._remove(lru) del self.map[lru.key] def get(self, key: int) -> int: node = self.map.get(key) if node is None: return -1 self._move_to_front(node) return node.val def put(self, key: int, value: int) -> None: node = self.map.get(key) if node is not None: node.val = value self._move_to_front(node) return new_node = self._Node(key, value) self.map[key] = new_node self._add_to_front(new_node) if len(self.map) > self.capacity: self._evict_lru() # Demonstration of correctness cache = LRUCache(2) cache.put(1, 10) cache.put(2, 20) print(cache.get(1)) # Expected: 10 cache.put(3, 30) # Evicts key 2 print(cache.get(2)) # Expected: -1 cache.put(4, 40) # Evicts key 1 print(cache.get(1)) # Expected: -1 print(cache.get(3)) # Expected: 30 print(cache.get(4)) # Expected: 40 # Output: # 10 # -1 # -1 # 30 # 40 # Brief O(1) explanation: # - A dictionary (hash map) maps keys to nodes, giving O(1) average lookup for get/put. # - A doubly linked list maintains recency order; moving a node to the front, # inserting a new node, and removing the LRU node are all O(1) pointer updates. # Combining these gives O(1) average time for both get and put.
Ergebnis
Siegstimmen
2 / 3
Durchschnittsscore
Gesamtpunktzahl
Gesamtkommentar
Hervorragende Implementierung eines LRU-Caches, der alle Anforderungen vollständig erfüllt. Die Lösung verwendet eine gut gestaltete Kombination aus einer Hash-Map und einer doppelt verketteten Liste mit Sentinel-Knoten, um eine Zeitkomplexität von O(1) sowohl für Get- als auch für Put-Operationen zu erreichen. Der Code ist sauber, gut strukturiert und behandelt alle Randfälle korrekt, einschließlich der Aktualisierung vorhandener Schlüssel und der ordnungsgemäßen Auslagerung. Die Demonstration liefert die exakt erwartete Ausgabe (10, -1, -1, 30, 40), und die Erklärung der O(1)-Komplexität ist korrekt und klar. Die Verwendung von __slots__ in der Node-Klasse zeigt Aufmerksamkeit für Speichereffizienz. Kleinere Beobachtungen: Der ValueError für eine nicht positive Kapazität ist ein netter defensiver Touch, war aber nicht explizit erforderlich; die Erklärung könnte etwas detaillierter sein, warum Dictionary-Lookups im Durchschnitt O(1) sind. Insgesamt ist dies eine Implementierung in Produktionsqualität.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung ist korrekt und liefert die exakt erwartete Ausgabesequenz (10, -1, -1, 30, 40). Alle Kernoperationen funktionieren ordnungsgemäß: get gibt korrekte Werte zurück und markiert Elemente als kürzlich verwendet, put fügt neue Elemente korrekt ein und aktualisiert vorhandene, und die Auslagerung entfernt ordnungsgemäß das am wenigsten kürzlich verwendete Element, wenn die Kapazität überschritten wird. Die doppelt verkettete Liste mit Sentinels behält die Reihenfolge der kürzlichen Verwendung korrekt bei. Randfälle wie die Aktualisierung eines vorhandenen Schlüssels werden korrekt behandelt. Der einzige geringfügige Abzug ist, dass der ValueError für eine nicht positive Kapazität, obwohl gute Praxis, nicht explizit für die Aufgabe erforderlich war.
Vollstandigkeit
Gewichtung 20%Die Antwort ist vollständig. Sie liefert die gesamte LRUCache-Klasse mit allen erforderlichen Methoden (__init__, get, put), enthält eine vollständige funktionierende Demonstration mit der exakt angegebenen Testsequenz, erzeugt alle erwarteten Ausgaben und schließt mit einer klaren Erklärung der O(1)-Zeitkomplexität ab. Die Implementierung enthält Hilfsmethoden (_remove, _add_to_front, _move_to_front, _evict_lru), die gut organisiert und für die Lösung notwendig sind. Nichts fehlt oder ist unvollständig.
Codequalitat
Gewichtung 20%Der Code ist von hoher Qualität mit ausgezeichneter Struktur und Lesbarkeit. Die Verwendung einer verschachtelten _Node-Klasse mit __slots__ zeigt Bewusstsein für Speichereffizienz. Methodennamen sind beschreibend und folgen Python-Konventionen. Die doppelt verkettete Liste mit Sentinel-Knoten ist elegant und vermeidet Randfälle der Nullprüfung. Kommentare erklären klar das Layout der Datenstruktur und den Zweck jeder Methode. Der Code ist gut organisiert mit logischer Trennung der Belange. Kleinere Anmerkung: Der Erläuterungskommentar am Ende könnte etwas detaillierter auf die durchschnittliche Komplexität von Hash-Maps eingehen, aber dies ist ein sehr kleiner Punkt.
Praktischer Nutzen
Gewichtung 15%Diese Implementierung hat einen hohen praktischen Wert als Referenzlösung. Sie demonstriert Best Practices für die Implementierung von LRU-Caches: Verwendung geeigneter Datenstrukturen (Hash-Map + doppelt verkettete Liste), ordnungsgemäße Verwendung von Sentinel-Knoten zur Eliminierung von Randfällen und klare Trennung von Hilfsmethoden. Der Code ist produktionsreif und könnte direkt in realen Anwendungen verwendet werden. Die defensive ValueError-Prüfung erhöht die Robustheit. Die Implementierung wäre ein hervorragendes lehrreiches Beispiel, um zu verstehen, wie Datenstrukturen kombiniert werden können, um spezifische Zeitkomplexitätsanforderungen zu erfüllen.
Befolgung der Anweisungen
Gewichtung 10%Die Antwort folgt allen Anweisungen präzise. Sie liefert eine vollständige Klasse namens 'LRUCache' mit den drei erforderlichen Methoden und korrekten Signaturen. Sowohl get als auch put erreichen eine durchschnittliche Zeitkomplexität von O(1) unter Verwendung geeigneter Datenstrukturen. Die Demonstrationssequenz wird exakt wie angegeben mit korrekter Ausgabe ausgeführt. Die Erklärung der O(1)-Komplexität ist enthalten und korrekt. Alle Anforderungen der Bewertungsrichtlinie sind erfüllt: korrekte Ausgabe, ordnungsgemäße Behandlung von Randfällen (Aktualisierung vorhandener Schlüssel), Verwendung von O(1)-Datenstrukturen und vollständiger lauffähiger Code.
Gesamtpunktzahl
Gesamtkommentar
Die bereitgestellte LRUCache-Implementierung ist außerordentlich gut strukturiert, korrekt und hochgradig effizient. Sie nutzt korrekt eine Kombination aus einer Hashmap und einer benutzerdefinierten doppelt verketteten Liste mit Sentinel-Knoten, um die geforderte durchschnittliche Zeitkomplexität von O(1) sowohl für `get`- als auch für `put`-Operationen zu erreichen. Der Code zeigt eine ausgezeichnete Liebe zum Detail, einschließlich der Verwendung von `__slots__` für die Knotenklasse und einer robusten Handhabung verschiedener Cache-Operationen wie die Aktualisierung bestehender Schlüssel und die Auslagerung des zuletzt verwendeten Elements. Die Demonstrationsausgabe ist vollkommen korrekt und die Erklärung der Zeitkomplexität ist klar und präzise.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung ist vollkommen korrekt. Die gesamte LRU-Cache-Logik, einschließlich Schlüsselabruf, Aktualisierungen, Einfügungen und Auslagerung des zuletzt verwendeten Elements, funktioniert wie erwartet. Die bereitgestellte Demonstrationssequenz erzeugt exakt die korrekte Ausgabe.
Vollstandigkeit
Gewichtung 20%Die Antwort liefert eine vollständige `LRUCache`-Klasse mit allen erforderlichen Methoden (`__init__`, `get`, `put`), eine klare Demonstration ihrer Verwendung und eine prägnante Erklärung ihrer Zeitkomplexität. Nichts Gefordertes fehlte.
Codequalitat
Gewichtung 20%Die Codequalität ist ausgezeichnet. Er ist gut organisiert mit Hilfsmethoden für die Operationen der verketteten Liste, verwendet Sentinel-Knoten für eine sauberere Listenmanipulation und enthält `__slots__` für Speichereffizienz in der `_Node`-Klasse. Die Variablennamen sind beschreibend und die Gesamtstruktur ist sehr gut lesbar und wartbar.
Praktischer Nutzen
Gewichtung 15%Diese Implementierung ist äußerst praktisch und produktionsreif. Sie zeigt ein tiefes Verständnis der für einen LRU-Cache erforderlichen Datenstrukturen und liefert eine robuste und effiziente Lösung. Die explizite Implementierung einer benutzerdefinierten doppelt verketteten Liste bietet volle Kontrolle und Einblick in den zugrunde liegenden Mechanismus, was sie in Szenarien wertvoll macht, in denen `collections.OrderedDict` möglicherweise nicht geeignet ist oder ein tieferes Verständnis erforderlich ist.
Befolgung der Anweisungen
Gewichtung 10%Alle Anweisungen wurden präzise befolgt. Die Klasse heißt `LRUCache`, die Methoden entsprechen den angegebenen Signaturen, die durchschnittliche Zeitkomplexität von O(1) wird erreicht und erklärt, die Kapazitätsprüfung ist vorhanden und die Demonstrationssequenz sowie ihre Ausgabe entsprechen exakt den Anforderungen.
Gesamtpunktzahl
Gesamtkommentar
Gut implementierter LRU-Cache: korrektes Verhalten, effiziente O(1)-Operationen mittels Hashmap + doppelt verketteter Liste, und die bereitgestellte Demonstration liefert die erwartete Ausgabe. Der Code ist klar und lauffähig, kleine Stil-/Anmerkungsverbesserungen sind möglich (z.B. mehr Typanmerkungen oder Docstrings), aber nichts davon beeinträchtigt die Korrektheit oder Leistung.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung ist korrekt: get und put verhalten sich wie spezifiziert, Updates verschieben Elemente zu MRU, Eviction entfernt das LRU bei Überschreiten der Kapazität, und die Demonstration gibt die erwartete Sequenz aus (10, -1, -1, 30, 40). Randfälle wie das Aktualisieren eines vorhandenen Schlüssels und Null-/Negative-Kapazität (ValueError) werden behandelt.
Vollstandigkeit
Gewichtung 20%Die Lösung umfasst eine vollständige, lauffähige LRUCache-Klasse mit __init__, get und put, eine Demonstration der erforderlichen Operationssequenz und eine prägnante Erklärung der O(1)-Komplexität. Alle im Prompt geforderten Verhaltensweisen sind vorhanden.
Codequalitat
Gewichtung 20%Der Code ist sauber und gut strukturiert: innere Node-Klasse mit __slots__, Sentinel-Kopf-/Schwanzknoten und klare Hilfsmethoden für Listenoperationen. Kleinere Stilverbesserungen könnten zusätzliche Typanmerkungen (z.B. für self.map) und Docstrings/Kommentare für öffentliche Methoden beinhalten, aber diese beeinträchtigen die Korrektheit nicht.
Praktischer Nutzen
Gewichtung 15%Die Implementierung ist effizient und praktisch für die reale Nutzung: O(1) durchschnittliche Operationen, Node-Design mit geringem Overhead und klare Semantik. Für den Produktionseinsatz könnte man Thread-Sicherheitsüberlegungen oder reichhaltigere Typisierung/Dokumentation hinzufügen, aber die Kernfunktionalität ist solide.
Befolgung der Anweisungen
Gewichtung 10%Alle Anweisungen wurden befolgt: Die Klasse LRUCache wurde bereitgestellt, die erforderlichen Methoden mit korrekten Signaturen implementiert, die Demonstration enthalten und die Erklärung der O(1)-Komplexität ist zutreffend.