题目

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。实现 LRUCache 类：

LRUCache(int capacity)：以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key)：如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value)：如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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

解答 & 代码

主要使用了两个数据结构：

双向链表：链表尾节点代表最晚被操作的节点，也就是最新被使用的；链表头节点则为最早被操作的节点，也就是最久未被使用的。链表越往右，节点越晚被使用（越新）
- 使用双向链表是为了可以方便的移动和删除节点，只要定位到该节点，就能得到其前后节点，就可以进行移动或删除，这是单向链表做不到的。使用双向链表使得能在 O(1) 时间复杂度内完成这些操作
- 链表节点中需要记录 key，是因为如代码 71 行所示，在删除最久未被使用的节点时，需要通过该节点查找哈希表并删除该数据
哈希表：存储
键值对
- 用于在 O(1) 时间复杂度内通过键 key 查询值 value
- 之所一存储的是 Node，是为了可以在 O(1) 时间复杂度定位到节点，将其移动到链表最末端（因为每次查询，就代表最新使用了这个数据） ```cpp struct Node { // 链表节点 int key; // 键 int val; // 值 Node pre; // 前一个节点 Node* next; // 后一个节点 Node(int key, int value) : key(key), val(value), pre(NULL), next(NULL) {} };

class LRUCache { private: unordered_map data; // 数据 int capacity; // 缓存容量 Node preHead; // 虚拟头节点，其下一个节点是头节点，是最早被操作即最久未被使用的 Node afterEnd; // 虚拟尾节点，其前一个节点是尾节点，是最晚被操作即最新被使用的 public: LRUCache(int capacity) { this->capacity = capacity; preHead = new Node(-1, -1); afterEnd = new Node(-1, -1); preHead->next = afterEnd; afterEnd->pre = preHead; }

int get(int key) {
    if(data.find(key) != data.end())
    {
        // 将 data[key] 这个节点移动到链表最后面，代表最后（新）被使用的
        // 先将 data[key] 节点原来的前后节点直接相连
        Node* pre = data[key]->pre;
        Node* next = data[key]->next;
        pre->next = next;
        next->pre = pre;
        // 再将 data[key] 节点插入到链表最后面
        pre = afterEnd->pre;
        pre->next = data[key];
        data[key]->pre = pre;
        data[key]->next = afterEnd;
        afterEnd->pre = data[key];

        return data[key]->val;
    }
    else
        return -1;    
}

void put(int key, int value) {
    if(data.find(key) != data.end())
    {
        // 将 data[key] 这个节点移动到链表最后面，代表最后（新）被使用的
        // 先将 data[key] 节点原来的前后节点直接相连
        Node* pre = data[key]->pre;
        Node* next = data[key]->next;
        pre->next = next;
        next->pre = pre;
        // 再将 data[key] 节点插入到链表最后面
        pre = afterEnd->pre;
        pre->next = data[key];
        data[key]->pre = pre;
        data[key]->next = afterEnd;
        afterEnd->pre = data[key];

        // 修改 data[key] 节点的值
        data[key]->val = value;
    }
    else
    {
        // 如果缓存满了，删除最早被使用的，也就是链表最前面的节点
        if(data.size() >= capacity)
        {
            Node* elaryNode = preHead->next;
            data.erase(elaryNode->key);            // 将该节点的键值对从哈希表中删除
            preHead->next = elaryNode->next;
            elaryNode->next->pre = preHead;
            delete elaryNode;                    // 删除该节点
        }
        // 将新节点插入链表最后面
        Node* node = new Node(key, value);
        Node* pre = afterEnd->pre;
        pre->next = node;
        node->pre = pre;
        node->next = afterEnd;
        afterEnd->pre = node;

        // 插入哈希表
        data.insert(make_pair(key, node));
    }
}

};

/**

Your LRUCache object will be instantiated and called as such:
LRUCache* obj = new LRUCache(capacity);
int param_1 = obj->get(key);
obj->put(key,value); */
```
执行结果：
```
执行结果：通过

执行用时：556 ms, 在所有 C++ 提交中击败了 5.02% 的用户内存消耗：161.1 MB, 在所有 C++ 提交中击败了 5.03% 的用户


二刷，相同思路，改了下代码写法
```cpp
struct Node {
    int key;
    int value;
    Node* pre;
    Node* next;

    Node(int key, int val): key(key), value(val), pre(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    int capacity;
    Node* dummyHead;
    Node* dummyEnd;
    unordered_map<int, Node*> cacheMap;

    // 将 node 节点移到链表最前面（代表最新被使用）
    void moveNodeToFront(Node* node)
    {
        node->pre->next = node->next;
        node->next->pre = node->pre;

        node->next = dummyHead->next;
        dummyHead->next->pre = node;
        dummyHead->next = node;
        node->pre = dummyHead;
    }

    // 删除链表最后的节点（除虚拟节点外），即最早被使用的节点
    // 同时从哈希表中删除相应的键值对
    void deleteEndNode()
    {
        Node* node = dummyEnd->pre;
        cacheMap.erase(node->key);
        node->pre->next = dummyEnd;
        dummyEnd->pre = node->pre;
        delete node;
    }

    // 将新节点 node 插入到链表最前面
    // 同时在哈希表中插入键值对
    void insertNodeToFront(Node* node)
    {
        node->next = dummyHead->next;
        dummyHead->next->pre = node;
        dummyHead->next = node;
        node->pre = dummyHead;
        cacheMap[node->key] = node;
    }
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        dummyHead = new Node(-1, -1);
        dummyEnd = new Node(-1, -1);
        dummyHead->next = dummyEnd;
        dummyEnd->pre = dummyHead;
    }

    int get(int key) {
        if(cacheMap.find(key) == cacheMap.end())
            return -1;
        else
        {
            Node* node = cacheMap[key];
            moveNodeToFront(node);
            return node->value;
        }
    }

    void put(int key, int value) {
        if(cacheMap.find(key) != cacheMap.end())
        {
            Node* node = cacheMap[key];
            node->value = value;
            moveNodeToFront(node);
        }
        else
        {
            if(cacheMap.size() == capacity)
                deleteEndNode();
            Node* node = new Node(key, value);
            insertNodeToFront(node);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

CodeTop 企业题库

[中等] 146. LRU 缓存机制

题目

解答 & 代码