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

import java.util.*;

//双向链表
class LRUCache{
    class DeListNode{    
        DeListNode pre;
        DeListNode next; 
        int key;
        public DeListNode(){
        }
     
        public DeListNode(int key){
            this.key = key;
        }
    }
    
    DeListNode head = new DeListNode();
    DeListNode tail = new DeListNode();  
    public LRUCache(){
        head.next = tail;
        tail.pre = head;
    }
    Map<Integer, Integer> map = new HashMap<>();
    //删除最后一个节点
    public int deleteLast(){        
        int res = tail.pre.key;
        DeListNode node = tail.pre.pre;
        tail.pre = node;
        node.next = tail;
        return res;
    }
    
    //加在最前面
    public void addFirst(DeListNode node){
        node.next = head.next;
        head.next.pre = node;
        head.next = node;
        node.pre = head;
    }
    
    //找到为key值的节点，并且移到最前面
    public void moveHead(int key){
        DeListNode node = head.next;
        while(node.next!=tail){            
            if(node.key == key){                
                break;               
            }
            node = node.next;
        }
            
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre=null;
        node.next=null;            
        addFirst(node);
    }
    
    public void set(int key, int value, int k){
        //已经有这个key，覆盖赋值，移到最前
        if(map.containsKey(key)){
            map.put(key, value);
            moveHead(key);          
        }else{  
            //没有这个值，加入map，加到链表最前
            map.put(key, value);   
            addFirst(new DeListNode(key));
            //大小超标，删除链表最后，删除map中
            if(map.size() > k){
                int num = deleteLast();
                map.remove(num);
            }
        }       
    }   
    public int get(int key){
        //没有，返回-1
        if(!map.containsKey(key)){
            return -1;
        }
        //有，得到值，链表移到最前
        int num = map.get(key);
        moveHead(key);
        return num;     
    }  
}
public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
      
    public int[] LRU (int[][] operators, int k) {
        // write code here
        List<int[]> list = new ArrayList<>();
        for(int[] a: operators){
            list.add(a);
        }
        LRUCache lru = new LRUCache();
        List<Integer> res = new ArrayList<>();
        for(int i = 0; i < list.size(); i++){
            if(list.get(i).length == 3){
                lru.set(list.get(i)[1], list.get(i)[2],k);
            }else{
                res.add(lru.get(list.get(i)[1]));
            }
        }
        
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
 
}