题目描述 运用你所掌握的数据结构,设计和实现一个 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/