题目链接

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的值
• 双向链表的相关操作
• 容量满时插入节点需要对使用频率最低的节点做删除操作