方法:HashMap+双向链表
解题思路:先通过遍历operators数组,将set和get操作区分开。利用HashMap存储双向链表中节点的key和节点的映射<key,Node>,其中Node为双向链表的节点<key,value>
get操作:先判断map中是否存在key,如果map不存在key 则返回-1;如果map存在key,先将该key的结点删除,然后再将此节点插入到链表的表头。
set操作:先判断map中是否存在key, 如果已经存在key,将val更新,并删除这个节点,再将node插入到表头,如果不存在key,先判断是否超出空间,如果超出先在链表和map删除最后一个节点,再将节点插入到表头,并将对应的映射添加到map中。

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public class Node{
        private int val;
        private int key;
        private Node pre =null;
        private Node next =null;
        private Node(int key,int val){
            this.val=val;
            this.key=key;
        }
    }

    private HashMap<Integer,Node> map = new HashMap();
    private Node head = new Node(-1,-1);  //头节点
    private Node tail = new Node(-1,-1);  //尾节点
    private int k=0;

    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.k = k;
        head.next = tail;
        tail.pre = head;

        int len = (int)Arrays.stream(operators).filter(x->x[0]==2).count();  //获取数组中开头为2(get操作)的元素个数        
        int res[] = new int[len];

        for(int i=0,j=0;i<operators.length;i++){
            if(operators[i][0] == 1){   //获取数组中开头为1(set操作)的元素个数
                set(operators[i][1],operators[i][2]);  //set(key,val)
            }else{   //获取数组中开头为2(get操作)的元素个数
                res[j++] = get(operators[i][1]);  //get(key)
            }
        }
        return res;
    }

    public void set(int key,int val){
        //判断是否存在key 
        Node node = null;
        if(map.containsKey(key)){   //如果已经存在key,将val更新,并删除这个节点,再将node插入到表头
            node = map.get(key);
            node.val = val;
            //删除该结点
            node.next.pre = node.pre;
            node.pre.next = node.next;
            //将node节点提到第一个
            moveToFirst(node);
        }else{  //如果不存在key,先判断是否超出空间,如果超出先在链表和map删除最后一个节点,再将节点插入到表头,并将对应的映射添加到map中
            if(map.size()==k){
                //在map中删除映射到最后一个节点的key
                int keyremove =tail.pre.key;
                map.remove(keyremove);
                //在链表中删除最后一个节点
                tail.pre.pre.next = tail;
                tail.pre = tail.pre.pre;
            }
            node = new Node(key,val);
            //在map中添加对新节点的映射
            map.put(key,node);
            //将节点插入到表头
            moveToFirst(node);

        }
    }

    public int get(int key){
        // 如果不存在key 则返回-1
        // 如果存在key,先将该key的结点删除,然后再将此节点插入到链表的表头
        if(!map.containsKey(key)){
            return -1;
        }else{
            Node node = map.get(key);
            //删除该结点
            node.next.pre = node.pre;
            node.pre.next = node.next;
            //插入到表头
            moveToFirst(node);
            return node.val;
        }
    }
    //将节点插入到表头
    public void moveToFirst(Node node){
            head.next.pre =node;
            node.next =head.next;
            node.pre =head;
            head.next=node;
    }
}