题目简介： 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例:
1 2 3 4 5 6 7 8 9 10 11 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
思路： LRU淘汰算法(Least Recently Used)上学期操作系统里学到过，也就是每次淘汰最久没有用到过的数据。
由于时间复杂度要求O(1)，所以为了查找快，我们使用哈希表 ；因为 cache 必须有顺序之分，以区分最近使用的和最久未使用的数据，且我们要在 cache 中查找键是否已存在，如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头，所以我们使用双向链表 。结合一下就成了哈希链表 ，就是像下图一样的结构：
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O (1) 的时间内完成 get 或者 put 操作。具体的方法如下：
对于 get 操作，首先判断 key 是否存在：
如果 key 不存在，则返回 -1
如果 key 存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部(该节点为最近使用的节点)，最后返回该节点的值。
对于 put 操作，首先判断 key 是否存在：
tip:
在双向链表的实现中，使用一个伪头部 （dummy head）和伪尾部 （dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
代码如下： 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 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 class LRUCache {public : struct DoubleLinkNode { int key, value; DoubleLinkNode* pre; DoubleLinkNode* next; DoubleLinkNode() : key(0 ), value(0 ), pre(NULL ), next(NULL ){} DoubleLinkNode(int _key, int _value) : key(_key), value(_value), pre(NULL ), next(NULL ){} }; unordered_map <int , DoubleLinkNode*> cache; DoubleLinkNode* head; DoubleLinkNode* tail; int size; int capacity; LRUCache(int _capacity) : capacity(_capacity), size(0 ){ head = new DoubleLinkNode(); tail = new DoubleLinkNode(); head -> next = tail; tail -> pre = head; } int get (int key) if (cache.count(key) == 0 ) return -1 ; DoubleLinkNode* node = cache[key]; moveToHead(node); return node -> value; } void put (int key, int value) if (cache.count(key) == 0 ){ DoubleLinkNode* newnode = new DoubleLinkNode(key, value); addToHead(newnode); cache[key] = newnode; size++; if (size > capacity){ DoubleLinkNode* node = removeTail(); cache.erase(node -> key); size--; } } else { DoubleLinkNode* node = cache[key]; node -> value = value; moveToHead(node); } } void addToHead (DoubleLinkNode* node) node -> pre = head; node -> next = head -> next; head -> next -> pre = node; head -> next = node; } void removeNode (DoubleLinkNode* node) node -> pre -> next = node -> next; node -> next -> pre = node -> pre; } void moveToHead (DoubleLinkNode* node) removeNode(node); addToHead(node); } DoubleLinkNode* removeTail () { DoubleLinkNode* node = tail -> pre; removeNode(node); return node; } };
