146. LRU 缓存

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) 的平均时间复杂度运行。

输入输出

输入
["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);//capacity为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

基本思路

使用哈希链表的结构LinkedHashMap labuladong的解析 leetcode官方题解

代码分成以下几个部分：

1. 定义DlinkedNode双向链表结构

2. 写关于DlinkedNode的常用操作(四个)

   1. 添加node节点到头部
   2. 删除节点node
   3. 当get()访问一个节点之后移动到队首
   4. 移出队尾的节点

3. 写LRUCache的两个方法get() put()

举个例子：
(头:最近使用)          (尾:最近不使用)
head -> tail                           //LRUCache lRUCache = new LRUCache(2)
head -> node1 -> tail                  //lRUCache.put(1, 1);
head -> node2 -> node1 -> tail         //lRUCache.put(2, 2);
head -> node1 -> node2 -> tail         //lRUCache.get(1);
head -> node3 -> node1 -> tail         //lRUCache.put(3, 3);
(关键点:如果put一个key相等value不等的节点 相当于一次访问 要移到队列头部)

时间复杂度：对于 put 和 get 都是 O(1)

空间复杂度：O(capacity)，因为哈希表和双向链表最多存储 capacity+1 个元素

java实现

//leetcode官方代码(较简短)
class LRUCache {

    class DlinkedNode{
        int key;
        int value;
        DlinkedNode prev;
        DlinkedNode next;
        public DlinkedNode(){}
        public DlinkedNode(int _key, int _value){
            key = _key;
            value = _value;
        }
    }

    public HashMap<Integer, DlinkedNode> cache = new HashMap<Integer, DlinkedNode>();
    public int size;
    public int capacity;
    public DlinkedNode head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        head = new DlinkedNode();
        tail = new DlinkedNode();
        head.next = tail;
        tail.prev = head;
    }


    // 添加node节点到头部
    public void addtoHead(DlinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    // 删除节点node
    public void removeNode(DlinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 当get()访问一个节点之后移动到队首
    public void movetoHead(DlinkedNode node){
        removeNode(node);
        addtoHead(node);
    }

    // 移出队尾的节点
    public DlinkedNode removeTail(){
        DlinkedNode node = tail.prev;
        removeNode(node);
        return node;
    }
    
    public int get(int key) {
        DlinkedNode node = cache.get(key);
        if(node == null) return -1;
        movetoHead(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        DlinkedNode node = cache.get(key);
        if(node == null){
            DlinkedNode newnode = new DlinkedNode(key, value);
            cache.put(key, newnode);
            addtoHead(newnode);
            size++;
            if(size > capacity){
                DlinkedNode deletenode = removeTail();
                cache.remove(deletenode.key);
                size--;
            }
        }
        else{
            node.value = value;
            movetoHead(node);
        }
    }
}

//labuladong解法
class LRUCache {
    class Node{
        public int key, val;
        public Node next, prev;
        public Node(int k, int v){
            this.key = k;
            this.val = v;
        }
    }

    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){
            x.prev = tail.prev;
            x.next = tail;
            tail.prev.next = x;
            tail.prev = x;
            size++;
        }

        // 删除链表中的节点x
        public void remove(Node x){
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }

        // 删除链表中第一个节点
        public Node removeFirst(){
            if(head.next == tail) return null;
            Node first = head.next;
            remove(first);
            return first;
        }

        public int size(){
            return size;
        }
    }
    
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;

    // 将某个key提升为最近使用的
    private void makeRecently(int key){
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    // 添加最近使用的元素
    private void addRecently(int key, int val){
        Node x = new Node(key, val);
        cache.addLast(x);
        map.put(key, x);        
    }

    // 删除某个key
    private void deleteKey(int key){
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    // 删除最久未使用的元素
    private void removeLeastRecently(){
        Node removeNode = cache.removeFirst();
        int deleteKey = removeNode.key;
        map.remove(deleteKey);

    }

    public LRUCache(int capacity) {
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    
    public int get(int key) {
        if(!map.containsKey(key)) return -1;
        makeRecently(key);
        return map.get(key).val;
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            deleteKey(key);
            addRecently(key, value);
            return;
        }

        if(cap == cache.size()){
            removeLeastRecently();
        }

        addRecently(key, value);
    }
}