460. LFU 缓存 (opens new window)

1.双向链表桶+TreeMap

思路：本质上LFU就是需要维护多个频次的LRU双向链表。

• Node维护一个成员变量cnt，记录当前节点的使用频次。
• Map维护key到Node节点的映射。同时通过size()方法来判断当前LFUCache的容量是否超载。
• TreeMap中key为节点使用频次，value为相同频次的双向链表的哨兵节点。(另一种做法维护一个全局变量，如果minFreq对应的双向链表删除，则minFreq++)

通过TreeMap的firstKey获取当前使用频次最低的节点。

注意，①get调用更新使用频次②put插入新的节点都会触发双向链表中节点的移除，都需要判断旧的双向频次链表是否为空删除：

class LFUCache {
   private static class Node{
        int cnt;
        int key,value;
        Node pre,next;
        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    int capacity;
    Map<Integer,Node> keyToNode;
    TreeMap<Integer,Node> cntToHead;
    public LFUCache(int capacity) {
        keyToNode=new HashMap<>();
        cntToHead=new TreeMap<>();
        this.capacity=capacity;
    }

    public int get(int key) {
        if(!keyToNode.containsKey(key)) return -1;
        Node node=keyToNode.get(key);
        int cnt=node.cnt;
        node.cnt=cnt+1;
        //删除在旧计数的双向链表
        node.pre.next=node.next;
        node.next.pre=node.pre;
        Node oldHead=cntToHead.get(cnt);
        if(oldHead.next==oldHead) cntToHead.remove(cnt);
        //插入新计数的双向链表
        if(!cntToHead.containsKey(cnt+1)){
            Node head=new Node(0,0);
            head.next=node;
            head.pre=node;
            node.pre=head;
            node.next=head;
            cntToHead.put(cnt+1,head);
        }
        else{
            Node head=cntToHead.get(cnt+1);
            node.pre=head;
            node.next=head.next;
            head.next=node;
            node.next.pre=node;
        }
        return node.value;
    }

    public void put(int key, int value) {
        //存在key,则更新使用次数
        if(keyToNode.containsKey(key)){
            keyToNode.get(key).value=value;
            get(key);
        }
        else{
            Node node=new Node(key,value);
            node.cnt=1;
            //移除LFU
            if(keyToNode.size()==this.capacity){
                int min=cntToHead.firstKey();
                Node head=cntToHead.get(min);
                Node remove=head.pre;
                remove.pre.next=remove.next;
                remove.next.pre=remove.pre;
                if(head.pre==head) cntToHead.remove(min);
                keyToNode.remove(remove.key);
            }
            //加入频次为1的双向链表
            if(!cntToHead.containsKey(1)){
                Node head=new Node(0,0);
                head.next=node;
                head.pre=node;
                node.pre=head;
                node.next=head;
                cntToHead.put(1,head);
            }
            else{
                Node head=cntToHead.get(1);
                node.pre=head;
                node.next=head.next;
                head.next=node;
                node.next.pre=node;
            }
            keyToNode.put(key,node);
        }
    }
}