146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache

输入
[“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

class LRUCache {
    class Node{
        int k,v;
        Node l,r;
        Node(int _k,int _v){
            k=_k;
            v=_v;
        }
    }
    int n;
    Node head,tail;
    Map map;
    public LRUCache(int capacity) {
        n=capacity;//初始化容量
        map=new HashMap<>();//初始化hashmap
        head=new Node(-1,-1);//哨兵头
        tail=new Node(-1,-1);//哨兵尾
        head.r=tail;//维护关系
        tail.l=head;
    }

    public int get(int key) {
        if(map.containsKey(key)){//存在此键
            Node node=map.get(key);//拿到节点
            refresh(node);//进行读的操作，更新其位置，至于双向链表头部位置(head后)
            return node.v;
        }
        return -1;
    }

    public void put(int key, int value) {
        Node node=null;
        if(map.containsKey(key)){//已经包含此键则进行更新
            node=map.get(key);
            node.v=value;
        }else {
            if(map.size()==n){//如果容量已满则释放尾节点（tail前）
                Node del=tail.l;
                map.remove(del.k);//从map中删除
                delete(del);//从链表中删除
            }
            node=new Node(key,value);
            map.put(key,node );//存入新的键值对
        }
        refresh(node);//进行存的操作，刷新状态至head后
    }
    void refresh(Node node){
        delete(node);
        node.r=head.r;
        node.l=head;
        head.r.l=node;
        head.r=node;
    }
    void delete(Node node){
        if(node.l!=null){
            Node left=node.l;
            left.r=node.r;
            node.r.l=left;
        }
    }

}

尽管有现成的实现api，但是面试时需要手动实现来展现你的能力，这里实现了一个双向链表，需要维护每个节点左右的关系，同时建立了head和tail两个哨兵节点来简化边界条件。存储键值对则使用hashmap，手动实现需要解决哈希冲突比较麻烦，因此调用现成的api。