最简单的网站设计乐清网站的建设

最简单的网站设计,乐清网站的建设,怎么开发手机网站,广告营销号码是干嘛的一、问题背景LRU#xff08;Least Recently Used#xff09;缓存是一种缓存淘汰策略#xff1a;当缓存容量满时#xff0c;删除最近最少使用的数据要求 get 和 put 操作的时间复杂度为 O(1)二、数据结构选择要实现 O(1) 操作#xff0c;需要两种数据结构配合#xff1a;H…一、问题背景LRULeast Recently Used缓存是一种缓存淘汰策略当缓存容量满时删除最近最少使用的数据要求 get 和 put 操作的时间复杂度为 O(1)二、数据结构选择要实现 O(1) 操作需要两种数据结构配合HashMap实现 O(1) 的查找MapInteger, Nodekey 到节点的映射2.双向链表实现 O(1) 的插入和删除维护访问顺序头部最近使用的节点尾部最近最少使用的节点三、核心设计虚拟头尾节点使用虚拟头尾节点简化边界处理head虚拟- Node1 - Node2 - Node3 - tail虚拟↑最近使用 ↑最近最少使用优势统一处理所有实际节点都有前驱和后继代码简洁不需要特殊判断边界情况减少错误避免空指针异常四、完整代码实现import java.util.*; class LRUCache { // 双向链表节点 class Node { int key; int value; Node prev; Node next; Node() {} Node(int key, int value) { this.key key; this.value value; } } private int capacity; private MapInteger, Node cache; private Node head; // 虚拟头节点 private Node tail; // 虚拟尾节点 public LRUCache(int capacity) { this.capacity capacity; this.cache new HashMap(); this.head new Node(); this.tail new Node(); head.next tail; tail.prev head; } public int get(int key) { Node node cache.get(key); if (node null) { return -1; } moveToHead(node); // 移到头部标记为最近使用 return node.value; } public void put(int key, int value) { Node node cache.get(key); if (node null) { // key不存在插入新节点 Node newNode new Node(key, value); if (cache.size() capacity) { // 容量已满删除最近最少使用的节点 Node lastNode removeTail(); cache.remove(lastNode.key); } addToHead(newNode); cache.put(key, newNode); } else { // key已存在更新值并移到头部 node.value value; moveToHead(node); } } // 将节点添加到头部 private void addToHead(Node node) { node.prev head; node.next head.next; head.next.prev node; head.next node; } // 移除节点 private void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; } // 将节点移到头部 private void moveToHead(Node node) { removeNode(node); addToHead(node); } // 移除尾部节点最近最少使用 private Node removeTail() { Node lastNode tail.prev; removeNode(lastNode); return lastNode; } }五、关键方法详解1. get(int key) - 获取值public int get(int key) { Node node cache.get(key); if (node null) { return -1; } moveToHead(node); // 关键移到头部标记为最近使用 return node.value; }流程从 HashMap 查找O(1)不存在返回 -1存在则移到头部标记为最近使用返回 value2. put(int key, int value) - 插入/更新public void put(int key, int value) { Node node cache.get(key); if (node null) { // 插入新节点 Node newNode new Node(key, value); if (cache.size() capacity) { Node lastNode removeTail(); cache.remove(lastNode.key); // 从HashMap中删除 } addToHead(newNode); cache.put(key, newNode); } else { // 更新已存在的节点 node.value value; moveToHead(node); } }两种情况key 不存在创建新节点容量满时删除尾部节点key 已存在更新 value 并移到头部3. addToHead(Node node) - 添加到头部private void addToHead(Node node){ node.prevhead; node.nexthead.next; head.next.prevnode; head.nextnode; }操作步骤原来head - node1 - tail插入 nodehead - node - node1 - tail1. node.prev head (node的前驱指向head)2. node.next head.next (node的后继指向原来的第一个节点)3. head.next.prev node (原来第一个节点的前驱指向node)4. head.next node (head的后继指向node)4. removeNode(Node node) - 移除节点private void removeNode(Node node){ node.prev.nextnode.next; node.next.prevnode.prev; }操作步骤原来prev - node - next 删除后prev - next 1. node.prev.next node.next (前驱的后继指向node的后继) 2. node.next.prev node.prev (后继的前驱指向node的前驱)六、执行流程示例假设 capacity 2执行以下操作1. put(1, 1)cache: {1 - Node(1,1)}链表: head - Node(1,1) - tail2. put(2, 2)cache: {1 - Node(1,1), 2 - Node(2,2)}链表: head - Node(2,2) - Node(1,1) - tail3. get(1)找到 Node(1,1)移到头部链表: head - Node(1,1) - Node(2,2) - tail返回: 14. put(3, 3)容量已满删除尾部 Node(2,2)插入新节点 Node(3,3) 到头部cache: {1 - Node(1,1), 3 - Node(3,3)}链表: head - Node(3,3) - Node(1,1) - tail七、总结LRU Cache 实现要点数据结构HashMap 双向链表虚拟节点简化边界处理访问顺序头部 最近使用尾部 最近最少使用时间复杂度所有操作 O(1)关键操作get/put 时都要将节点移到头部这是一个经典的数据结构组合应用在面试中经常出现。掌握这个实现对理解缓存机制和数据结构设计很有帮助。