题解 | #LFU缓存结构设计#

java版本

核心：双Hashmap， 一个用作set，get操作，一个用作队列。

用作队列的HashMap 键为操作的次数，值为一个双链表链接所有具有相同操作的节点。

注意有插入和删除操作时应先判断 键 是否存在，删除最不常使用节点时应判断链表是否为空，为空应删除。

import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class Node{
        private int key, value, cnt;
        private Node pre, next;

        public Node(int key, int value){
            this.key = key;
            this.value = value;
            this.cnt = 1;
            this.pre = this.next = null;
        }
    }

    class Que{
        private Node head;
        private Node tail;

        public Que(Node head, Node tail){
            this.head = head;
            this.tail = tail;
            this.head.next = this.tail;
            this.tail.pre = this.head;
        }
    }

    class Lfu{
        private HashMap<Integer, Node> hashmap;
        private HashMap<Integer, Que> que;
        int size;
        int least;

        public Lfu(int size){
            this.hashmap = new HashMap<>();
            this.que = new HashMap<>();
            this.size = size;
            this.least = 1;
        }

        public void refresh(Node node){
            if(this.que.containsKey(node.cnt)){
                    Que q1 = this.que.get(node.cnt);
                    node.next = q1.head.next;
                    node.pre = q1.head;
                    q1.head.next.pre = node;
                    q1.head.next = node;
                }else{
                    Que q2 = new Que(new Node(-1, -1), new Node(-1, -1));
                    node.next = q2.head.next;
                    node.pre = q2.head;
                    node.next.pre = node;
                    q2.head.next = node;
                    this.que.put(node.cnt, q2);
                }
        }

        public void set(int key, int value){
            if(get(key) != -1){
                Node node = this.hashmap.get(key);
                node.value = value;
                node.cnt += 1;
                this.hashmap.put(key, node);
            }else{
                if(this.size == 0){
                    Que q = this.que.get(this.least);
                    this.hashmap.remove(q.tail.pre.key);
                    q.tail.pre.pre.next = q.tail;
                    q.tail.pre = q.tail.pre.pre;

                    if(q.head.next == q.tail){
                        this.que.remove(this.least);
                        while(!this.que.containsKey(this.least)) this.least++;
                    }
                }else{
                    this.size --;
                }
                Node node = new Node(key, value);
                this.hashmap.put(key, node);
                this.least = 1;

                refresh(node);
            }
        }

        public int get(int key){
            if(hashmap.containsKey(key)){
                Node node = this.hashmap.get(key);
                node.cnt ++;
                node.pre.next = node.next;
                node.next.pre = node.pre;
                refresh(node);
                return node.value;
            }
            return -1;
        }
    }

    public int[] LFU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> arraylist = new ArrayList<>();
        int[] res;
        Lfu lfu = new Lfu(k);
        for(int i = 0; i < operators.length; i++){
            if(operators[i][0] == 1){
                lfu.set(operators[i][1], operators[i][2]);
            }else{
                arraylist.add(lfu.get(operators[i][1]));
            }
        }
        res = new int[arraylist.size()];
        for(int i = 0; i < arraylist.size(); i++) res[i] = arraylist.get(i);
        return res;
    }
}