Gesehen
Programmierung
OpenAI
GPT-5.2
VS
Google
Gemini 2.5 Pro
Implementierung eines Least Recently Used (LRU) Caches
Implementieren Sie eine LRU (Least Recently Used) Cache-Datenstruktur in Python. Ihre Implementierung sollte eine Klasse namens `LRUCache` sein, die die folgenden Operationen unterstützt:
1. `__init__(self, capacity: int)` — Initialisieren Sie den Cache mit einer positiven Ganzzahl-Kapazität.
2. `get(self, key: int) -> int` — Geben Sie den Wert zurück, der dem Schlüssel zugeordnet ist, falls er im Cache vorhanden ist, andernfalls geben Sie -1 zurück. Der Zugriff auf einen Schlüssel zählt als "Verwendung".
3. `put(self, key: int, value: int) -> None` — Fügen Sie das Schlüssel-Wert-Paar ein oder aktualisieren Sie es. Wenn der Cache nach der Einfügung seine Kapazität überschreitet, verwerfen Sie den am wenigsten zuletzt verwendeten Schlüssel.
Sowohl `get` als auch `put` müssen in einer durchschnittlichen Zeitkomplexität von O(1) laufen.
Stellen Sie die vollständige Klassenimplementierung bereit. Demonstrieren Sie dann seine Korrektheit, indem Sie die Ausgabe der folgenden Sequenz von Operationen zeigen:
```
cache = LRUCache(2)
cache.put(1, 10)
cache.put(2, 20)
print(cache.get(1)) # Erwartet: 10
cache.put(3, 30) # Verwirft Schlüssel 2
print(cache.get(2)) # Erwartet: -1
cache.put(4, 40) # Verwirft Schlüssel 1
print(cache.get(1)) # Erwartet: -1
print(cache.get(3)) # Erwartet: 30
print(cache.get(4)) # Erwartet: 40
```
Erklären Sie kurz, wie Ihre Implementierung eine O(1) Zeitkomplexität für beide Operationen erreicht.
