题目描述 运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。它应该支持以下操作: 获取数据 get
和 写入数据 put
。
获取数据 get(key)
- 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。 写入数据 put(key, value)
- 如果密钥已经存在,则变更其数据值;如果密钥不存在,则插入该组「密钥/数据值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
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
解题思路 通过哈希表和双向链表来实现。哈希表用于存储目前还在缓存中的数据,双向链表用于存储数据被访问的顺序。若某数据被访问,则将该数据对应的节点移动至链表头部,若超过了缓存容量,则将链表尾部的节点以及哈希表中的数据删除。
代码 OrderedDict
在 Python
语言中,有一种结合了哈希表与双向链表的数据结构 OrderedDict
,只需要短短的几行代码就可以完成本题。
Python 3.6
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class LRUCache : def __init__ (self, capacity: int) : self.capacity = capacity self.data = collections.OrderedDict() def get (self, key: int) -> int: if key not in self.data: return -1 self.data.move_to_end(key) return self.data[key] def put (self, key: int, value: int) -> None : if key in self.data: self.data.move_to_end(key) self.data[key] = value if len(self.data) > self.capacity: self.data.popitem(last=False )
执行用时:268 ms
内存消耗:22 MB
哈希表和双向链表自实现 Python 3.6
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 class LinkedNode () : def __init__ (self, key=0 , value=0 ) : self.key = key self.value = value self.prev = None self.next = None class LRUCache : def __init__ (self, capacity: int) : self.data = dict() self.head = LinkedNode() self.tail = LinkedNode() self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.size = 0 def get (self, key: int) -> int: if key not in self.data: return -1 node = self.data[key] self.moveToHead(node) return node.value def put (self, key: int, value: int) -> None : if key not in self.data: node = LinkedNode(key, value) self.data[key] = node self.addToHead(node) self.size += 1 if self.size > self.capacity: removed = self.removeEnd() self.data.pop(removed.key) self.size -= 1 else : node = self.data[key] node.value = value self.moveToHead(node) def addToHead (self, node) : node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def moveToHead (self, node) : self.removeNode(node) self.addToHead(node) def removeNode (self, node) : node.prev.next = node.next node.next.prev = node.prev def removeEnd (self) : removed = self.tail.prev self.removeNode(removed) return removed
执行用时:272 ms
内存消耗:22.5 MB
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 class LinkedNode { friend class LRUCache ; public : LinkedNode() = default ; LinkedNode(int k, int v) : key(k), value(v), prev(nullptr ), next(nullptr ) { } private : int key = 0 ; int value = 0 ; LinkedNode* prev = nullptr ; LinkedNode* next = nullptr ; }; class LRUCache {public : LRUCache(int _capacity) : capacity(_capacity), size(0 ) { head = new LinkedNode(); tail = new LinkedNode(); head->next = tail; tail->prev = head; } int get (int key) { if (data.count(key) == 0 ) { return -1 ; } else { LinkedNode* node = data[key]; moveToHead(node); return node->value; } } void put (int key, int value) { if (data.count(key) == 0 ) { LinkedNode* node = new LinkedNode(key, value); data[key] = node; addToHead(node); ++size; if (size > capacity) { LinkedNode* removed = removeEnd(); data.erase(removed->key); --size; } } else { LinkedNode* node = data[key]; node->value = value; moveToHead(node); } } void addToHead (LinkedNode* node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = node; } void moveToHead (LinkedNode* node) { removeNode(node); addToHead(node); } void removeNode (LinkedNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } LinkedNode* removeEnd () { LinkedNode* removed = tail->prev; removeNode(removed); return removed; } private : unordered_map <int , LinkedNode*> data; LinkedNode* head; LinkedNode* tail; int size = 0 ; int capacity; };
执行用时:196 ms
内存消耗:37.2 MB
参考
https://leetcode-cn.com/problems/lru-cache/solution/lruhuan-cun-ji-zhi-by-leetcode-solution/