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

import java.util.*;
 class LruCache{
    class DListNode{
            int key;
            int value;
            DListNode prev;
            DListNode next;
            public DListNode(){}
            public DListNode(int _key,int _value){key = _key;value = _value;}
        }

    Map<Integer,DListNode> cache;
    int capacity = 0,size = 0;
    static DListNode head,tail;

    public LruCache(int capacity){
        this.capacity = capacity;
        cache = new HashMap<>();
        size = 0;
        head = new DListNode();
        tail = new DListNode();
        head.next = tail;
        tail.prev = head;
    }
        public void set(int key,int value){
        DListNode node = cache.get(key);
        if(node == null){
            DListNode add = new DListNode(key,value);
            insertToHead(add);
            ++size;
            cache.put(key,add);
            if(size > capacity){
                DListNode rnode = removeTail();
                cache.remove(rnode.key);
                --size;
            }
        }
        else{
            node.value = value;
            moveToHead(node);
        }
    }
    public int get(int key){
        DListNode node = cache.get(key);
        if(node == null){
            return -1;
        }
        else {
            moveToHead(node);
            return node.value;
        }
    }
    public void remove(DListNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    public void insertToHead(DListNode add){
        add.prev = head;
        head.next.prev = add;
        add.next = head.next;
        head.next = add; 
    }
    public void moveToHead(DListNode node){
        remove(node);
        insertToHead(node);
    }
    public DListNode removeTail(){
        DListNode node = tail.prev;
        remove(node);
        return node;
    }
}

public class Solution {   
    public int[] LRU (int[][] operators, int k) {
        int M = operators.length;
        List<Integer> res = new ArrayList<>();
        LruCache lru = new LruCache(k);

        for(int i = 0;i<M;i++){
            if(operators[i][0] == 1){
                int key = operators[i][1];
                int value = operators[i][2];
                lru.set(key,value);
            }
            else{
                int key = operators[i][1];
                res.add(lru.get(key));
            }            
        }
        int n = res.size();
        int[] fin = new int[n];
        for(int i = 0;i<n;i++){
            fin[i] = res.get(i);
        }
        return fin;
    }
}