腾讯常见算法测试题：设计并实现一个满足LRU（最近最少使用）缓存约束的数据结构

请设计并实现。满足 LRU（最近最少使用）缓存约束的数据结构。

实现 LRUCache 类：

• LRUCache(intcapacity) 使用正整数作为容量来初始化 LRU 缓存
• int get(int key) 如果缓存中存在关键字，则获取关键字的值，否则返回-1。
• void put(int key, int value) 如果关键字key已经存在，则更改其数据value值；如果不存在，则将键值放入缓存中。如果插入操作超出了关键字的数量容量，则应驱逐最旧的未使用的关键字。

获取和设置函数的平均时间复杂度必须为O(1)。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

对于这个问题，经常出现。在采访中，不少朋友反映在原题上遇到了。

LRU，最近最少使用，即最近使用的数据有用，可以使用双链表+Hashmap答，双链表用于存储LRUCache数据，Hashmap达到平均时间复杂度为 O(1)。

• 每次从链表末尾添加一个元素，末尾的元素就是最后使用的元素。
• 通过哈希表可以在节点上快速定位特定的key。

对于双向链表你需要做什么？

• 首先是链表的初始化。为了方便对i的处理，创建虚拟头节点和尾节点。
• 添加项目时，将其放在链表的底部，表示该项目最近被使用过。
• 删除双向链表中的节点。
• 删除并返回头节点，也就是说最长时间没有被使用的元素将被删除。
• 返回链接列表。当前长度

LRU缓存有哪些方法？

• 构造函数初始化方法
• get 和 put 方法
• makeRecently 设置元素最近使用的方法。哈希表已经有元素
• addRecently添加最近使用的元素，更新map的同时删除最长时间没有使用的元素

完整代码如下：

class Node {

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

class DoubleList {
    //虚拟出头节点和尾结点
    private Node head, tail;
    private int size;

    //初始化双链表
    public DoubleList() {
        //虚拟头结点
        head = new Node(0, 0);
        //虚拟头结点
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }

    //要加到链表尾部，且越靠近链表尾部，越表示最近使用过
    public void addLast(Node x) {
        //比如当前链表为：head <-> 1 <-> tail，加入结点x = 2
        x.prev = tail.prev;
        // 完成结点2指向两端的箭头  head <-> 1 <- 2 -> tail; 此时tail.pre = 结点1还未断开
        x.next = tail;
        //head <-> 1 <-> 2 -> tail;
        tail.prev.next = x;
        //head <-> 1 <-> 2 <-> tail;
        tail.prev = x;
        //更新链表长度
        size++;
    }

    // 删除指定结点
    public void remove(Node x) {
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    // 删除并返回头结点
    public Node removeHead() {
        if (head.next == tail) {
            return null;
        }
        Node first = head.next;
        // size在remove中更新了
        remove(first);
        // 用作在哈希表中移除最久未使用的数据值
        return first;
    }

    // 获取链表长度
    public int getSize() {
        return size;
    }
}

public class LRUCache {

    private Map<Integer, Node> map;
    private DoubleList doubleList;
    private int cap;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.doubleList = new DoubleList();
        this.cap = capacity;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            // 先将key标记为最近使用，再返回value
            makeRecently(key);
            return map.get(key).val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            deleteKey(key); // 从原map中移除该key
            addRecently(key, value); // 更新最近使用
            return;
        }

        int size = doubleList.getSize();
        if (size == cap) { // 说明需要移除最久未使用的元素了
            removeLeastRecently();
        }
        addRecently(key, value); //添加新的元素进来
    }


    public void makeRecently(int key) { // 将某个key标记为最近使用的元素（map中已存在的）
        Node x = map.get(key);
        doubleList.remove(x); // 先从双链表删除
        doubleList.addLast(x); // 再添加到链表末尾， 因为尾部是最近使用过的元素
    }

    public void addRecently(int key, int value) { // 添加最近使用过的元素
        Node x = new Node(key, value);
        doubleList.addLast(x);
        map.put(key, x);  //更新map
    }

    public void deleteKey(int key) {
        Node x = map.get(key);
        map.remove(key);
        doubleList.remove(x); // 在map中和cache中同时删除
    }

    // 删除最久未使用的元素
    public void removeLeastRecently() {
        // 最久未使用的一定在链表头部
        Node oldNode = doubleList.removeHead();
        int oldKey = oldNode.key;
        map.remove(oldKey);
    }
}