Antwort A: OpenAI GPT-5.2
class _Node: __slots__ = ("key", "value", "prev", "next") def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Dummy head/tail to avoid edge cases. # Most-recent is right after head. Least-recent is right before tail. self.head = _Node()...
Vollstandige Antwort anzeigen ▼
class _Node: __slots__ = ("key", "value", "prev", "next") def __init__(self, key=None, value=None): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): if not isinstance(capacity, int) or capacity <= 0: raise ValueError("capacity must be a positive integer") self.capacity = capacity self.map = {} # key -> _Node # Dummy head/tail to avoid edge cases. # Most-recent is right after head. Least-recent is right before tail. self.head = _Node() self.tail = _Node() self.head.next = self.tail self.tail.prev = self.head def _add_to_front(self, node: _Node) -> None: node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def _remove(self, node: _Node) -> None: node.prev.next = node.next node.next.prev = node.prev node.prev = None node.next = None def _move_to_front(self, node: _Node) -> None: self._remove(node) self._add_to_front(node) def _evict_lru(self) -> None: 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.value def put(self, key: int, value: int) -> None: node = self.map.get(key) if node is not None: node.value = value self._move_to_front(node) return new_node = _Node(key, value) self.map[key] = new_node self._add_to_front(new_node) if len(self.map) > self.capacity: self._evict_lru() # Demonstration 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
Ergebnis
Siegstimmen
3 / 3
Durchschnittsscore
Gesamtpunktzahl
Gesamtkommentar
Die Einreichung ist herausragend. Sie bietet eine korrekte, effiziente und qualitativ hochwertige Implementierung eines LRU-Caches von Grund auf. Der Code verwendet den klassischen und optimalen Ansatz einer Hashmap in Kombination mit einer doppelt verketteten Liste. Die Implementierung ist robust, verfügt über Dummy-Kopf-/Fußzeilenknoten zur Vereinfachung von Randfällen und zeigt ausgezeichnete Codierungspraktiken wie Hilfsmethoden und Typ-Annotationen. Sie entspricht vollständig allen Aufgabenanforderungen und Einschränkungen.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung ist vollkommen korrekt. Sie verwendet erfolgreich eine Hashmap für O(1)-Lookups und eine doppelt verkettete Liste, um die Reihenfolge der Nutzung beizubehalten. Die Logik für `get`, `put` und Eviction funktioniert einwandfrei, und der bereitgestellte Demonstrationscode liefert genau die erwartete Ausgabe.
Vollstandigkeit
Gewichtung 20%Die Lösung ist vollständig. Sie bietet eine in sich geschlossene Klasse `LRUCache`, eine private `_Node`-Hilfsklasse und den exakten Demonstrationscode, der in der Aufforderung verlangt wurde. Alle erforderlichen Funktionalitäten sind implementiert.
Codequalitat
Gewichtung 20%Die Codequalität ist ausgezeichnet. Sie ist gut strukturiert mit klaren Hilfsmethoden mit einzelner Verantwortung (_add_to_front, _remove usw.), die die Lesbarkeit verbessern. Die Verwendung von Dummy-Kopf-/Fußzeilenknoten ist eine ausgefeilte Technik, die die Logik der verknüpften Liste vereinfacht. Die Einbeziehung von Typ-Annotationen, `__slots__` und Eingabevalidierung für die Kapazität zeigt starke, professionelle Codierungspraktiken.
Praktischer Nutzen
Gewichtung 15%Die Lösung hat einen hohen praktischen Wert. Sie bietet eine lehrbuchmäßig perfekte, effiziente Implementierung einer fundamentalen und weit verbreiteten Datenstruktur. Dieser Code könnte in realen Anwendungen verwendet werden und dient als hervorragende Referenz für den Aufbau eines LRU-Caches von Grund auf.
Befolgung der Anweisungen
Gewichtung 10%Die Lösung hält sich perfekt an alle Anweisungen. Sie implementiert korrekt den LRU-Cache von Grund auf, ohne verbotene Bibliotheken wie `collections.OrderedDict` zu verwenden. Sie erreicht die geforderte durchschnittliche Zeitkomplexität von O(1) für ihre Kernoperationen und enthält die obligatorische Demonstration.
Gesamtpunktzahl
Gesamtkommentar
Dies ist eine ausgezeichnete Implementierung eines LRU-Caches. Die Lösung verwendet korrekt eine doppelt verkettete Liste in Kombination mit einer Hashmap, um eine durchschnittliche Zeitkomplexität von O(1) sowohl für Get- als auch für Put-Operationen zu erreichen. Der Code vermeidet verbotene Konstrukte (OrderedDict, functools.lru_cache), behandelt alle Randfälle ordnungsgemäß und liefert genau die erwartete Ausgabe. Die Verwendung von Dummy-Kopf-/Schwanz-Sentinel-Knoten ist ein sauberer Ansatz, der Randfälle eliminiert. Der Code ist gut strukturiert, verwendet __slots__ zur Speichereffizienz, enthält eine Eingabevalidierung und ist klar kommentiert. Die Demonstration entspricht exakt der erforderlichen Ausgabe.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Die Implementierung ist vollständig korrekt. Die doppelt verkettete Liste mit Dummy-Sentinels verfolgt die Aktualität korrekt, get verschiebt aufgerufene Knoten nach vorne, put behandelt sowohl Einfüge- als auch Aktualisierungsfälle, die Verdrängung entfernt den tail.prev-Knoten (LRU), und alle Demonstrationsausgaben stimmen mit den erwarteten Werten überein (10, -1, -1, 30, 40).
Vollstandigkeit
Gewichtung 20%Die Lösung ist vollständig: Sie enthält die LRUCache-Klasse mit allen erforderlichen Methoden (Konstruktor, get, put), private Hilfsmethoden, die _Node-Klasse, Eingabevalidierung und den vollständigen Democode gemäß der Aufgabenstellung.
Codequalitat
Gewichtung 20%Codequalität ist ausgezeichnet. Die Verwendung von __slots__ für _Node zeigt Aufmerksamkeit für Speichereffizienz. Private Hilfsmethoden (_add_to_front, _remove, _move_to_front, _evict_lru) sind gut benannt und zweckgebunden. Typ-Annotationen werden verwendet. Kommentare erklären das Design des Sentinel-Knotens. Der Code ist sauber und lesbar.
Praktischer Nutzen
Gewichtung 15%Die Implementierung ist sehr praktisch. Sie enthält eine Eingabevalidierung mit einer aussagekräftigen Fehlermeldung, verwendet __slots__ für die Leistung und das Design ist erweiterbar. Die einzige geringfügige Lücke besteht darin, dass sie keine Threadsicherheit behandelt, was jedoch nicht von der Aufgabe gefordert wurde.
Befolgung der Anweisungen
Gewichtung 10%Alle Anweisungen werden präzise befolgt: keine Verwendung von OrderedDict oder functools.lru_cache, O(1)-Komplexität erreicht durch Hashmap + doppelt verkettete Liste, die zugrunde liegende Datenstruktur wird manuell implementiert, und der exakte Democode aus der Aufgabe ist mit korrekten erwarteten Ausgabenkommentaren enthalten.
Gesamtpunktzahl
Gesamtkommentar
Diese Antwort bietet eine korrekte, effiziente und in sich geschlossene Python-Implementierung eines LRU-Caches unter Verwendung einer Hashmap und einer doppelt verketteten Liste. Sie erfüllt die erforderlichen O(1)-Operationen, behandelt Kapazität und Verdrängung korrekt und enthält die angeforderte Demonstration, die die erwarteten Ausgaben drucken würde. Der Code ist sauber und lesbar; geringfügige Probleme beschränken sich auf kleine Stilpunkte (z. B. der Name 'map' überschattet ein Builtin und es gibt keine Docstrings), aber diese beeinträchtigen die Korrektheit oder Leistung nicht.
Bewertungsdetails anzeigen ▼
Korrektheit
Gewichtung 35%Implementiert LRU korrekt unter Verwendung einer Hashmap + doppelt verketteten Liste. Get und Put arbeiten in durchschnittlich O(1) Zeit, die Verdrängungslogik ist korrekt und die bereitgestellte Demonstration wird die erwarteten Ausgaben liefern.
Vollstandigkeit
Gewichtung 20%Alle erforderlichen Funktionen sind vorhanden: Konstruktor mit Kapazitätsvalidierung, Get- und Put-Semantik, LRU-Verdrängung bei Überschreitung der Kapazität, keine Verwendung von OrderedDict oder functools.lru_cache und die angeforderte Demonstration ist enthalten.
Codequalitat
Gewichtung 20%Der Code ist gut strukturiert, klar und verwendet Dummy-Kopf-/Schwanzknoten, um Listenoperationen zu vereinfachen. Die Methoden sind klein und fokussiert. Geringfügige Stil-Anmerkungen: Der Attributname 'map' überschattet das Builtin und es gibt keine Docstrings, aber diese beeinträchtigen die Korrektheit nicht.
Praktischer Nutzen
Gewichtung 15%Die Implementierung ist praktisch und für die Verwendung in echtem Code bereit: effizient, sicher (validiert Kapazität) und speichereffizient (verwendet __slots__). Würde von kleinen Ergänzungen wie Docstrings oder Unit-Tests profitieren, ist aber funktional vollständig.
Befolgung der Anweisungen
Gewichtung 10%Folgt den Anweisungen genau: Verwendet keine verbotenen Bibliotheken, implementiert die erforderlichen Datenstrukturen manuell, gewährleistet O(1)-Operationen und enthält die exakte Demonstration mit erwarteten gedruckten Ergebnissen.