Voyz's Studio.

LeetCode算法笔记--LRU缓存机制

字数统计: 420阅读时长: 2 min
2021/01/14 Share

LeetCode算法笔记-Day61

146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
Example:

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);
lRUCache.put(2, 2);
lRUCache.get(1); // return 1
lRUCache.put(3, 3); // evicts key 2
lRUCache.get(2); // returns -1 (not found)
lRUCache.put(4, 4); // evicts key 1
lRUCache.get(1); // return -1 (not found)
lRUCache.get(3); // return 3
lRUCache.get(4); // return 4

方法一:双向链表

Answer:

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
class ListNode {
constructor(key, value) {
this.key = key
this.value = value
this.next = null
this.prev = null
}
}

class LRUCache {
constructor(capacity) {
this.capacity = capacity
this.hashTable = {}
this.count = 0
this.dummyHead = new ListNode()
this.dummyTail = new ListNode()
this.dummyHead.next = this.dummyTail
this.dummyTail.prev = this.dummyHead
}

get(key) {
let node = this.hashTable[key]
if (node == null) return -1
this.moveToHead(node)
return node.value
}

put(key, value) {
let node = this.hashTable[key]
if (node == null) {
let newNode = new ListNode(key, value)
this.hashTable[key] = newNode
this.addToHead(newNode)
this.count++
if (this.count > this.capacity) {
this.removeLRUItem()
}
} else {
node.value = value
this.moveToHead(node)
}
}

moveToHead(node) {
this.removeFromList(node)
this.addToHead(node)
}

removeFromList(node) {
let tempForPrev = node.prev
let tempForNext = node.next
tempForPrev.next = tempForNext
tempForNext.prev = tempForPrev
}

addToHead(node) {
node.prev = this.dummyHead
node.next = this.dummyHead.next
this.dummyHead.next.prev = node
this.dummyHead.next = node
}

removeLRUItem() {
let tail = this.popTail()
delete this.hashTable[tail.key]
this.count--
}

popTail() {
let tailItem = this.dummyTail.prev
this.removeFromList(tailItem)
return tailItem
}
}
  • 时间复杂度:O(1)
CATALOG
  1. 1. LeetCode算法笔记-Day61
    1. 1.1. 146. LRU Cache
    2. 1.2. 方法一:双向链表
      1. 1.2.1. Answer: