做静态头像网站,上海装修网官网,wordpress 备份到云盘,王也天演过的电视剧请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否则返回 -…请你设计并实现一个满足 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)的时间复杂度
总结
本题考察对LRU缓存的实现考虑到各个方法的实现的时间复杂度要求在O(1)所以采用双向链表保证时间复杂度最后实现各个方法即可解决
