题目

  运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

1. LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
3. void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

• 示例：
  输入
  [“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
  提示：
  1 <= capacity <= 3000
  0 <= key <= 3000
  0 <= value <= 104
  最多调用 3 * 104 次 get 和 put

题解

  LRU(Least Recently Used)，最近最少使用。淘汰掉最近最少使用的缓存，最新的缓存放置于头部。所以我们可以考虑使用双向链表来存储缓存数据，但是单纯的依靠双向链表，在寻找值得时候需要遍历，这种方式比较耗时，所以我们可以采用HashMap来存储key与节点得关系，能达到O(1)的查找速度。

• 代码实现：

class LRUCache {
   
	//缓存节点
    private class CacheNode{
   
        CacheNode prev;
        CacheNode next;
        int key;
        int value;
        private CacheNode(int key,int value){
   
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }
	//缓存容量
    private int capacity;
    //key与节点映射
    private Map<Integer,CacheNode> valNodeMap;
    private CacheNode head = new CacheNode(-1,-1);
    private CacheNode tail = new CacheNode(-1,-1);

    public LRUCache(int capacity) {
   
        this.capacity = capacity;
        valNodeMap = new HashMap(capacity);
        this.head.next = tail;
        this.tail.prev = head;
    }
    
    public int get(int key) {
   
        if(!valNodeMap.containsKey(key)){
   
            return -1;
        }
        CacheNode node = valNodeMap.get(key);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        moveToTail(node);
        return node.value;
    }
    
    public void put(int key, int value) {
   
        if(get(key)!=-1){
   
            valNodeMap.get(key).value = value;
            return;
        }
        CacheNode node = new CacheNode(key,value);
      
        if(valNodeMap.size() == capacity){
   
            //淘汰
            valNodeMap.remove(head.next.key);
            head.next.next.prev = head;
            head.next = head.next.next;
        }
        valNodeMap.put(key,node);
        //追加
        moveToTail(node);
    }

    public void moveToTail(CacheNode node){
   
        node.prev = this.tail.prev;
        this.tail.prev.next = node;
        node.next = this.tail;
        this.tail.prev = node;
    }
}

/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */