What is the best way to solve LRU Cache?

The optimized O(1) approach using Linked List patterns is generally preferred.

상위 150개 인터뷰쉬움

LRU 캐시

'LRU 캐시' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

LRU(Least Recent Used) 캐시의 제약 조건을 따르는 데이터 구조를 설계합니다.

LRUCache 클래스를 구현합니다.

- LRUCache(capacity: int) - 양수 크기 용량으로 LRU 캐시를 초기화합니다.

- get(key: int) -> int - 키가 존재하면 해당 키의 값을 반환하고, 그렇지 않으면 -1을 반환합니다.

- put(key: int, value: int) -> None - 키가 존재하는 경우 키 값을 업데이트합니다. 그렇지 않으면 키-값 쌍을 캐시에 추가합니다. 키 수가 용량을 초과하는 경우 가장 최근에 사용한 키를 제거합니다.

가져오기 및 넣기 기능은 각각 O(1) 평균 시간 복잡도에서 실행되어야 합니다.

입력은 작업 목록과 인수 목록입니다. 결과 목록을 반환하는 lruCache(operations: list, arguments: list) -> list 함수를 구현합니다(생성자 및 넣기에는 없음).

제약

•1 <= capacity <= 3000
•0 <= key <= 10000
•0 <= value <= 100000
•At most 200000 calls will be made to get and put

예

Example 1

Input

["LRUCache","put","put","get","put","get","put","get","get","get"], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

Output

[None,None,None,1,None,-1,None,-1,3,4]

Explanation

Cache capacity is 2. put(1,1), put(2,2), get(1) returns 1. put(3,3) evicts key 2. get(2) returns -1 (evicted). put(4,4) evicts key 1. get(1) returns -1, get(3) returns 3, get(4) returns 4.

Need a Hint?

세트나 힙과 같은 연결 목록 관련 데이터 구조를 사용하는 것을 고려해보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

연결 목록 접근 방식의 논리를 설명하십시오.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(1)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

class DNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCacheOpt:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.left = DNode(0, 0)
        self.right = DNode(0, 0)
        self.left.next = self.right
        self.right.prev = self.left

    def _remove(self, node):
        prev, nxt = node.prev, node.next
        prev.next = nxt
        nxt.prev = prev

    def _insert(self, node):
        prev, nxt = self.right.prev, self.right
        prev.next = node
        nxt.prev = node
        node.prev = prev
        node.next = nxt

    def get(self, key: int) -> int:
        if key in self.cache:
            self._remove(self.cache[key])
            self._insert(self.cache[key])
            return self.cache[key].val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self._remove(self.cache[key])
        self.cache[key] = DNode(key, value)
        self._insert(self.cache[key])
        if len(self.cache) > self.cap:
            lru = self.left.next
            self._remove(lru)
            del self.cache[lru.key]

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

class LRUCacheBrute:
    def __init__(self, capacity: int):
        self.cap = capacity
        self.cache = {}
        self.usage = []

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.usage.remove(key)
        self.usage.append(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.usage.remove(key)
        elif len(self.cache) >= self.cap:
            lru = self.usage.pop(0)
            del self.cache[lru]
        self.cache[key] = value
        self.usage.append(key)