前言：

請你設計并實現一個滿足??LRU (最近最少使用) 緩存?約束的數據結構。

實現?LRUCache?類：

• LRUCache(int capacity)?以?正整數?作為容量?capacity?初始化 LRU 緩存
• int get(int key)?如果關鍵字?key?存在于緩存中，則返回關鍵字的值，否則返回?-1?。
• void put(int key, int value)?如果關鍵字?key?已經存在，則變更其數據值?value?；如果不存在，則向緩存中插入該組?key-value?。如果插入操作導致關鍵字數量超過?capacity?，則應該?逐出?最久未使用的關鍵字。
• 函數?get?和?put?必須以?O(1)?的平均時間復雜度運行。

關鍵設計說明

1. 雙向鏈表：維護訪問順序

   • 頭部節點 (head.next)：最近使用的數據

   • 尾部節點 (end.prev)：最久未使用的數據

   • 節點移動/刪除操作都是 O(1) 時間復雜度

2. 哈希表：提供 O(1) 的鍵值查找

   • Map<Integer, DLinkedNode>?映射鍵到鏈表節點

   • 快速判斷鍵是否存在并獲取對應節點

3. 哨兵節點：簡化邊界處理

   • 頭節點 (head) 和尾節點 (end) 作為虛擬節點

   • 避免空指針檢查，使代碼更簡潔

4. 操作流程：

   • get()：存在則移動節點到頭部

   • put()：

     • 存在 → 更新值并移到頭部

     • 不存在 → 創建新節點并添加到頭部

     • 容量超限 → 移除尾部節點

復雜度分析

• 時間復雜度：get()?和?put()?均為?O(1)

  • 哈希表操作：O(1) 的查找/插入/刪除

  • 鏈表操作：O(1) 的節點添加/刪除/移動

代碼實現：

import java.util.HashMap;
import java.util.Map;
class LRUCache {//雙向鏈表class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int key,int value){this.key = key;this.value = value;}}//LRU緩存的屬性//容量private int capacity = 0;//實際個數private int size = 0;//map裝的key，node節點private final Map<Integer,DLinkedNode> cache = new HashMap();//鏈表前后節點哨兵,方便操作頭尾。private final DLinkedNode head = new DLinkedNode();private final DLinkedNode end = new DLinkedNode();//初始化緩存public LRUCache(int capacity) {//不僅僅是賦值還要初始化鏈表//頭尾節點互相指向head.next = end;end.prev = head;this.capacity = capacity;}public int get(int key) {//得到nodeDLinkedNode node = cache.get(key);//判斷是否存在,存在就添加到鏈表頭部if(node==null){return -1;}moveToNode(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node!=null){//已經存在就重新賦值node.value = value;moveToNode(node);}else{//不存在就要新建一個節點，在放入mapDLinkedNode Newnode = new DLinkedNode(key,value);cache.put(key,Newnode);addToTop(Newnode);size++;}//判斷是否溢出if(size>capacity){//移除最后一個元素DLinkedNode endnode = end.prev;removeEndNode(endnode);}}//輔助方法//添加到鏈表頭部public void addToTop(DLinkedNode node){node.prev = head;head.next.prev = node;node.next = head.next;head.next = node;}//移動鏈表到頭部public void moveToNode(DLinkedNode node){removeNode(node);addToTop(node);}//移除nodepublic void removeNode(DLinkedNode node){node.next.prev = node.prev;node.prev.next = node.next;}//移除最后一個元素,還要清除hashpublic void removeEndNode(DLinkedNode node){removeNode(node);cache.remove(node.key);size--;}
}

總結

本人是一個菜鳥，沒怎么刷算法題，這算是我第一次刷算法題，不過基本的數據結構我還是會，這道題我是直接問的ai因為我完全沒有思路，覺得這個很難，然后看了ai的解法，和思路，感覺非常清晰，就去自己動手寫了一遍，一次過，很有成就感，后續也會繼續刷題。

如果我的文章成功幫助了你，請點贊加關注，你們的支持是我最大的動力。