两种解题方式

一、先整个题目的解答架构

    public int[] LRU (int[][] operators, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if(operators==null||operators.length==0
                ||operators[0].length==0) return new int[]{};
        int rows = operators.length;
        int cols = operators[0].length;
        LRUCache cache = new LRUCache(k);
        for(int opr = 0;opr<rows;opr++){
            int[] opration = operators[opr];
            if(opration[0]==1){
                //set操作
                cache.set(opration[1],opration[2]);
            }else if(opration[0]==2){
                //get操作
                res.add(cache.get(opration[1]));
            }
        }
        //接收答案
        int[] resArr = new int[res.size()];
        for(int i = 0;i<res.size();i++){
            resArr[i] = res.get(i);
        }
        return resArr;
    }

二、缓存设计

1. 继承LinkedHashMap，背靠大树好乘凉。

    public  class LRUCache extends LinkedHashMap<Integer,Integer>{
        int cap;
        public LRUCache(int k){
            super(k,0.75f,true);//需要注意，只有accessOrder为ture才是LRU，否则是按插入顺序，不会根据访问进行调整
            this.cap = k;
        }
        public void set(int key,int value){
            this.put(key,value);
        }
        @Override
        public Integer get(Object key) {
            if(!this.containsKey(key)) return -1;
            return super.get(key);
        }
        //增强方法，在节点插入后回调，如果返回true就将最老那个节点删除
        @Override
        protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
            return this.size()>cap;
        }
    }

2. 自己设计，基于LRU的特性

   • 能够O(1)进行set,get,肯定得用到哈希表
   • 在一个节点操作后移动到最新位置，能够在集合中进行随机存取，肯定是链表，我规定尾巴就是最新的节点，剔除的时候剔除头节点

   2.1先造出这么个链表

需要具备这些api:

• addNode(将节点插入尾巴)

• moveNodeToTail(将节点从原来地方取出来，丢到尾巴处)

• removeHead(剔除Least Recent Used的节点，也就是头节点)

    public static class Node{
        Node pre,next;
        int value;
        int key;
        public Node(int key,int value){
            this.key = key;
            this.value = value;
        }
    }
    public static class DoubleLinkedList{
        Node head,tail;
        //将节点加到尾巴
        public void addNode(Node node){
            if(head==null){
                head = node;
                tail = node;
            }else{
                node.pre = tail;
                tail.next = node;
                tail = tail.next;
                tail.next = null;
            }
        }
        //将一个节点移动到尾巴
        public void moveNodeToTail(Node node){
            if(head==null||node==tail){
                return;
            }
            if(node==head){
                removeHead();
            }else{
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            addNode(node);
        }
        //去头
        public Node removeHead(){
            if(head==null){
                return null;
            }
            Node res = head;
            if(head==tail){
                head = null;
                tail = null;
            }else{
                head = head.next;
                head.pre = null;
            }
            return res;
        }
    }

  2.2 完事具备，可以写LRUCache了

    public static class LRUCache{
        Map<Integer,Node> keyToNode = new HashMap<>();
        DoubleLinkedList doubleList = new DoubleLinkedList();
        int cap;
        int size;
        public LRUCache(int cap){
            this.cap = cap;
        }
        public void set(int key,int value){
            if(keyToNode.containsKey(key)){
                Node shot = keyToNode.get(key);
                shot.value = value;
                doubleList.moveNodeToTail(shot);
                return;
            }
            Node cur = new Node(key,value);
            keyToNode.put(key,cur);
            if(size>=cap){
                //剔除一个
                keyToNode.remove(doubleList.removeHead().key);
                size--;
  
            }
            doubleList.addNode(cur);
            size++;
        }
        public int get(int key){
            Node res = null;
            if(!keyToNode.containsKey(key)) return -1;
            res = keyToNode.get(key);
            doubleList.moveNodeToTail(res);
            return res.value;
        }
  
    }