題目鏈接

LFU 緩存

題目描述

注意點

• 1 <= capacity <= 10^4
• 0 <= key <= 10^5
• 0 <= value <= 10^9
• 對緩存中的鍵執行 get 或 put 操作，使用計數器的值將會遞增
• 當緩存達到其容量 capacity 時，則應該在插入新項之前，移除最不經常使用的項
• 函數 get 和 put 必須以 O(1) 的平均時間復雜度運行

解答思路

• 創建Node雙向鏈表節點類，其中包含freq，key，value，prev指針，next指針
• 兩個Map，kvMap存儲鍵值對，freqMap存儲頻率以及對應頻率的鏈表頭尾節點，capacity存儲容量，minFreq存儲最小調用頻率
• 做get()操作時，如果key無相應節點，直接返回-1；如果有相應節點，則其頻率要加一，要從原頻率鏈表中移除該節點，并將該節點加入到新頻率的鏈表中，還要注意更新minFreq的值
• 做put()操作時
  • 如果key有相應節點，則取出原有節點，將原有節點取出，將其頻率加一，從原頻率鏈表中移除該節點，并將該節點加入到新頻率的鏈表中，還要注意更新minFreq的值
  • 如果key無相應節點，則需要新建一個節點，寫入key，value，freq為1，再將該節點加入到kvMap和freqMap對應頻率鏈表中，還要判斷此時kvMap是否已滿，如果節點過多還要移除最不經常使用的節點，也就是最低頻率minFreq對應鏈表中的第一個節點，還要注意更新minFreq的值為1

代碼

class LFUCache {// 最小調用頻率int minFreq;// 容量int capacity;// key->key，value->對應節點Map<Integer, Node> kvMap;// key->使用頻率，value->對應鏈表的頭尾節點Map<Integer, Node[]> freqMap;public LFUCache(int capacity) {minFreq = 0;this.capacity = capacity;kvMap = new HashMap<>(capacity);freqMap = new HashMap<>();}public int get(int key) {if (kvMap.get(key) == null) {return -1;}Node node = kvMap.get(key);// 當前節點是最低頻率且此時最低頻率鏈表只有該節點，最低頻率增加if (node.freq == minFreq && node.prev.prev == null && node.next.next == null) {minFreq++;}// 頻率加一node.freq++;// 從舊頻率對應鏈表刪除deleteNode(node);// 插入到新頻率鏈表尾部if (freqMap.get(node.freq) == null) {initFreqMap(node.freq);}addTail(node, freqMap.get(node.freq)[1]);return node.value;}public void put(int key, int value) {Node node = new Node();if (kvMap.get(key) != null) {node = kvMap.get(key);// 當前節點是最低頻率且此時最低頻率只有該節點，最低頻率增加if (node.freq == minFreq && node.prev.prev == null && node.next.next == null) {minFreq++;}// 頻率加一node.freq++;node.value = value;// 從舊頻率對應鏈表刪除deleteNode(node);} else {// 超出容量，移除最小頻率的節點if (capacity == 0) {Node head = freqMap.get(minFreq)[0];kvMap.remove(head.next.key);deleteNode(head.next);capacity = 1;}node.freq = 1;node.key = key;node.value = value;kvMap.put(key, node);minFreq = 1;capacity--;}if (freqMap.get(node.freq) == null) {initFreqMap(node.freq);}// 插入到新頻率鏈表尾部addTail(node, freqMap.get(node.freq)[1]);}public void initFreqMap(int freq) {Node head = new Node();Node tail = new Node();head.next = tail;tail.prev = head;Node[] arr = new Node[] {head, tail};freqMap.put(freq, arr);}public void deleteNode(Node node) {Node prevNode = node.prev;Node nextNode = node.next;prevNode.next = nextNode;nextNode.prev = prevNode;node.prev = null;node.next = null;}public void addTail(Node node, Node tail) {Node prevNode = tail.prev;prevNode.next = node;node.prev = prevNode;node.next = tail;tail.prev = node;}
}class Node {int freq;int key;int value;Node prev;Node next;
}

關鍵點

• 注意更新minFreq的值
• 雙向鏈表的相關操作
• 容量滿時插入節點需要對使用頻率最低的節點做刪除操作