Bộ Nhớ Đệm LRU
Nộp bài giải
Điểm:
1,00 (OI)
Giới hạn thời gian:
2.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, Java, Python
Cài đặt cấu trúc LRU Cache (Least Recently Used) với dung lượng cố định :
get(key): Trả về giá trị tương ứng với , hoặc nếu không tồn tại. Thao tác này cũng đánh dấu là vừa được truy cập.put(key, value): Thêm/cập nhật cặp . Nếu cache đã đầy, loại bỏ phần tử ít được dùng gần đây nhất (LRU).
Cả hai thao tác get và put đều đánh dấu là "vừa truy cập".
Hàm cần cài đặt
Đây là bài toán signature grader. Bạn chỉ cần cài đặt ba hàm sau, không cần viết main() hay đọc/ghi dữ liệu.
Ngôn ngữ hỗ trợ: C/C++, Python, và Java.
C++
void init(int cap);
int get(int key);
void put(int key, int value);
Python
def init(cap: int) -> None: ...
def get(key: int) -> int: ...
def put(key: int, value: int) -> None: ...
Java
public class Solution {
public void init(int cap) { ... }
public int get(int key) { ... }
public void put(int key, int value) { ... }
}
Mô tả
init(cap): Khởi tạo cache rỗng với dung lượng .get(key): Trả về giá trị nếu tồn tại, ngược lại trả về . Cập nhật thành "vừa truy cập".put(key, value): Thêm hoặc cập nhật. Nếu cache đầy và chưa tồn tại, loại bỏ phần tử LRU.
Ràng buộc
- Tổng số thao tác và :
- Mỗi thao tác
get/putphải chạy trong trung bình.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 2 8 P 1 1 P 2 2 G 1 P 3 3 G 2 P 4 4 G 1 G 3 |
1 -1 -1 3 |
cap=2. put(1,1), put(2,2). get(1)→1 (cache: 2,1). put(3,3) loại 2 (cache: 1,3). get(2)→-1. put(4,4) loại 1 (cache: 3,4). get(1)→-1. get(3)→3. |
Bình luận