Thiết kế bộ nhớ đệm LRU Cache (LRU Cache Simulator) | Đấu Trường Thuật Toán

Bộ nhớ đệm LRU (Least Recently Used) là cấu trúc dữ liệu cực kỳ phổ biến trong các hệ thống caching Web (như Redis, Memcached, HTTP Gateway Cache) nhằm giải phóng bộ nhớ bằng cách đẩy phần tử ít được truy cập nhất ra ngoài khi dung lượng đầy.

Cho dung lượng capacity và danh sách các thao tác operations, mỗi thao tác có dạng ['put', key, value] hoặc ['get', key].

Hãy thực thi lần lượt các thao tác và trả về mảng kết quả của các lệnh get (nếu key không tồn tại trả về -1).

Ví dụ 1:

Input:
capacity = 2
operations = [['put', 1, 1], ['put', 2, 2], ['get', 1], ['put', 3, 3], ['get', 2], ['put', 4, 4], ['get', 1], ['get', 3], ['get', 4]]
Output: [1, -1, -1, 3, 4]
Giải thích:
- put(1, 1), put(2, 2)
- get(1) -> trả về 1 (1 trở thành mới nhất)
- put(3, 3) -> loại bỏ 2 (vì 2 ít được dùng nhất)
- get(2) -> trả về -1 (không tìm thấy)
- put(4, 4) -> loại bỏ 1
- get(1) -> trả về -1, get(3) -> 3, get(4) -> 4

Định Dạng Đầu Vào (Input)

Dòng 1: Số nguyên capacity
Dòng 2: Mảng operations

Định Dạng Đầu Ra (Output)

Mảng số nguyên kết quả của các lệnh get

Ràng Buộc (Constraints)

1 <= capacity <= 3000
1 <= operations.length <= 10^4

Ví Dụ Kiểm Thử Mẫu

Ví dụ 1:

Input:

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

Output:

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

Giải thích: Loại bỏ đúng phần tử cũ nhất

Ví dụ 2:

Input:

1
[["put", 1, 10], ["get", 1], ["put", 2, 20], ["get", 1], ["get", 2]]

Output:

[10, -1, 20]

Giải thích: Capacity = 1

Gợi ý được sắp xếp theo cấp độ tiến dần. Hãy mở từng gợi ý khi bạn thực sự cần thêm định hướng.

Kỹ thuật Hash Map & Thứ Tự Truy Cập O(1)

Duy trì một Hash Map kết hợp cơ chế ghi nhận thứ tự truy cập. Mỗi khi get(key) hoặc put(key), di chuyển key đó lên vị trí mới nhất. Khi vượt quá capacity, xóa key ở vị trí cũ nhất.

Vui lòng đăng nhập

Đăng nhập tài khoản học viên để xem lịch sử nộp bài của bạn.

Đăng nhập