题目描述请你设计并实现一个满足 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); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4解题思路这题我卡在了如何维护访问顺序的问题上了。看了题解才知道其实思路不难。方法一哈希表 双向链表为什么需要两个数据结构需求数据结构原因O(1) 查找 key哈希表unordered_map查找 O(1)O(1) 维护访问顺序双向链表插入、删除、移动节点都是 O(1)双向链表的角色头部最近使用的节点尾部最久未使用的节点每次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_mapint, 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; } } } };复杂度分析操作时间复杂度说明getO(1)哈希表查找 O(1) 链表移动 O(1)putO(1)哈希表插入 O(1) 链表操作 O(1)空间复杂度O(capacity)哈希表 链表最多存 capacity 个节点关键细节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找到前驱。方法二用listunordered_mapC STL 版代码实现:class LRUCache { private: int capacity; listpairint, int cacheList; // 存 (key, value) unordered_mapint, listpairint, 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的用法两种方法对比:方法getput代码复杂度推荐度手写双向链表 哈希表O(1)O(1)较高⭐⭐⭐⭐⭐STL list 哈希表O(1)O(1)中等⭐⭐⭐⭐总结要点说明核心思想哈希表 双向链表哈希表作用O(1) 查找 key双向链表作用O(1) 维护访问顺序头部最近使用尾部最久未使用超出容量删除尾部节点这道题是设计题的经典题也是面试高频题。核心是哈希表 双向链表的组合。
题目描述请你设计并实现一个满足 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); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4解题思路这题我卡在了如何维护访问顺序的问题上了。看了题解才知道其实思路不难。方法一哈希表 双向链表为什么需要两个数据结构需求数据结构原因O(1) 查找 key哈希表unordered_map查找 O(1)O(1) 维护访问顺序双向链表插入、删除、移动节点都是 O(1)双向链表的角色头部最近使用的节点尾部最久未使用的节点每次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_mapint, 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; } } } };复杂度分析操作时间复杂度说明getO(1)哈希表查找 O(1) 链表移动 O(1)putO(1)哈希表插入 O(1) 链表操作 O(1)空间复杂度O(capacity)哈希表 链表最多存 capacity 个节点关键细节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找到前驱。方法二用listunordered_mapC STL 版代码实现:class LRUCache { private: int capacity; listpairint, int cacheList; // 存 (key, value) unordered_mapint, listpairint, 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的用法两种方法对比:方法getput代码复杂度推荐度手写双向链表 哈希表O(1)O(1)较高⭐⭐⭐⭐⭐STL list 哈希表O(1)O(1)中等⭐⭐⭐⭐总结要点说明核心思想哈希表 双向链表哈希表作用O(1) 查找 key双向链表作用O(1) 维护访问顺序头部最近使用尾部最久未使用超出容量删除尾部节点这道题是设计题的经典题也是面试高频题。核心是哈希表 双向链表的组合。
、readline()、readlines()的区别与选型)
