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 中移除对应的键值对,以腾出空间。
维护双链表:
当有新节点插入到链表的头部时,需要更新头节点和新节点的 prevnext 指针。
当有节点从链表中删除时,需要更新该节点的前一个节点和后一个节点的 prevnext 指针。
通过这种方式,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为最大缓存容量。

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

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部