网站开发费用明细,网站开发需求分析内容,唐山哪个公司做网站,电子商务网站建设的目的题目描述#xff1a;请你设计并实现一个满足 LRU #xff08;最近最少使用#xff09; 缓存 约束的数据结构。 获得更多#xff1f;算法思路:代码文档#xff0c;算法解析的私得。 运行效果 完整代码 import java.util.HashMap;
import java.util.Map;/*** 2 * Author: L… 题目描述请你设计并实现一个满足 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 MapInteger,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对应的值输出ASystem.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);}
}
