【問題描述】

設計并實現最不經常使用（LFU）緩存的數據結構。它應該支持以下操作：get?和?put。get(key)?- 如果鍵存在于緩存中，則獲取鍵的值（總是正數），否則返回 -1。 put(key, value)?- 如果鍵不存在，請設置或插入值。當緩存達到其容量時，它應該在插入新項目之前，使最不經常使用的項目無效。在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，最近最少使用的鍵將被去除。進階： 你是否可以在?O(1)?時間復雜度內執行兩項操作？示例：LFUCache cache = new LFUCache( 2 /* capacity (緩存容量) */ );cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/lfu-cache

【解答思路】

1. 核心思想：先考慮訪問次數，在訪問次數相同的情況下，再考慮緩存的時間

• 每次訪問一個已經存在的元素的時候：應該先把結點類從當前所屬的訪問次數雙鏈表里刪除，然后再添加到它「下一個訪問次數」的雙向鏈表的頭部。
  

時間復雜度：O(1) 空間復雜度：O(N)

import java.util.HashMap; import java.util.Map;public class LFUCache {/*** key 就是題目中的 key* value 是結點類*/private Map<Integer, ListNode> map;/*** 訪問次數哈希表，使用 ListNode[] 也可以，不過要占用很多空間*/private Map<Integer, DoubleLinkedList> frequentMap;/*** 外部傳入的容量大小*/private Integer capacity;/*** 全局最高訪問次數，刪除最少使用訪問次數的結點時會用到（這個設計可能是冗余的）*/private Integer maxFrequent = 1;public LFUCache(int capacity) {map = new HashMap<>(capacity);frequentMap = new HashMap<>();this.capacity = capacity;}/*** get 一次操作，訪問次數就增加 1；* 從原來的鏈表調整到訪問次數更高的鏈表的表頭** @param key* @return*/public int get(int key) {// 測試測出來的，capacity 可能傳 0if (capacity == 0) {return -1;}if (map.containsKey(key)) {// 獲得結點類ListNode listNode = removeListNode(key);// 掛接到新的訪問次數的雙向鏈表的頭部int frequent = listNode.frequent;addListNode2Head(frequent, listNode);return listNode.value;} else {return -1;}}/*** @param key* @param value*/public void put(int key, int value) {// 如果 key 存在，就更新訪問次數 + 1，更新值if (map.containsKey(key)) {ListNode listNode = removeListNode(key);// 更新 valuelistNode.value = value;int frequent = listNode.frequent;addListNode2Head(frequent, listNode);return;}// 如果 key 不存在// 1、如果滿了，先刪除訪問次數最小的的末尾結點，再刪除 map 里對應的 keyif (map.size() == capacity) {for (int i = 1; i <= maxFrequent; i++) {if (frequentMap.containsKey(i) && frequentMap.get(i).count > 0) {// 1、從雙鏈表里刪除結點DoubleLinkedList doubleLinkedList = frequentMap.get(i);ListNode removeNode = doubleLinkedList.removeTail();// 2、刪除 map 里對應的 keymap.remove(removeNode.key);break;}}}// 2、再創建新結點放在訪問次數為 1 的雙向鏈表的前面ListNode newListNode = new ListNode(key, value);addListNode2Head(1, newListNode);map.put(key, newListNode);}// 以下部分主要是結點類和雙向鏈表的操作/*** 結點類，是雙向鏈表的組成部分*/private class ListNode {private int key;private int value;private int frequent = 1;private ListNode pre;private ListNode next;public ListNode() {}public ListNode(int key, int value) {this.key = key;this.value = value;}}/*** 雙向鏈表*/private class DoubleLinkedList {/*** 虛擬頭結點，它無前驅結點*/private ListNode dummyHead;/*** 虛擬尾結點，它無后繼結點*/private ListNode dummyTail;/*** 當前雙向鏈表的有效結點數*/private int count;public DoubleLinkedList() {this.dummyHead = new ListNode(-1, -1);this.dummyTail = new ListNode(-1, -1);dummyHead.next = dummyTail;dummyTail.pre = dummyHead;count = 0;}/*** 把一個結點類添加到雙向鏈表的開頭（頭部是最新使用數據）** @param addNode*/public void addNode2Head(ListNode addNode) {ListNode oldHead = dummyHead.next;// 兩側結點指向它dummyHead.next = addNode;oldHead.pre = addNode;// 它的前驅和后繼指向兩側結點addNode.pre = dummyHead;addNode.next = oldHead;count++;}/*** 把雙向鏈表的末尾結點刪除（尾部是最舊的數據，在緩存滿的時候淘汰）** @return*/public ListNode removeTail() {ListNode oldTail = dummyTail.pre;ListNode newTail = oldTail.pre;// 兩側結點建立連接newTail.next = dummyTail;dummyTail.pre = newTail;// 它的兩個屬性切斷連接oldTail.pre = null;oldTail.next = null;count--;return oldTail;}}/*** 將原來訪問次數的結點，從雙向鏈表里脫離出來** @param key* @return*/private ListNode removeListNode(int key) {// 獲得結點類ListNode deleteNode = map.get(key);ListNode preNode = deleteNode.pre;ListNode nextNode = deleteNode.next;// 兩側結點建立連接preNode.next = nextNode;nextNode.pre = preNode;// 刪除去原來兩側結點的連接deleteNode.pre = null;deleteNode.next = null;// 維護雙鏈表結點數frequentMap.get(deleteNode.frequent).count--;// 訪問次數加 1deleteNode.frequent++;maxFrequent = Math.max(maxFrequent, deleteNode.frequent);return deleteNode;}/*** 把結點放在對應訪問次數的雙向鏈表的頭部** @param frequent* @param addNode*/private void addListNode2Head(int frequent, ListNode addNode) {DoubleLinkedList doubleLinkedList;// 如果不存在，就初始化if (frequentMap.containsKey(frequent)) {doubleLinkedList = frequentMap.get(frequent);} else {doubleLinkedList = new DoubleLinkedList();}// 添加到 DoubleLinkedList 的表頭doubleLinkedList.addNode2Head(addNode);frequentMap.put(frequent, doubleLinkedList);} }作者：liweiwei1419 鏈接：https://leetcode-cn.com/problems/lfu-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiwei/

測試用例

public class LFUCache {public static void main(String[] args) {LFUCache cache = new LFUCache(3);cache.put(1, 1);cache.put(2, 2);cache.put(3, 3);System.out.println(cache.map.keySet());cache.put(4, 4);System.out.println(cache.map.keySet());int res1 = cache.get(4);System.out.println(res1);int res2 = cache.get(3);System.out.println(res2);int res3 = cache.get(2);System.out.println(res3);int res4 = cache.get(1);System.out.println(res4);cache.put(5, 5);int res5 = cache.get(1);System.out.println(res5);int res6 = cache.get(2);System.out.println(res6);int res7 = cache.get(3);System.out.println(res7);int res8 = cache.get(4);System.out.println(res8);int res9 = cache.get(5);System.out.println(res9);} }

【總結】

1.LFU （Least Frequently Used）緩存機制（看訪問次數）
-在緩存滿的時候，刪除緩存里使用次數最少的元素，然后在緩存中放入新元素；
-數據的訪問次數很重要，訪問次數越多，就越不容易被刪除；
-根據題意，「當存在平局（即兩個或更多個鍵具有相同使用頻率）時，最近最少使用的鍵將被去除」，即在「訪問次數」相同的情況下，按照時間順序，先刪除在緩存里時間最久的數據

2.編碼總結

3.功力仍未夠深厚 只能理解其思想

文章轉載鏈接： https://leetcode-cn.com/problems/lfu-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiwei/

總結

以上是生活随笔為你收集整理的[Leedcode][JAVA][第460题][LFU]的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。