cpp-087Đọc toàn bộ đề miễn phí

Cài đặt bộ nhớ đệm LRU Cache: Danh sách liên kết kép kết hợp Bảng băm

Cài đặt bộ nhớ đệm LRU có sức chứa C. Bạn cần xử lý Q truy vấn thuộc 2 loại:

C++Trung bình35 phút

Tiến độ của tôi ở bài này

Điểm được lưu vào tài khoản sau khi chấm bài.

Đang tải điểm của bạn…

data structureslru cachelinked listhash table

Kiến thức tiên quyết: std unordered map, doubly linked list.

Nội dung đề bài3 cấp độ gợi ýPhân tích lời giảiCode tham khảo

Hiểu cơ chế thay thế trang Least Recently Used (LRU): Khi bộ nhớ đệm vượt quá dung lượng $C$ , phần tử ít được sử dụng nhất gần đây sẽ bị loại bỏ.
Kết hợp Danh sách liên kết kép (Doubly Linked List) và Bảng băm (std::unordered_map) để hỗ trợ thao tác GET và PUT trong thời gian $O(1)$ .

Cài đặt bộ nhớ đệm LRU có sức chứa $C$ . Bạn cần xử lý $Q$ truy vấn thuộc 2 loại:

PUT key val: Thêm hoặc cập nhật cặp (key, val). Nếu dung lượng vượt quá $C$ , xóa phần tử ít được sử dụng nhất.
GET key: Trả về giá trị của key và đánh dấu key này là vừa được sử dụng. Nếu key không tồn tại, trả về -1.

Chỉ cần viết một chương trình đọc stdin và in ra stdout. Bài này không yêu cầu viết hàm.
Không dùng cout để in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vào stdout và làm bài sai.
Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.

Dòng 1: Gồm 2 số nguyên $C, Q$ ( $1 \leq C \leq 105, 1 \leq Q \leq 105$ ).
$Q$ dòng tiếp theo: Mỗi dòng mô tả một thao tác PUT key val hoặc GET key ( $1 \leq key, val \leq 109$ ).

2 6
PUT 1 10
PUT 2 20
GET 1
PUT 3 30
GET 2
GET 3

10
-1
30
*Giải thích: Sau khi GET 1, thứ tự dùng là [2, 1]. PUT 3 khiến 2 bị loại (do 2 là LRU). GET 2 trả về -1.*

3 cấp độ gợi ýMở dần khi bạn thật sự cần hỗ trợ.

Phân tích lời giảiGiải thích hướng tư duy và thuật toán.

Code tham khảoDùng để đối chiếu sau khi tự làm.

Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.

Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.