Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

LeetCode_Thiết kế cấu trúc dữ liệu_Độ khó_460.

In lại Tác giả: Người biết Thời gian cập nhật: 2024-03-13 00:47:12 33 4
mua khóa gpt4 Nike

1. Câu hỏi

xin vui lòng làmThuật toán bộ nhớ đệm ít được sử dụng nhất (LFU)Thiết kế và triển khai cấu trúc dữ liệu.

Triển khai lớp LFUCache:

LFUCache(int dung lượng) - Khởi tạo đối tượng int với dung lượng của cấu trúc dữ liệu get(int key) - Nhận giá trị của khóa nếu nó tồn tại trong bộ đệm, nếu không thì trả về -1. void put(int key, int value) - Nếu khóa đã tồn tại, hãy thay đổi giá trị của nó; nếu khóa không tồn tại, hãy chèn cặp khóa-giá trị. Khi bộ đệm đạt đến dung lượng của nó, những mục ít được sử dụng nhất sẽ bị xóa trước khi các mục mới được chèn vào. Trong vấn đề này, khi có sự ràng buộc (tức là hai hoặc nhiều phím có cùng tần suất sử dụng), thì nên loại bỏ phím không được sử dụng gần đây nhất.

Để xác định các khóa ít được sử dụng nhất, bộ đếm mức sử dụng có thể được duy trì cho từng khóa trong bộ đệm.Khóa có số lần sử dụng nhỏ nhất là khóa cũ nhất chưa được sử dụng.

Khi một khóa lần đầu tiên được chèn vào bộ đệm, bộ đếm mức sử dụng của nó được đặt thành 1 (do thao tác đặt). Khi thao tác lấy hoặc đặt được thực hiện trên một phím trong bộ đệm, bộ đếm mức sử dụng sẽ tăng lên.

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ụ:

Đầu vào: ["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"] [[2 ], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]] Đầu ra: [null, null, null, 1, null, -1, 3, null, -1, 3, 4] Giải thích: // cnt(x) = số lần sử dụng của khóa x // cache=[] sẽ hiển thị thứ tự được sử dụng gần đây nhất (ngoài cùng bên trái Phần tử là mới nhất) LFUCache lfu = new LFUCache(2); lfu.put(1, 1); // cache=[1,_], cnt(1)=1 lfu.put(2, 2); cache=[2,1], cnt(2)=1, cnt(1)=1 lfu.get(1); // Trả về 1 // cache=[1,2], cnt(2)=1, cnt (1)=2 lfu.put(3, 3); // Xóa key 2, vì cnt(2)=1, số lần sử dụng là nhỏ nhất // cache=[3,1], cnt(3)=1 , cnt( 1)=2 lfu.get(2); // Trả về -1 (không tìm thấy) lfu.get(3); // Trả về 3 // cache=[3,1], cnt(3)=2, cnt(1)=2 lfu.put(4, 4); // Xóa key 1, cnt của 1 và 3 giống nhau, nhưng 1 lâu nhất không được sử dụng // cache=[4,3], cnt(4)= 1, cnt(3)=2 lfu.get(1); // Trả về -1 (không tìm thấy) lfu.get(3); // Trả về 3 // cache=[3,4], cnt(4)=1, cnt(3)=3 lfu.get(4); // Trả về 4 // cache=[3,4], cnt(4)=2, cnt(3)=3

gợi ý:
0 <= công suất <= 104
0 <= phím <= 105
0 <= giá trị <= 109
Gọi phương thức get và put tối đa 2 * 105 lần

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

2. Ý tưởng

(1) Thiết kế cấu trúc dữ liệu
Tham khảo ý tưởngCác câu hỏi về thuật toán giống như việc xây dựng Lego: Tôi sẽ hướng dẫn bạn từng bước để tháo dỡ thuật toán LFU.

3. Triển khai mã (Java)

