Leetcode Tencent 50 Task15 146. LRU Cache

Posted on In Views: Disqus:
DataWhale暑期学习小组-LeetCode刷题第八期Task15。

描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1)O(1) 时间复杂度内完成这两种操作？

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

来源：力扣（LeetCode）
链接：146. LRU Cache

解题思路

设计类的题目都略难，参考几位大神的题解，来整理下我的思路。

LRU

什么是LRU算法

LRU是一种缓存机制，也是一种缓存淘汰策略。

计算机的缓存容量有限，如果缓存满了就要删除一些内容，给新内容腾位置。这里有两个问题：

  • 删除哪些内容
  • 衡量内容是否删除的依据

而LRU缓存淘汰算法就是一种用来回答以上两个问题的常用策略，LRU全称Least Recently Used，我们把那些最近没有用过的数据删除，换言之，那些最近使用的数据是有价值的，应该被保留的。

LRU算法描述

LRU 算法实际上是让你设计数据结构：首先要接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。

根据题意，get和put方法都是O(1)O(1)的时间复杂度。下面一个算法工作的流程：

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
/* 初始化缓存，分配容量为 2 */
LRUCache cache = new LRUCache(2);
// 你可以把 cache 理解成一个队列
// 假设左边是队头，右边是队尾
// 最近使用的排在队头，久未使用的排在队尾
// 圆括号表示键值对 (key, val)

cache.put(1, 1);
// cache = [(1, 1)]
cache.put(2, 2);
// cache = [(2, 2), (1, 1)]
cache.get(1);       // 返回 1
// cache = [(1, 1), (2, 2)]
// 解释：因为最近访问了键 1，所以提前至队头
// 返回键 1 对应的值 1
cache.put(3, 3);
// cache = [(3, 3), (1, 1)]
// 解释：缓存容量已满，需要删除内容空出位置
// 优先删除久未使用的数据，也就是队尾的数据
// 然后把新的数据插入队头
cache.get(2);       // 返回 -1 (未找到)
// cache = [(3, 3), (1, 1)]
// 解释：cache 中不存在键为 2 的数据
cache.put(1, 4);    
// cache = [(1, 4), (3, 3)]
// 解释：键 1 已存在，把原始值 1 覆盖为 4
// 不要忘了也要将键值对提前到队头

数据结构及算法设计

  • 首先， 要求get和put都是O(1)O(1)的时间复杂度， 那么必须要用一个hashmap
  • 其次，光用hashmap无法知道那个元素是最没有被使用过的，通常想要知道某个元素使用的时间顺序，那需要有一个list， 然后每次使用(get/put)的时候把这个元素放到list的最前面
  • 另外，为了确保O(1)O(1)时间复杂度，需要用linkedlist
  • 最后，为了在删除linkedlist的中间元素时把前后元素都连起来，采用doublylinkedlist

具体哈希链表的数据结构如下：

代码

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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225

/**
 * Your LRUCache struct will be instantiated and called as such:
 * LRUCache* obj = lRUCacheCreate(capacity);
 * int param_1 = lRUCacheGet(obj, key);
 
 * lRUCachePut(obj, key, value);
 
 * lRUCacheFree(obj);
*/

//定义哈希函数求余被除数与哈希表容量的倍数关系
#define scale 2

//定义双链表
typedef struct node 
{
    int value; //节点值
    int key;   //节点hash值
    struct node *last;  //指向前向节点
    struct node *next;  //指向后续节点
    bool deleted;       //是否删除标记
} Node;

//用二级指针变量cache来保存链表节点从而实现哈希表
typedef struct
{
    Node **cache;  //保存链表节点
    Node *head;    //头节点
    Node *tail;    //未节点
    int capacity;  //哈希表容量
    int count;     //节点数目
} LRUCache;


