企业官网建设流程全解析

题目描述：

请你设计并实现一个满足 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)的平均时间复杂度运行。

示例：

输入["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]输出[null, null, null, 1, null, -1, null, -1, 3, 4]解释LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {1=1} lRUCache.put(2, 2); // 缓存是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4

解题思路：

这题我卡在了如何维护访问顺序的问题上了。看了题解才知道其实思路不难。

方法一：哈希表 + 双向链表

为什么需要两个数据结构？

双向链表的角色：

• 头部：最近使用的节点

• 尾部：最久未使用的节点

• 每次get或put，把节点移到头部

• 超出容量时，删除尾部节点

具体过程示例：

哈希表: {1: node1, 2: node2, 3: node3} 双向链表: head <-> 3 <-> 1 <-> 2 <-> tail ↑ 最近使用 最久未使用 get(1) 后: head <-> 1 <-> 3 <-> 2 <-> tail put(4) 后: 容量超出，删除 tail 前一个（2） head <-> 4 <-> 1 <-> 3 <-> tail

代码实现：

class LRUCache { private: struct Node { int key, value; Node *prev, *next; Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {} }; int capacity; unordered_map<int, Node*> cache; // key → 节点指针 Node *head, *tail; // 虚拟头尾节点 // 把节点移到头部（最近使用） void moveToHead(Node* node) { removeNode(node); addToHead(node); } // 从链表中删除节点 void removeNode(Node* node) { node->prev->next = node->next; node->next->prev = node->prev; } // 把节点加到头部 void addToHead(Node* node) { node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; } // 删除尾部节点（最久未使用） Node* removeTail() { Node* node = tail->prev; removeNode(node); return node; } public: LRUCache(int capacity) : capacity(capacity) { head = new Node(0, 0); // 虚拟头结点 tail = new Node(0, 0); // 虚拟尾节点 head->next = tail; tail->prev = head; } int get(int key) { if (cache.find(key) == cache.end()) { return -1; } Node* node = cache[key]; moveToHead(node); // 移到头部，表示最近使用 return node->value; } void put(int key, int value) { if (cache.find(key) != cache.end()) { // key 已存在，更新值并移到头部 Node* node = cache[key]; node->value = value; moveToHead(node); } else { // key 不存在，新建节点 Node* node = new Node(key, value); cache[key] = node; addToHead(node); // 超出容量，删除尾部 if (cache.size() > capacity) { Node* removed = removeTail(); cache.erase(removed->key); delete removed; } } } };

复杂度分析：

关键细节：

1. 为什么用虚拟头尾节点？

head = new Node(0, 0); tail = new Node(0, 0); head->next = tail; tail->prev = head;

• 避免处理"链表为空"、"插入第一个节点"等边界情况

• 所有节点的插入删除逻辑统一

2.get和put都要调用moveToHead

因为get也算"使用"，被get的节点应该变成最近使用的。

3. 超出容量时删除尾部

Node* removed = removeTail(); cache.erase(removed->key); delete removed;

注意：先从哈希表中删除，再释放节点内存。

4. 为什么用双向链表而不是单向链表？

因为需要 O(1) 删除任意节点。单向链表删除节点需要知道前驱，双向链表可以直接通过node->prev找到前驱。

方法二：用list+unordered_map（C++ STL 版）

代码实现:

class LRUCache { private: int capacity; list<pair<int, int>> cacheList; // 存 (key, value) unordered_map<int, list<pair<int, int>>::iterator> cacheMap; public: LRUCache(int capacity) : capacity(capacity) {} int get(int key) { if (cacheMap.find(key) == cacheMap.end()) return -1; // 移到头部 cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]); return cacheMap[key]->second; } void put(int key, int value) { if (cacheMap.find(key) != cacheMap.end()) { // 更新值并移到头部 cacheMap[key]->second = value; cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]); } else { // 插入新节点 cacheList.push_front({key, value}); cacheMap[key] = cacheList.begin(); // 超出容量 if (cacheList.size() > capacity) { cacheMap.erase(cacheList.back().first); cacheList.pop_back(); } } } };

优点：用 STL 的list和splice，代码更简洁
缺点：需要理解splice的用法

两种方法对比:

总结：

这道题是设计题的经典题，也是面试高频题。核心是哈希表 + 双向链表的组合。