LFU 缓存

题目链接

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