两个重要的方法set get

用到两个数据结构 双端链表 ，HashMap 这两个一定是同步进行的

put分为

1. 检查链表size size满了 删除first
2. 不含 直接加入
3. 包含 value相同 删除再添加 value不同 删除原来的node 删除新的node

get

1. 没找到 返回-1
2. 设置为最近使用 （先删除再加入尾端） 返回node

import java.util.*;


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
        cap = k;
        int m = operators.length;
        List<Integer> res = new ArrayList<>();
        for(int i= 0;i<m;i++){
            int[] nums = operators[i];
            if(nums[0] == 1){
                if(nums.length == 3){
                    set(nums[1],nums[2]);
                }
            }else if (nums[0] ==2){
                if(nums.length == 2){
                    int temp = get(nums[1]);
                    res.add(temp);
                }
            }
        }
        int n = res.size();
        int[] ans = new int[n];
        for(int i = 0;i<n;i++){
            ans[i] = res.get(i);
        }
        
        return ans;
        
    }
    
    Map<Integer,Node> map = new HashMap<>(); 
    DoubleList list ;
    int cap ;
    public Solution(){
        list = new  DoubleList();
    }
    
    public void set(int key ,int value){
         Node node = new Node(key,value);

//         包含
        if(map.containsKey(key)&& value == map.get(key).value){
            
            list.setLastRecently(node);
        }
        
        if(map.containsKey(key)&& value != map.get(key).value){
            
            Node temp = map.get(key);
            list.deleteNode(temp);
            list.addList(node);
        }
        
//         检验数量
        if(list.size == cap){
          Node first =  list.deleteFirst();
            map.remove(first.key);
        }
//         不包含
        map.put(key,node);
        list.addList(node);
        
    }
    
    public  int get(int key){
        if(!map.containsKey(key)){
            return -1;
        }
        Node node = map.get(key);
        list.setLastRecently(node);
        return node.value;
    }
    
    
}

class DoubleList{
    
    Node head ;
    Node tail;
    int size = 0;
    public DoubleList(){
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
    }
    
  public void addList(Node x){
        Node prev = tail.prev;
        prev.next = x;
        x.prev = prev;
        x.next = tail;
        tail.prev = x;
         size++;
    }
    
   public void deleteNode(Node x){
        Node prev = x.prev;
        Node next = x.next;
        prev.next = next;
        next.prev =prev;
       size--;
    }
   public void setLastRecently(Node x){
        if(x == head){
            return;
        }
        deleteNode(x);
        addList(x);
    }
    
    public Node  deleteFirst(){
        Node fistNode = head.next;
        deleteNode(fistNode);
        return fistNode;
    }
    
}

class Node{
    int key ;
    int value;
    Node prev;
    Node next;
    public Node(int key ,int value){
        this.key = key;
        this.value = value;
    }
}