请你设计并实现一个满足 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)
的平均时间复杂度运行。
思路一:双向链表
c语言解法
struct LRUInfo{
int val;
int value;
struct LRUInfo* pre;
struct LRUInfo* next;
};
typedef struct {
int top;
int total;
struct LRUInfo * head;
struct LRUInfo * rear;
struct LRUInfo lruinfo[10001];
} LRUCache;
LRUCache* lRUCacheCreate(int capacity) {
LRUCache* obj = calloc(1, sizeof(LRUCache));
obj->total = capacity;
obj->head = calloc(1, sizeof(struct LRUInfo));
obj->rear = calloc(1, sizeof(struct LRUInfo));
obj->head->next = obj->rear;
obj->rear->pre = obj->head;
return obj;
}
int lRUCacheGet(LRUCache* obj, int key) {
if (obj->lruinfo[key].val == 1) {
obj->lruinfo[key].pre->next = obj->lruinfo[key].next;
obj->lruinfo[key].next->pre = obj->lruinfo[key].pre;
obj->rear->pre->next = obj->lruinfo + key;
obj->lruinfo[key].pre = obj->rear->pre;
obj->lruinfo[key].next = obj->rear;
obj->rear->pre = obj->lruinfo + key;
return obj->lruinfo[key].value;
}
return -1;
}
void lRUCachePut(LRUCache* obj, int key, int value) {
if (obj->lruinfo[key].val == 0 && obj->top < obj->total) {
(obj->top)++;
obj->rear->pre->next = obj->lruinfo + key;
obj->lruinfo[key].pre = obj->rear->pre;
obj->lruinfo[key].next = obj->rear;
obj->lruinfo[key].val = 1;
obj->lruinfo[key].value = value;
obj->rear->pre = obj->lruinfo + key;
} else if (obj->lruinfo[key].val == 1){
obj->lruinfo[key].pre->next = obj->lruinfo[key].next;
obj->lruinfo[key].next->pre = obj->lruinfo[key].pre;
obj->rear->pre->next = obj->lruinfo + key;
obj->lruinfo[key].pre = obj->rear->pre;
obj->lruinfo[key].next = obj->rear;
obj->lruinfo[key].value = value;
obj->rear->pre = obj->lruinfo + key;
} else if (obj->lruinfo[key].val == 0 && obj->top >= obj->total && obj->head->next != NULL) {
obj->lruinfo[key].val = 1;
obj->lruinfo[key].value = value;
obj->rear->pre->next = obj->lruinfo + key;
obj->lruinfo[key].pre = obj->rear->pre;
obj->lruinfo[key].next = obj->rear;
obj->rear->pre = obj->lruinfo + key;
obj->head->next->val = 0;
obj->head->next = obj->head->next->next;
obj->head->next->pre = obj->head;
}
return;
}
void lRUCacheFree(LRUCache* obj) {
free(obj);
}
/**
* 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);
*/
分析:
本题要实现LRU缓存实现双向链表的各个操作后即可解决,删除方法利用前驱节点的指针才能满足O(1)的时间复杂度,get方法利用前驱节点达到O(1)的时间复杂度文章来源:https://www.toymoban.com/news/detail-730682.html
总结:
本题考察对LRU缓存的实现,考虑到各个方法的实现的时间复杂度要求在O(1),所以采用双向链表保证时间复杂度,最后实现各个方法即可解决文章来源地址https://www.toymoban.com/news/detail-730682.html
到了这里,关于leetcode做题笔记146. LRU 缓存的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!