LeetCode刷题之HOT100之LRU缓存

2024/6/21 酷暑难耐，离开空调我将不知道能否《活着》，昨天跑步感觉全身的热无法排出去，出门那种热浪一阵一阵打过来，一点风都舍不得给我。早早的来到实验室，也没多早，九点哈哈，做题啦！

1、题目描述

2、逻辑分析

刚看到这个题目，我看了好久，看不懂啥意思，然后去看了题解以及代码，打算跳过这题的想法在脑海里飘过三四次，好长啊代码。但是我还是看完了，就是一个redis缓存思想。该算法使用了哈希表和双链表的数据结构。LRUCache 的大致思路是使用哈希表（如 HashMap）和双链表（Doubly Linked List）来实现一个最近最少使用（Least Recently Used, LRU）缓存机制。
具体思路如下：
数据结构：
使用 HashMap 来存储键值对（key-value pairs），其中 key 是缓存项的键，value 是对应的缓存值以及该值在双链表中的节点引用。
使用双链表来维护缓存项的访问顺序。最近访问的项位于链表的头部，而最久未访问的项位于链表的尾部。
初始化：
创建一个空的双链表，包含头节点（head）和尾节点（tail），它们互相指向对方，形成一个循环链表。
初始化 HashMap 用于存储键值对。
get(key) 操作：
在 HashMap 中查找键（key）对应的节点。
如果节点存在（即该键在缓存中），则将该节点从当前位置删除，并重新插入到链表的头部，以表示该键最近被访问过。
返回该节点的值。
如果节点不存在，则返回 -1 表示未找到。
put(key, value) 操作：
在 HashMap 中查找键（key）对应的节点。
如果节点存在（即该键已经在缓存中），则更新该节点的值为新的 value，并将该节点从当前位置删除，重新插入到链表的头部。
如果节点不存在（即该键不在缓存中），则需要创建一个新节点，将新节点插入到链表的头部，并在 HashMap 中添加键值对。
如果此时缓存已满（即缓存中元素的数量超过了设定的容量），则需要删除链表尾部的节点，并在 HashMap 中移除对应的键值对，以腾出空间。
维护双链表：
当有新节点插入到链表的头部时，需要更新头节点和新节点的 prev 和 next 指针。
当有节点从链表中删除时，需要更新该节点的前一个节点和后一个节点的 prev 和 next 指针。
通过这种方式，LRU 缓存能够快速地访问最近使用过的数据，并在必要时淘汰最久未使用的数据，从而保持缓存的有效性。

3、代码演示

public class LRUCache {
    // 双链表节点类
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
        // 构造无参数的DLinkedNode实例（通常用于初始化头尾节点）
        public DLinkedNode(){}
        // 构造带有key和value的DLinkedNode实例
        public DLinkedNode(int _key, int _value){key = _key; value = _value;}
    }

    // 使用HashMap存储key到DLinkedNode的映射
    private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
    // 当前缓存中元素的数量 
    private int size;
    // 缓存的最大容量
    private int capacity;
    // 双链表的头尾节点，用于维护最近最少使用（LRU）顺序
    private DLinkedNode head, tail;

    // 构造函数，初始化LRUCache
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 初始化头尾节点，它们之间互相指向，构成一个空链表
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head.next = tail;
        tail.prev = head;
    }
    
    // 根据key获取缓存值
    public int get(int key) {
        DLinkedNode node = cache.get(key);
        // 如果节点不存在，返回-1 
        if(node == null){
            return -1;
        }
        // 节点存在，将访问过的节点移动到头部
        moveToHead(node);
        // 返回节点的值
        return node.value;

    }
    
    // 将key-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);
            // 缓存元素数量加1
            size++;
            // 如果超过容量，删除尾部的节点
            if(size > capacity){
                DLinkedNode tail = removeTail();
                // 从HashMap中移除该节点 
                cache.remove(tail.key);
                // 缓存元素数量减1
                size--;
            }
            // 如果节点已存在，更新节点的值并移动到头部
        }else{
            node.value = value;
            moveToHead(node);
        }


    }

    // 将节点添加到双链表的头部
    private void addToHead(DLinkedNode node){
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }
    // 从双链表中移除一个节点
    private void removeNode(DLinkedNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    // 将一个节点从当前位置移动到双链表的头部
    private void moveToHead(DLinkedNode node){
        removeNode(node);
        addToHead(node);
    }
    
    // 移除并返回双链表的尾部节点
    private DLinkedNode removeTail(){
        DLinkedNode res = tail.prev;
        removeNode(res);
        return res;
    }
}

4、复杂度分析

• 时间复杂度：O(1)。get和put都只需要O(1)的时间。
• 空间复杂度：O(capacity)。capacity为最大缓存容量。

拜拜啦，我知道这题下次见到还是不能完整敲出来滴，那就希望下下次可以叭，再见！