Hướng dẫn giải của Bộ nhớ đệm LRU

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.

Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.

Bạn phải đăng nhập để mở lời giải này.

Đăng nhập

Tác giả: Hiếu Nguyễn

Phân tích

Bài toán yêu cầu mô phỏng hoạt động của một LRU Cache với hai thao tác chính:

Get(key): Truy xuất giá trị của key, nếu không tồn tại trả về -1. Sau khi truy xuất, key đó trở thành "mới nhất".
Put(key, value): Chèn hoặc cập nhật cặp key-value. Nếu cache đầy, cần xóa bỏ phần tử "ít được sử dụng nhất" (LRU).

Thuật toán

Sử dụng OrderedDict (trong Python) hoặc HashMap + Doubly Linked List để:

Tra cứu key trong O(1) bằng hash map
Xác định và xóa phần tử LRU trong O(1) bằng doubly linked list

Các bước cụ thể:

Get(key):
- Nếu key không tồn tại → trả về -1
- Nếu tồn tại → di chuyển node chứa key xuống cuối (most recent), trả về giá trị
Put(key, value):
- Nếu key đã tồn tại → cập nhật giá trị và di chuyển xuống cuối
- Nếu key mới:
  - Nếu cache đầy → xóa phần tử đầu tiên (least recent)
  - Thêm key mới vào cuối

Độ phức tạp

Time: O(1) cho cả get và put
Space: O(capacity)

Code mẫu (Python)

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

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

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

Bình luận

Please read the guidelines before commenting.

from collections import OrderedDict

class LRUCache: def init(self, capacity: int): self.cache = OrderedDict() self.capacity = capacity

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

def put(self, key: int, value: int) -> None:
    if key in self.cache:
        self.cache.move_to_end(key)
    self.cache[key] = value
    if len(self.cache) > self.capacity:
        self.cache.popitem(last=False)