首先，我们先来看一下LRU缓存结构是什么
LRU是Least Recently Used 的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。

有两操作：
set(key,value) 插入操作,缓存区有限定的大小，如果已满的话，需要将最近最久未使用的页面淘汰以后再插入。
get(key) 查找给定的key对应的value是什么
例：缓存区大小为3
set(1,2)
set(2,5)
set(3,2)
get(1)
set(4,1)
get(2)

一开始 我们放入(1,2),(2,5),(3,2),然后查询key = 1之后(2,5),(3,2),(1,2)，1变成最近访问过的了。
再想插入(4,1)，但是目前缓存区满了。要淘汰掉一个，最近最久未使用的页面是(2,5)，那就淘汰(2,5)、变成(3,2),(1,2),(4,1)
之后想查询key=2，但是目前缓存区里没有key=2的界面，那就返回-1。
要求set操作和get操作的时间复杂度都是 O(1)，get操作O(1)复杂度比较好说，就是查找key对应的value的话，我们语言中直接有对应的容器的实现，比如c++中的unordered_map,java中的hashmap，python中的dict，都可以直接通过key查找到对应的value
然后就是怎么样才能知道哪个页面是最近最近未使用的页面了。以及进行get操作以后，对应的key是被使用过了。所以要更新一下这个结点的状态。
那我们怎么进行这个操作呢？每次新插入一个结点的时候，我们把这个结点放在双端链表的末尾，进行get操作查询某个key的时候，也把key对应的结点放在双端链表的末尾。
为了能快速的找到一个key对应的结点，我们的map里的存的键值对是<key,node>。node里存了value，前后指针。这样的话，我们就可以通过O(1)的复杂度来完成get和set操作了。

c++

class Solution {
public:
     struct node{
        int key;
        int value;
        node* pre = NULL;
        node* next = NULL;
    };
    unordered_map<int,node*> M;
    node* front;
    node* end;

    void push_back(node* val)
    {
        node* pre = end->pre;
        pre->next = val;
        val->pre = pre;
        val->next = end;
        end->pre = val;
    }
    void delete_front()
    {
        node* first = front->next;
        if(first == end){return;}//如果链表中没有元素，不删除
        M.erase(first->key);
        front->next = first->next;
        first->next->pre = front;
        delete first;
    }
    vector<int> LRU(vector<vector<int> >& operators, int k) {
        front = new node;
        end = new node;
        front->next = end;
        end->pre = front;
        end->key = -1;
        vector<int> ans;
        for(int i = 0 ; i < operators.size() ; i++)
        {
            if(operators[i][0] == 1)//插入操作
            {
                node *t = new node;
                t->key = operators[i][1];
                t->value = operators[i][2];
                t->next = NULL;
                if(M.size() < k)//可以直接插入
                {
                     M[t->key] = t;
                     push_back(t);
                }
                else{//要替换一下,先把链表最前面的元素删掉，然后把节点放到链表后面
                    delete_front();
                    M[t->key] = t;
                     push_back(t);
                }
            }
            else if(operators[i][0] == 2)//查询操作
            {
                //先把要查询的key对应的value查出来
                if(M.count(operators[i][1])>0)//如果存在这个节点
                {
                    node * t = M[operators[i][1]];
                    ans.push_back(t->value);
                    //把当前的t节点删掉，然后放到队列的末尾
                    node * pre = t->pre;
                    pre->next = t->next;
                    pre->next->pre = pre;
                    push_back(t);

                }
                else{//不存在返回-1
                    ans.push_back(-1);
                }
            }
        }
        return ans;
    }
};

java

import java.util.*;
public class Solution {
    class Node {
        int key;
        int value;
        Node pre = null;
        Node next = null;
    }

    HashMap<Integer, Node> M = new HashMap<Integer, Node>();
    static Node head;
    static Node tail;

    static void delete(Node now) {
        Node PRE = now.pre;
        Node NEXT = now.next;
        PRE.next = NEXT;
        NEXT.pre = PRE;
    }
    static void insertLast(Node now) {
        Node PRE = tail.pre;
        PRE.next = now;
        now.pre = PRE;
        now.next = tail;
        tail.pre = now;
    }
public int[] LRU (int[][] operators, int k) {
        int count = 0;
        ArrayList<Integer> ans = new ArrayList<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
        for (int i = 0; i < operators.length; i++) {
            int op = operators[i][0];
            if (op == 1) { // set
                if (count < k) {
                    count++;
                } else { // 删除链表首位元素
                    Node first = head.next;
                    M.remove(first.key);
                    delete(first);
                }
                // 插入当前元素
                Node now = new Node();
                now.key = operators[i][1];
                now.value = operators[i][2];
                M.put(operators[i][1], now);
                insertLast(now);
            } else if (op == 2) { // get
                int key = operators[i][1];
                // 看一下有没有对应的key
                if (!M.containsKey(key)) {
                    ans.add(-1);
                } else {
                    // 查对应value，放入
                    Node now = M.get(key);
                    ans.add(now.value);
                    // 把当前节点移到链表末尾
                    delete(M.get(key));
                    insertLast(M.get(key));
                }
            }
        }
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i);
        }
        return result;
    }
}