1. Câu hỏi

Vui lòng thiết kế và triển khai cấu trúc dữ liệu thỏa mãn các ràng buộc bộ đệm LRU (ít được sử dụng gần đây nhất).
Triển khai lớp LRUCache:

① LRUCache(int dung lượng) Khởi tạo bộ đệm LRU với số nguyên dương làm dung lượng dung lượng ② int get(int key) Nếu khóa từ khóa tồn tại trong bộ đệm, trả về giá trị của từ khóa, nếu không thì trả về -1. ③ void put(int key, int value) Nếu khóa từ khóa đã tồn tại, hãy thay đổi giá trị giá trị dữ liệu của nó, nếu nó không tồn tại, hãy chèn tập hợp khóa-giá trị vào bộ đệm. Nếu thao tác chèn làm cho số lượng từ khóa vượt quá khả năng cho phép thì từ khóa cũ nhất không được sử dụng sẽ bị loại bỏ. Các hàm get và put phải chạy với độ phức tạp thời gian trung bình là O(1).

Ví dụ:

Nhập ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] đầu ra [null, null, null, 1 , không, -1, null, -1, 3, 4] Giải thích LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // Bộ đệm là {1=1} lRUCache.put(2, 2); cache là {1=1, 2=2} lRUCache.get(1); // Trả về 1 lRUCache.put(3, 3); // Thao tác này sẽ tạo ra từ khóa 2 Không hợp lệ, bộ đệm là {1=1, 3=3} lRUCache.get(2); // Trả về -1 (không tìm thấy) lRUCache.put(4, 4); // Thao tác này sẽ làm mất hiệu lực từ khóa 1 và được lưu vào bộ đệm {4=4, 3=3} lRUCache.get(1); // Trả về -1 (không tìm thấy) lRUCache.get(3); // Trả về 3 lRUCache.get(4); 4

gợi ý:
1 <= công suất <= 3000
0 <= phím <= 10000
0 <= giá trị <= 105
Gọi get và đặt tối đa 2 * 105 lần

Nguồn: LeetCode
Liên kết: https://leetcode-cn.com/problems/lru-cache

2. Ý tưởng

(1) Danh sách liên kết băm
Tham khảo ý tưởngCác thuật toán giống như xây dựng Lego: Tôi sẽ chỉ cho bạn thuật toán LRU.

3. Triển khai mã (Java)

//Ý tưởng 1——Băm danh sách liên kết lớp LRUCache { //Xác định danh sách liên kết băm LinkedHashMap cache = new LinkedHashMap<>(); // Dung lượng của bộ đệm int dung lượng; { this.capacity = dung lượng; } public int get(int key) { if (!cache.containsKey(key)) { return -1; } else { //thay thế khóa Thay đổi thành makeRecently(key); return cache.get(key); } } public void put(int key, int value) { if (cache.containsKey(key)) { //khóa đã tồn tại, hãy sửa đổi nó giá trị dữ liệu tương ứng cache.put(key, value); //Thay đổi khóa thành makeRecently(key); //Dung lượng đã đầy, phần đầu của danh sách liên kết là khóa lâu ngày không được sử dụng int oldKey = cache.keySet().iterator().next(); //Thêm khóa mới vào cuối danh sách được liên kết cache.put(key, value); } public void makeRecently(int key) { int val = cache.get(key); ); //Thêm nó trở lại cuối danh sách được liên kết cache.put(key, val); } } /** * Đối tượng LRUCache của bạn sẽ được khởi tạo và gọi như sau: * LRUCache obj = new LRUCache(capacity); param_1 = obj .get(key); * obj.put(key,value */);

Thử thách đăng ký sáng tạo

Giành giải thưởng khuyến khích ngoại vi lưu lượng truy cập/tiền mặt/CSDN