LeetCode刷题之HOT100之LRU缓存

本文主要是介绍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;// 构造函数，初始化LRUCachepublic 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);// 缓存元素数量加1size++;// 如果超过容量，删除尾部的节点if(size > capacity){DLinkedNode tail = removeTail();// 从HashMap中移除该节点 cache.remove(tail.key);// 缓存元素数量减1size--;}// 如果节点已存在，更新节点的值并移动到头部}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为最大缓存容量。

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

这篇关于LeetCode刷题之HOT100之LRU缓存的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---