0460. LFU緩存 · ttttt

# 0460. LFU緩存 ## 題目地址(460. LFU緩存) <https://leetcode-cn.com/problems/lfu-cache/> ## 題目描述 ``` <pre class="calibre18">``` 請你為最不經常使用（LFU）緩存算法設計并實現數據結構。它應該支持以下操作：get 和 put。 get(key) - 如果鍵存在于緩存中，則獲取鍵的值（總是正數），否則返回 -1。 put(key, value) - 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。當緩存達到其容量時，則應該在插入新項之前，使最不經常使用的項無效。在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除最久未使用的鍵。「項的使用次數」就是自插入該項以來對其調用 get 和 put 函數的次數之和。使用次數會在對應項被移除后置為 0 。進階：你是否可以在 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 ``` ``` ## 前置知識 - 鏈表 - HashMap ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 `本題已被收錄到我的新書中，敬請期待～` [LFU（Least frequently used)](https://www.wikiwand.com/en/Least_frequently_used) 但內存容量滿的情況下，有新的數據進來，需要更多空間的時候，就需要刪除被訪問頻率最少的元素。舉個例子，比如說 cache 容量是 3，按順序依次放入 `1，2，1，2，1，3`， cache 已存滿 3 個元素 (1，2，3)，這時如果想放入一個新的元素 4 的時候，就需要騰出一個元素空間。用 LFU，這里就淘汰 3，因為 3 的次數只出現依次， 1 和 2 出現的次數都比 3 多。題中 `get` 和 `put` 都是 `O(1)`的時間復雜度，那么刪除和增加都是`O(1)`，可以想到用雙鏈表，和`HashMap`，用一個`HashMap, nodeMap,` 保存當前`key`，和 `node{key, value, frequent}`的映射。這樣`get(key)`的操作就是`O(1)`. 如果要刪除一個元素，那么就需要另一個`HashMap，freqMap，`保存元素出現次數`（frequent）`和雙鏈表`（DoublyLinkedlist）` 映射，這里雙鏈表存的是 frequent 相同的元素。每次`get`或`put`的時候，`frequent+1`，然后把`node`插入到雙鏈表的`head node, head.next=node`每次刪除`freqent`最小的雙鏈表的`tail node, tail.prev`。用給的例子舉例說明： ``` <pre class="calibre18">``` 1. put(1, 1), - 首先查找 nodeMap 中有沒有 key=1 對應的 value，沒有就新建 node(key, value, freq) -> node1(1, 1, 1), 插入 nodeMap，{[1, node1]} - 查找 freqMap 中有沒有 freq=1 對應的 value，沒有就新建 doublylinkedlist(head, tail), 把 node1 插入 doublylinkedlist head->next = node1. 如下圖， ``` ``` ![](https://img.kancloud.cn/41/d0/41d066177761cf72a18d4e6f8fa6f9b9_1473x1080.jpg) ``` <pre class="calibre18">``` 2. put(2, 2), - 首先查找 nodeMap 中有沒有 key=2 對應的 value，沒有就新建 node(key, value, freq) -> node2(2, 2, 1), 插入 nodeMap，{[1, node1], [2, node2]} - 查找 freqMap 中有沒有 freq=1 對應的 value，沒有就新建 doublylinkedlist(head, tail), 把 node2 插入 doublylinkedlist head->next = node2. 如下圖， ``` ``` ![](https://img.kancloud.cn/a9/ed/a9ed40a71ca074b0b911d2a5c8036f8a_1460x1080.jpg) ``` <pre class="calibre18">``` 3. get(1), - 首先查找 nodeMap 中有沒有 key=1 對應的 value，nodeMap:{[1, node1], [2, node2]}, 找到 node1，把 node1 freq+1 -> node1(1,1,2) - 更新 freqMap，刪除 freq=1，node1 - 更新 freqMap，插入 freq=2，node1 如下圖， ``` ``` ![](https://img.kancloud.cn/5a/19/5a19bf2fbc4f7a1c22753dfc833e1006_1429x1080.jpg) ``` <pre class="calibre18">``` 4. put(3, 3), - 判斷 cache 的 capacity，已滿，需要淘汰使用次數最少的元素，找到最小的 freq=1，刪除雙鏈表 tail node.prev 如果 tailnode.prev != null, 刪除。然后從 nodeMap 中刪除對應的 key。 - 首先查找 nodeMap 中有沒有 key=3 對應的 value，沒有就新建 node(key, value, freq) -> node3(3, 3, 1), 插入 nodeMap，{[1, node1], [3, node3]} - 查找 freqMap 中有沒有 freq=1 對應的 value，沒有就新建 doublylinkedlist(head, tail), 把 node3 插入 doublylinkedlist head->next = node3. 如下圖， ``` ``` ![](https://img.kancloud.cn/85/ff/85ff5343825d1f17574ad83575a9182c_1425x968.jpg) ``` <pre class="calibre18">``` 5. get(2) - 查找 nodeMap，如果沒有對應的 key 的 value，返回 -1。 6. get(3) - 首先查找 nodeMap 中有沒有 key=3 對應的 value，nodeMap:{[1, node1], [3, node3]}, 找到 node3，把 node3 freq+1 -> node3(3,3,2) - 更新 freqMap，刪除 freq=1，node3 - 更新 freqMap，插入 freq=2，node3 如下圖， ``` ``` ![](https://img.kancloud.cn/73/d2/73d2db02e42d904918f607aea84fd8a1_1412x973.jpg) ``` <pre class="calibre18">``` 7. put(4, 4), - 判斷 cache 的 capacity，已滿，需要淘汰使用次數最少的元素，找到最小的 freq=1，刪除雙鏈表 tail node.prev 如果 tailnode.prev != null, 刪除。然后從 nodeMap 中刪除對應的 key。 - 首先查找 nodeMap 中有沒有 key=4 對應的 value，沒有就新建 node(key, value, freq) -> node4(4, 4, 1), 插入 nodeMap，{[4, node4], [3, node3]} - 查找 freqMap 中有沒有 freq=1 對應的 value，沒有就新建 doublylinkedlist(head, tail), 把 node4 插入 doublylinkedlist head->next = node4. 如下圖， ``` ``` ![](https://img.kancloud.cn/78/31/78314bfec746b86d7a5fa62a7f03d473_1576x1071.jpg) ``` <pre class="calibre18">``` 8. get(1) - 查找 nodeMap，如果沒有對應的 key 的 value，返回 -1。 9. get(3) - 首先查找 nodeMap 中有沒有 key=3 對應的 value，nodeMap:{[4, node4], [3, node3]}, 找到 node3，把 node3 freq+1 -> node3(3,3,3) - 更新 freqMap，刪除 freq=2，node3 - 更新 freqMap，插入 freq=3，node3 如下圖， ``` ``` ![](https://img.kancloud.cn/be/8f/be8f7407309adaff7b663587b464ebf7_1434x1080.jpg) ``` <pre class="calibre18">``` 10. get(4) - 首先查找 nodeMap 中有沒有 key=4 對應的 value，nodeMap:{[4, node4], [3, node3]}, 找到 node4，把 node4 freq+1 -> node4(4,4,2) - 更新 freqMap，刪除 freq=1，node4 - 更新 freqMap，插入 freq=2，node4 如下圖， ``` ``` ![](https://img.kancloud.cn/ed/be/edbe76dedb9a243314eaedf1b94d7b5a_1474x1056.jpg) ## 關鍵點分析用兩個`Map`分別保存 `nodeMap {key, node}` 和 `freqMap{frequent, DoublyLinkedList}`。實現`get` 和 `put`操作都是`O(1)`的時間復雜度。可以用 Java 自帶的一些數據結構，比如 HashLinkedHashSet，這樣就不需要自己自建 Node，DoublelyLinkedList。可以很大程度的縮減代碼量。 ## 代碼（Java code） ``` <pre class="calibre18">``` public class LC460LFUCache { class Node { int key, val, freq; Node prev, next; Node(int key, int val) { this.key = key; this.val = val; freq = 1; } } class DoubleLinkedList { private Node head; private Node tail; private int size; DoubleLinkedList() { head = new Node(0, 0); tail = new Node(0, 0); head.next = tail; tail.prev = head; } void add(Node node) { head.next.prev = node; node.next = head.next; node.prev = head; head.next = node; size++; } void remove(Node node) { node.prev.next = node.next; node.next.prev = node.prev; size--; } // always remove last node if last node exists Node removeLast() { if (size > 0) { Node node = tail.prev; remove(node); return node; } else return null; } } // cache capacity private int capacity; // min frequent private int minFreq; Map<Integer, Node> nodeMap; Map<Integer, DoubleLinkedList> freqMap; public LC460LFUCache(int capacity) { this.minFreq = 0; this.capacity = capacity; nodeMap = new HashMap<>(); freqMap = new HashMap<>(); } public int get(int key) { Node node = nodeMap.get(key); if (node == null) return -1; update(node); return node.val; } public void put(int key, int value) { if (capacity == 0) return; Node node; if (nodeMap.containsKey(key)) { node = nodeMap.get(key); node.val = value; update(node); } else { node = new Node(key, value); nodeMap.put(key, node); if (nodeMap.size() == capacity) { DoubleLinkedList lastList = freqMap.get(minFreq); nodeMap.remove(lastList.removeLast().key); } minFreq = 1; DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList()); newList.add(node); freqMap.put(node.freq, newList); } } private void update(Node node) { DoubleLinkedList oldList = freqMap.get(node.freq); oldList.remove(node); if (node.freq == minFreq && oldList.size == 0) minFreq++; node.freq++; DoubleLinkedList newList = freqMap.getOrDefault(node.freq, new DoubleLinkedList()); newList.add(node); freqMap.put(node.freq, newList); } } ``` ``` ## 參考（References） 1. [LFU(Least frequently used) Cache](https://www.wikiwand.com/en/Least_frequently_used) 2. [Leetcode discussion mylzsd](https://leetcode.com/problems/lfu-cache/discuss/94547/Java-O(1)-Solution-Using-Two-HashMap-and-One-DoubleLinkedList) 3. [Leetcode discussion aaaeeeo](https://leetcode.com/problems/lfu-cache/discuss/94547/Java-O(1)-Solution-Using-Two-HashMap-and-One-DoubleLinkedList)