题目描述 请你设计并实现一个满足 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)
的平均时间复杂度运行。
输入输出 1 2 3 4 5 输入 ["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]
代码 c++版 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 struct DLinkedNode { int key, value; DLinkedNode* prev; DLinkedNode* next; DLinkedNode (): key (0 ), value (0 ), prev (nullptr ), next (nullptr ){}; DLinkedNode (int k, int v): key (k), value (v), prev (nullptr ), next (nullptr ){}; }; class LRUCache {private : unordered_map<int , DLinkedNode*> mp; DLinkedNode *head, *tail; int size, capacity; public : LRUCache (int capacity) { size = 0 ; this ->capacity = capacity; head = new DLinkedNode (); tail = new DLinkedNode (); head->next = tail; tail->prev = head; } int get (int key) { if (mp.count (key) == 0 ) return -1 ; DLinkedNode *node = mp[key]; moveToHead (node); return node->value; } void put (int key, int value) { if (mp.count (key) == 1 ) { mp[key]->value = value; moveToHead (mp[key]); }else { DLinkedNode *node = new DLinkedNode (key, value); mp[key] = node; addHead (node); size ++; if (size > capacity) { size--; moveTail (); } } } void moveToHead (DLinkedNode *node) { moveNode (node); addHead (node); } void moveNode (DLinkedNode *node) { node->prev->next = node->next; node->next->prev = node->prev; } void addHead (DLinkedNode *node) { node->next = head->next; node->next->prev = node; node->prev = head; head->next = node; } void moveTail () { DLinkedNode *node = tail->prev; mp.erase (node->key); moveNode (node); delete node; } };
go语言版 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 type DLinkedNode struct { key, value int prev, next *DLinkedNode } type LRUCache struct { size, capacity int head, tail *DLinkedNode mp map [int ]*DLinkedNode } func initDL (key int , value int ) *DLinkedNode{ return &DLinkedNode{ key: key, value: value, } } func Constructor (capacity int ) LRUCache { l := LRUCache{ size: 0 , capacity: capacity, head: initDL(0 , 0 ), tail: initDL(0 , 0 ), mp: map [int ]*DLinkedNode{}, } l.head.next = l.tail l.tail.prev = l.head return l } func (this *LRUCache) Get(key int ) int { if _, k := this.mp[key]; !k{ return -1 } node := this.mp[key] this.moveToHead(node) return node.value } func (this *LRUCache) Put(key int , value int ) { if _, k := this.mp[key]; k { node := this.mp[key] node.value = value this.moveToHead(node) }else { node := initDL(key, value) this.mp[key] = node this.addHead(node) this.size++ if this.size > this.capacity { this.moveTail() this.size-- } } } func (this *LRUCache) moveToHead(node *DLinkedNode){ this.moveNode(node); this.addHead(node); } func (this *LRUCache) moveNode(node *DLinkedNode){ node.prev.next = node.next; node.next.prev = node.prev; } func (this *LRUCache) addHead(node *DLinkedNode){ node.next = this.head.next; node.next.prev = node; node.prev = this.head; this.head.next = node; } func (this *LRUCache) moveTail(){ node := this.tail.prev; delete (this.mp, node.key) this.moveNode(node); }