Java算法_ LRU 缓存(LeetCode_Hot100)

题目描述：请你设计并实现一个满足 LRU （最近最少使用） 缓存 约束的数据结构。

获得更多？算法思路:代码文档，算法解析的私得。

运行效果

完整代码

import java.util.HashMap;
import java.util.Map;/*** 2 * @Author: LJJ* 3 * @Date: 2023/8/7 13:14* 4*/
public class LRUCache {class Node{int key;String value;Node prev;Node next;public Node(int key , String value){this.key = key;this.value = value;}}private int capacity;private Map<Integer,Node> cache;private Node head;private Node tail;// 初始化LRUCache类的构造函数,// 使用了一个哨兵节点的技巧，将head和tail初始化为哨兵节点，并不存储具体的键值对。// 哨兵节点可以简化链表的操作，避免处理头部和尾部节点时需要特殊处理的情况。public LRUCache(int capacity){this.capacity = capacity;cache = new HashMap<>();//初始化头尾节点；head = new Node(-1, "-1");tail = new Node(-1, "-1");head.next = tail;tail.prev = head;}public String get(int key){if (cache.containsKey(key)){Node node = cache.get(key);//将查到的节点移动到链表头部removeNode(node);addToHead(node);return node.value;}return "-1";}public void put(int key, String value){if (cache.containsKey(key)){Node node = cache.get(key);node.value = value;//将更新后的节点移动到链表头部removeNode(node);addToHead(node);}else {if (cache.size() >= capacity){//如果缓存已满，需要移除最久未使用的节点（即链表尾部节点）cache.remove(tail.prev.key);removeNode(tail.prev);}Node newNode = new Node(key,value);cache.put(key,newNode);//将新的节点插入链表头部addToHead(newNode);}}// 将节点插入链表头部private void addToHead(Node node){node.next = head.next;head.next.prev = node;head.next = node;node.prev = head;}//移除节点private void removeNode(Node node){node.prev.next = node.next;node.next.prev = node.prev;}private static void printCache(Node head){Node current = head;while (current != null){System.out.print("(" + current.key + ", " + current.value + ") -> ");current = current.next;}System.out.println("null");}public static void main(String[] args) {LRUCache lruCache = new LRUCache(3);// 插入键值对 (1, "A")lruCache.put(1, "A");// 插入键值对 (2, "B")lruCache.put(2, "B");// 插入键值对 (3, "C")lruCache.put(3, "C");// 此时缓存状态为：3 -> 2 -> 1，其中1是最近访问的，3是最久未使用的System.out.println("初始缓存状态为：");printCache(lruCache.head);// 获取键1对应的值，输出"A"System.out.println(" // 获取键1对应的值:"+lruCache.get(1));// 此时缓存状态不变：1 -> 3 -> 2System.out.println("获取键1对应的值，输出\"A\"后的缓存状态为：");printCache(lruCache.head);// 插入键值对 (4, "D")，此时缓存已满，需要逐出最久未使用的键值对，即键2 -> 值B被逐出lruCache.put(4, "D");// 此时缓存状态为：4 -> 1 -> 3，其中3是最久未使用的，4是最近访问的System.out.println("插入键值对 (4, \"D\")，此时缓存已满，需要逐出最久未使用的键值对，即键2 -> 值B被逐出的缓存状态为：");printCache(lruCache.head);// 获取键2对应的值，由于键2已经被逐出，输出-1System.out.println("获取键2对应的值:"+lruCache.get(2));// 此时缓存状态不变：4 -> 1 -> 3System.out.println("获取键2对应的值，由于键2已经被逐出，输出-1的缓存状态为：");printCache(lruCache.head);// 插入键值对 (5, "E")，此时缓存已满，需要逐出最久未使用的键值对，即键3 -> 值C被逐出lruCache.put(5, "E");// 此时缓存状态为：5 -> 4 -> 1，其中1是最久未使用的，5是最近访问的System.out.println("插入键值对 (5, \"E\")，此时缓存已满，需要逐出最久未使用的键值对，即键3 -> 值C被逐出的缓存状态为：");printCache(lruCache.head);// 获取键3对应的值，由于键3已经被逐出，输出-1System.out.println("获取键3对应的值:"+lruCache.get(3));// 此时缓存状态不变：5 -> 4 -> 1System.out.println(" // 获取键3对应的值，由于键3已经被逐出，输出-1的缓存状态为：");printCache(lruCache.head);}
}