一、题目内容

二、题解

解法1：

思路

代码

public class Solution {
    public int[] LFU (int[][] operators, int k) {
        // write code here
        List<Integer> ansList = new ArrayList<Integer>();
        LFUCache cache = new LFUCache(k);
        for(int[] operator: operators){
            int operation = operator[0];
            int key = operator[1];
            if(operation == 1){
                cache.set(key,operator[2]);
            }else if(operation == 2){
                ansList.add(cache.get(key));
            }
        }
        int[] ans = new int[ansList.size()];
        for(int i = 0;i<ansList.size();i++){
            ans[i] = ansList.get(i);
        }
        return ans;
    }
    //-------LFUCache------------------------------//
    class LFUCache{
        Map<Integer,Bucket> cacheMap = new HashMap<Integer,Bucket>();
        Bucket head,tail;
        int cap;
        int size;
        public LFUCache(int cap){
            this.cap = cap;
            size = 0;
            head = new Bucket(-1);
            tail = new Bucket(-1);
            head.next = tail;
            tail.pre = head;
        }
        public int get(int key){
            if(cacheMap.containsKey(key)){
                Bucket cur = cacheMap.get(key);
                Bucket target = null;
                //建新桶
                if(cur.next.idx != cur.idx+1){
                    target = new Bucket(cur.next.idx+1);
                    target.pre = cur;
                    target.next = cur.next;
                    cur.next.pre = target;
                    cur.next = target;
                }else{
                    target = cur.next;
                }
                Item remove = cur.remove(key);
                target.put(remove.key,remove.value);
                cacheMap.put(key,target);
                //清空 空桶
                deleteIfEmpty(cur);
                return remove.value;
            }
            return -1;
        }
        public void set(int key,int value){
            if(cap == 0){
                return;
            }
            if(cacheMap.containsKey(key)){
                Bucket cur = cacheMap.get(key);
                cur.put(key,value);
                get(key);//idx+1
            }else{
                //满，移除
                if(size == cap){
                    Bucket cur = head.next;
                    Item item = cur.clearLast();
                    cacheMap.remove(item.key);
                    size--;
                    deleteIfEmpty(cur);
                }else{
                    Bucket first = null;
                    //新建1号桶
                    if(head.next.idx!=1){
                        first = new Bucket(1);
                        first.next = head.next;
                        first.pre = head;
                        head.next.pre = first;
                        head.next = first;
                    }else{
                        first = head.next;
                    }
                    first.put(key,value);
                    cacheMap.put(key,first);
                    size++;
                }
            }
        }
        void deleteIfEmpty(Bucket cur){
            if(cur.isEmpty()){
                cur.pre.next = cur.next;
                cur.next.pre = cur.pre;
                cur = null;
            }
        }
    }
    //------Item, Bucket------------------------//
    class Item{
        Item pre,next;
        int key,value;
        public Item(int k,int v){
            this.key = k;
            this.value = v;
        }
    }
    class Bucket{
        Bucket pre,next;
        int idx;
        Item head,tail;
        Map<Integer,Item> dic = new HashMap<Integer,Item>();
        public Bucket(int idx) {
            this.idx = idx;
            head = new Item(-1, -1);
            tail = new Item(-1, -1);
            head.next = tail;
            tail.pre = head;
        }
        void put(int key,int value){
            Item item = null;
            if(dic.containsKey(key)){
                item = dic.get(key);
                item.value = value;
                //移除
                item.pre.next = item.next;
                item.next.pre = item.pre;
            }else{
                item = new Item(key,value);
                dic.put(key,item);
            }
            item.next = head.next;
            item.pre = head;
            head.next.pre = item;
            head.next = item;
        }
        Item remove(int key){
            if(dic.containsKey(key)){
                Item item = dic.get(key);
                item.pre.next = item.next;
                item.next.pre = item.pre;
                dic.remove(key);
                return item;
            }
            return null;
        }
        Item clearLast(){
            Item item = tail.pre;
            item.pre.next = item.next;
            item.next.pre = item.pre;
            dic.remove(item.key);
            return item;
        }
        boolean isEmpty(){
            return dic.size() == 0;
        }
    }
}