//Ý tưởng 1——Lớp thiết kế cấu trúc dữ liệu LFUCache { //Dung lượng tối đa của bộ đệm LFU int dung lượng; // Tần số tối thiểu của bộ đệm LFU int minFreq; // Khóa để ánh xạ giá trị HashMap keyToValue; Khóa để ánh xạ tần số HashMap keyToFreq; // tần số để ánh xạ danh sách khóa HashMap> freqToKeys; LFUCache công khai (công suất int) { //Khởi tạo this.capacity = công suất; this.minFreq = 0; this.keyToValue = new HashMap<>(); ; this.freqToKeys = new HashMap<>(); } public int get(int key) { if (keyToValue.containsKey(key) == false) { //Không tìm thấy khóa return -1; } else { // Nếu tìm thấy khóa, tần số của nó sẽ tăng thêm một tăngFreq(key); key); } } public void put(int key, int value) { if (this.capacity <= 0) { return; } if (keyToValue.containsKey(key)) { /*if key đã tồn tại, chỉ cần sửa đổi giá trị tương ứng*/ keyToValue.put(key, value); // Tần suất của khóa tăng lên một tăngFreq(key); } /*Nếu khóa không tồn tại, bạn cần chèn nó* / if (this.capacity <= keyToValue.size()) { //Dung lượng bộ đệm LFU đã đầy, bạn cần loại bỏ khóa tối thiểu freq RemoveMinFreqKey(); } //Thay thế (khóa, giá trị) Thêm vào keyToValue keyToValue.put(key, value); //Thêm (key, 1) vào keyToFreq keyToFreq.put(key, 1); //Cập nhật freqToKeys freqToKeys.putIfAbsent(1, new LinkedHashSet<>() ); .get(1).add(key); // minFreq sau khi chèn khóa mới Nó phải là 1 this.minFreq = 1; } // Thêm một vào tần số của khóa public void tăngFreq(int key) { //Cập nhật keyToFreq int freq = keyToFreq.get(key); 1); // Xóa khóa khỏi danh sách tương ứng với freq freqToKeys.get(freq).remove(key); // Thêm khóa vào freq + 1 freqToKeys.putIfAbsent(freq + 1, new LinkedHashSet<>()); freqToKeys.get(freq + 1).add(key); //Nếu danh sách tương ứng với freq trống, hãy xóa freq này if (freqToKeys.get( freq).isEmpty()) { freqToKeys.remove(freq); //Nếu tần số này Nó xảy ra là minFreq, sau đó cập nhật minFreq if (freq == this.minFreq) { this.minFreq++; } } } // Loại bỏ khóa có tần số nhỏ nhất public void getMinFreqKey() { //Tìm danh sách freq = minFreq từ freqToKeys' LinkedHashSet keyList = freqToKeys.get(this.minFreq); Khóa đầu tiên được thêm vào là khóa cần loại bỏ int RemoveKey = KeysList.iterator().next(); KeysList.remove(removedKey); trống freqToKeys.remove(this.minFreq); /* Không cần cập nhật minFreq tại đây vì những lý do sau: RemoveMinFreqKey() Nó có thể được gọi khi chèn key mới vào put(), và trong code của put(), minFreq sẽ được cập nhật lên 1 khi chèn key mới nên không cần cập nhật minFreq tại đây */ } // Xóa keyToValue đã xóa trong keyToValue .remove(removedKey); // Xóa khóa đã xóa trong keyToFreq keyToFreq.remove(removedKey); Đối tượng LFUCache của bạn sẽ được khởi tạo và gọi như sau: * LFUCache obj = new LFUCache(capacity); * int param_1 = obj.get(key);
33 4 0
Bài viết khuyến nghị: Gói phân phối không có NCCL tích hợp
Bài viết khuyến nghị: Chân dung người dùng Internet, tiếp thị chính xác và kho dữ liệu có những thủ thuật thông minh
Bài viết khuyến nghị: Lua+OpenResty khởi động nhanh
Bài viết khuyến nghị: Cách sử dụng Tomcat để triển khai máy chủ dịch vụ nhắn tin tức thời WebSocket
người biết
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress