[LeetCode] 146. LRU Cache

Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.

Implement the LRUCache class:

LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.

The functions get and put must each run in O(1) average time complexity.

Example 1:

Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]

Explanation
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // cache is {1=1}
lRUCache.put(2, 2); // cache is {1=1, 2=2}
lRUCache.get(1);    // return 1
lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
lRUCache.get(2);    // returns -1 (not found)
lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
lRUCache.get(1);    // return -1 (not found)
lRUCache.get(3);    // return 3
lRUCache.get(4);    // return 4

Constraints:

1 <= capacity <= 3000
0 <= key <= 104
0 <= value <= 105
At most 2 * 105 calls will be made to get and put.

LRU缓存器。

请你设计并实现一个满足 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) 的平均时间复杂度运行。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

实现这个缓存器，时间复杂度要求是O(1)。LRU缓存器是在一定的容量范围内存了一些node，按照上一次被访问的时间由新到旧排列，越近被访问的node应该排得越靠前。一个很容易理解的例子就是手机的后台，类似这样，最近使用的APP最靠前，内存不足的时候，会释放上一次使用时间最远的APP。

思路是双向链表（DLL） + hashmap。因为题意要求了时间复杂度必须是O(1)所以只有 hashmap 和链表才能满足这个时间复杂度。至于为什么是DLL而不是单链表，则是为了node之间的移动方便，也是为了添加删除节点的时候能更加高效。这里解释一下两个函数的实现细节。

get函数，就是在hashmap里面寻找目标。如果有则先删除这个目标，再加进去，再返回，没有则返回-1；同时DLL里面，如果没有这个目标则什么都不做，如果有这个目标则需要把这个node移动到头节点。

put函数，如果node之前存在过，则hashmap没有动作，DLL里面需要把这个node放到头节点；如果node不存在，需要看一下此时此刻node的数量是否超过cache的容量capacity，如果没超过就直接把node放到DLL的头节点，放入hashmap并size++，如果超过了capacity，要先去掉DLL的tail节点，再加入当前节点。

时间O(1) - required

空间O(n) - hashmap + DLL

Java实现

 1 class LRUCache {
 2     class Node {
 3         int key;
 4         int value;
 5         Node prev;
 6         Node next;
 7     }
 8 
 9     private void addNode(Node node) {
10         // always add the node after the head
11         node.prev = head;
12         node.next = head.next;
13         head.next.prev = node;
14         head.next = node;
15     }
16 
17     private void removeNode(Node node) {
18         Node prev = node.prev;
19         Node next = node.next;
20         prev.next = next;
21         next.prev = prev;
22     }
23 
24     private void moveToHead(Node node) {
25         removeNode(node);
26         addNode(node);
27     }
28 
29     private Node popTail() {
30         Node res = tail.prev;
31         removeNode(res);
32         return res;
33     }
34 
35     private HashMap<Integer, Node> cache = new HashMap<>();
36     private int size;
37     private int capacity;
38     private Node head, tail;
39 
40     public LRUCache(int capacity) {
41         this.size = 0;
42         this.capacity = capacity;
43         head = new Node();
44         tail = new Node();
45         head.next = tail;
46         tail.prev = head;
47     }
48 
49     public int get(int key) {
50         Node node = cache.get(key);
51         if (node == null) {
52             return -1;
53         }
54         moveToHead(node);
55         return node.value;
56     }
57 
58     public void put(int key, int value) {
59         Node node = cache.get(key);
60         if (node == null) {
61             Node newNode = new Node();
62             newNode.key = key;
63             newNode.value = value;
64             cache.put(key, newNode);
65             addNode(newNode);
66             size++;
67             if (size > capacity) {
68                 Node tail = popTail();
69                 cache.remove(tail.key);
70                 size--;
71             }
72         } else {
73             node.value = value;
74             moveToHead(node);
75         }
76     }
77 }
78 
79 /**
80  * Your LRUCache object will be instantiated and called as such:
81  * LRUCache obj = new LRUCache(capacity);
82  * int param_1 = obj.get(key);
83  * obj.put(key,value);
84  */

View Code

JavaScript实现

ES6里面的hashmap有一个特性，是加入hashmap里面的object是有序的，所以如果用ES6写这道题的话是不需要DLL的。用map.prototype.keys()得到一个迭代器（iterator），然后用.next().value获取到map里面最老的一个节点然后将其删除。我这里给出两种实现，第一种不需要DLL，第二种需要。

 1 /**
 2  * @param {number} capacity
 3  */
 4 var LRUCache = function (capacity) {
 5     this.capacity = capacity;
 6     this.cache = new Map();
 7 };
 8 
 9 /** 
10  * @param {number} key
11  * @return {number}
12  */
13 LRUCache.prototype.get = function (key) {
14     if (this.cache.has(key)) {
15         var val = this.cache.get(key);
16         this.cache.delete(key);
17         this.cache.set(key, val);
18         return val;
19     } else {
20         return -1;
21     }
22 };
23 
24 /** 
25  * @param {number} key 
26  * @param {number} value
27  * @return {void}
28  */
29 LRUCache.prototype.put = function (key, value) {
30     if (this.cache.size < this.capacity && !this.cache.has(key)) {
31         this.cache.set(key, value);
32     } else if (this.cache.has(key)) {
33         this.cache.delete(key);
34         this.cache.set(key, value);
35     } else if (this.cache.size === this.capacity) {
36         // Map.prototype.keys() 返回一个迭代对象，而不是数组
37         // 迭代对象 Iterator.next() 是迭代对象的第一个对象，而不是值，需要 .value获取值
38         this.cache.delete(this.cache.keys().next().value);
39         this.cache.set(key, value);
40     }
41 };
42 
43 /**
44  * Your LRUCache object will be instantiated and called as such:
45  * var obj = new LRUCache(capacity)
46  * var param_1 = obj.get(key)
47  * obj.put(key,value)
48  */

View Code

  1 /**
  2  * @param {number} capacity
  3  */
  4 const LRUCache = function (capacity) {
  5     this.size = 0;
  6     this.capacity = capacity;
  7     this.LL = new DoublyLinkedList();
  8     this.cache = {};
  9 };
 10 
 11 LRUCache.prototype.get = function (key) {
 12     const getNode = this.cache[key];
 13     if (getNode) {
 14         this.LL.moveToHead(getNode);
 15     } else {
 16         return -1;
 17     }
 18     return getNode.val;
 19 };
 20 
 21 LRUCache.prototype.put = function (key, value) {
 22     // overwrite the value if it exists
 23     if (this.cache[key]) {
 24         this.cache[key].val = value;
 25         this.LL.moveToHead(this.cache[key]);
 26         return;
 27     }
 28 
 29     // otherwise create new node
 30     const node = new Node(key, value);
 31 
 32     // only evict if max capacity has been reached
 33     if (this.size < this.capacity) {
 34         this.size++;
 35     } else {
 36         const keyToRemove = this.LL.removeTail();
 37         delete this.cache[keyToRemove];
 38     }
 39 
 40     // set to most recently used
 41     this.LL.insertHead(node);
 42     this.cache[key] = node;
 43 };
 44 
 45 class Node {
 46     constructor(key, val) {
 47         this.key = key;
 48         this.val = val;
 49         this.next = null;
 50         this.prev = null;
 51     }
 52 }
 53 
 54 class DoublyLinkedList {
 55     constructor() {
 56         this.head = null;
 57         this.tail = null;
 58     }
 59 
 60     removeTail() {
 61         const evict = this.tail;
 62         if (evict.prev !== null && this.tail != this.head) {
 63             evict.prev.next = null;
 64             this.tail = evict.prev;
 65         } else {
 66             this.tail = null;
 67             this.head = null;
 68         }
 69         return evict.key;
 70     }
 71 
 72     insertHead(node) {
 73         if (this.head !== null) {
 74             node.next = this.head;
 75             this.head.prev = node;
 76             this.head = node;
 77         } else {
 78             this.head = node;
 79             this.tail = node;
 80         }
 81     }
 82 
 83     moveToHead(node) {
 84         if (node === this.head) return;
 85         if (node === this.tail) {
 86             node.next = this.head;
 87             this.head.prev = node;
 88             this.tail = node.prev;
 89             node.prev.next = null;
 90             node.prev = null;
 91         } else {
 92             node.prev.next = node.next;
 93             node.next.prev = node.prev;
 94             node.next = this.head;
 95             node.next.prev = node;
 96             node.prev = null
 97         }
 98         this.head = node;
 99     }
100 }
101 
102 /**
103  * Your LRUCache object will be instantiated and called as such:
104  * var obj = new LRUCache(capacity)
105  * var param_1 = obj.get(key)
106  * obj.put(key,value)
107  */

View Code

[LeetCode] 146. LRU Cache

推荐阅读