Leetcode.146 LRU 缓存

题目链接

Leetcode.146 LRU 缓存 mid

题目描述

请你设计并实现一个满足 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

提示：

• $1\le capacity\le 3000$
• $0\le key\le 10000$
• $0\le value\le 10^5$
• 最多调用 $2\ast 10^5$ 次 $get$ 和 $put$

解法：双向链表 + 哈希表

我们先设计出双向链表的节点 Node：

struct Node{
    Node* prev;
    Node* next;
    int key;
    int val;
    Node(int k,int v){
        key = k;
        val = v;
        prev = nullptr;
        next = nullptr;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12

我们开始设计链表的 API。

struct LinkedList{
    Node* head; //链表头节点(假)
    Node* tail; //链表尾节点(假)
    unordered_map<int,Node*> mp; //根据键值 key 获得对应的节点 node
    int size; //节点数量 , 初始为0
    int capacity; //链表容量,即链表最多能由几个节点，多了的节点就移除
};    
1
2
3
4
5
6
7

每次我们通过 $get$ 和 $put$ 操作节点之后，我们就要将其移动到链表头部，所以我们需要一个节点 node 插入到链表头部的函数 add：

void add(Node* node){
        head->next->prev = node;
        node->next = head->next;
        head->next = node;
        node->prev = head;
}
1
2
3
4
5
6

此外，我们需要从链表中删除指定节点 node：

void remove(Node* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
}
1
2
3
4

当链表中的节点数量 $size$ 超过链表容量 $capacity$ 时 ，即 $size>capacity$。我们就需要移除尾部的节点 并且 从$mp$ 删除对应的 $key$ 和 $node$ 的关系：

void remove(){
        Node* node = tail->prev; //要删除的是尾部的节点
        remove(node);
        int key = node->key;
        mp.erase(key);
        size--; //移除节点，链表节点数量 - 1
}
1
2
3
4
5
6
7

对于 $get$，如果不存在 $key$ 对应的节点，直接返回 $-1$；如果存在 ，返回对应节点 $node$ 的值，并且将 $node$ 提升到链表头部：

int get(int key){
        if(!mp.count(key)) return -1;
        Node* node = mp[key];
        int ans = node->val;
        //如果此时 node 已经是第一个节点了，就没必要移动了，直接返回node->val
        if(node == head->next) return ans;
        //将 node 移动到链表头部
        remove(node);
        add(node);
        return ans;
}
1
2
3
4
5
6
7
8
9
10
11

对于 $put$，如果存在 $key$ 对应的节点，我们更新节点值，然后将节点移动到头部即可；如果不存在，那我们直接插入新的节点 $Node(key,value)$，如果此时超出容量，还要移除尾部的节点：

void put(int key,int value){
        if(mp.count(key)){
            Node* node = mp[key];
            node->val = value;
            if(node == head->next) return;
            remove(node);
            add(node);
            return;
        }
        Node* node = new Node(key,value);
        mp[key] = node;
        add(node);
        size++;
        if(size > capacity) remove();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

时间复杂度：$O(1)$

完整代码：

struct Node{
    Node* prev;
    Node* next;
    int key;
    int val;
    Node(int k,int v){
        key = k;
        val = v;
        prev = nullptr;
        next = nullptr;
    }
};

struct LinkedList{
    Node* head;
    Node* tail;
    unordered_map<int,Node*> mp;
    int size;
    int capacity;

    LinkedList(int c){
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head->next = tail;
        tail->prev = head;
        size = 0;
        capacity = c;
    }

    void put(int key,int value){
        if(mp.count(key)){
            Node* node = mp[key];
            node->val = value;
            if(node == head->next) return;
            remove(node);
            add(node);
            return;
        }
        Node* node = new Node(key,value);
        mp[key] = node;
        add(node);
        size++;
        if(size > capacity) remove();
    }

    int get(int key){
        if(!mp.count(key)) return -1;
        Node* node = mp[key];
        int ans = node->val;
        if(node == head->next) return ans;
        remove(node);
        add(node);
        return ans;
    }

    void add(Node* node){
        head->next->prev = node;
        node->next = head->next;
        head->next = node;
        node->prev = head;
    }

    void remove(){
        Node* node = tail->prev;
        remove(node);
        int key = node->key;
        mp.erase(key);
        size--;
    }

    void remove(Node* node){
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
};

class LRUCache {
public:
    LinkedList* list;
    LRUCache(int capacity) {
        list = new LinkedList(capacity);
    }
    
    int get(int key) {
        return list->get(key);
    }
    
    void put(int key, int value) {
        list->put(key,value);
    }
};

/**
 * 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);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98