//返回参数key对应hash值所在的节点，若cache变量当中无该key所对应的hash值，返回NULL
Node* cacheGet(LRUCache *obj, int key) 
{
    int m = obj->capacity * scale;
    for (int a = 0; a < m; a++) 
    {
        int hash = (key + a) % m;
        Node *nd = obj->cache[hash];
        if (nd != NULL) 
        {
            if (nd->key == key)
            {
                return nd;
            }
        }
        else
        {
            return NULL;
        }
    }
    return NULL;
}

//返回参数key对应的节点的hash，若cache变量当中无该key所对应的节点，返回NULL
int cacheIndex(LRUCache *obj, int key)
{
    int m = obj->capacity * scale;
    for (int a = 0; a < m; a++) 
    {
        int hash = (key + a) % m;
        Node *nd = obj->cache[hash];
        if (nd != NULL)
        {
            if (nd->key == key)
            {
                return hash;
            }
        }
        else
        {
            return hash;
        }
    }
    return -1;
}

//根据key，value健值对初始化一个节点
Node * newNode(int key, int value)
{
    Node *node = calloc(1, sizeof(Node));
    node->key = key;
    node->value = value;
    return node;
}

//将节点移动到哈希链表的末尾
void moveToTail(LRUCache *obj, Node *node) 
{
    if (obj->tail != NULL) 
    {
        Node *tail = obj->tail;
        if (node != tail)   //判断当前节点是不是在哈希链表的尾部节点
        {
            Node *last = node->last; //保存存入节点的之前一个节点指针
            if (last != NULL) 
            {
                last->next = node->next; //
            }
            Node *next = node->next;
            if (next != NULL) 
            {
                next->last = last;
                node->next = NULL;
            }
            tail->next = node;
            obj->tail = node;
            if (obj->head == node) 
            {
                obj->head = next;
            }
            node->last = tail;
        }
    }
    else
    {
        obj->tail = node;
    }
}

//哈希链表初始化
LRUCache* lRUCacheCreate(int capacity) 
{
    LRUCache *cache = calloc(1, sizeof(LRUCache));
    cache->cache = calloc(capacity * scale, sizeof(Node *));
    cache->capacity = capacity;
    return cache;
}

int lRUCacheGet(LRUCache* obj, int key) 
{
    Node *node = cacheGet(obj, key);
    if (node != NULL) 
    {
        if (node->deleted) 
        {
            return -1;
        }
        moveToTail(obj, node);
        return node->value;
    }
    return -1;
}

void lRUCachePut(LRUCache* obj, int key, int value) 
{
    int index = cacheIndex(obj, key);
    if (index >= 0) 
    {
        Node *node = obj->cache[index];
        if (node != NULL) 
        {
            if (node->deleted) 
            {
                node->deleted = false;
                Node *next = obj->head->next;
                if (next) 
                {
                    next->last = NULL;
                    obj->head->next = NULL;
                    obj->head->deleted = true;
                    obj->head = next;
                }
            }
            node->value = value;
            moveToTail(obj, node);
        }
        else
        {
            node = newNode(key, value);
            obj->count++;
            if (obj->count > obj->capacity) 
            {
                obj->head->deleted = true;
                Node *next = obj->head->next;
                if (next) 
                {
                    next->last = NULL;
                    obj->head->next = NULL;
                    obj->head = next;
                }
                
            }
            moveToTail(obj, node);
            obj->cache[index] = node;
            if (obj->head == NULL) 
            {
                obj->head = node;
            }
        }
    }
    else
    {
        Node *node = obj->head;
        Node *next = node->next;
        if (next != NULL) 
        {
            obj->head = next;
            next->last = NULL;
        }
        node->key = key;
        node->value = value;
        moveToTail(obj, node);
    }
}

void lRUCacheFree(LRUCache* obj) 
{
    int m = obj->capacity * scale;
    for (int a = 0; a < m; a++) 
    {
        Node *node = obj->cache[a];
        if (node != NULL) 
        {
            free(node);
        }
    }
    free(obj->cache);
    free(obj);
}