0146. LRU 缓存机制
题目地址(146. LRU 缓存机制)
https://leetcode-cn.com/problems/lru-cache/
题目描述
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现
LRUCache 类：LRUCache(int capacity)以正整数作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在
O(1) 时间复杂度内完成这两种操作？示例：
1
输入
2
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
3
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
4
输出
5
[null, null, null, 1, null, -1, null, -1, 3, 4]
6
7
解释
8
LRUCache lRUCache = new LRUCache(2);
9
lRUCache.put(1, 1); // 缓存是 {1=1}
10
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
11
lRUCache.get(1); // 返回 1
12
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
13
lRUCache.get(2); // 返回 -1 (未找到)
14
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
15
lRUCache.get(1); // 返回 -1 (未找到)
16
lRUCache.get(3); // 返回 3
17
lRUCache.get(4); // 返回 4
Copied!
思路
- 1.确定需要使用的数据结构
- 1.根据题目要求,存储的数据需要保证顺序关系(逻辑层面) ===> 使用数组,链表等保证顺序关系
- 2.同时需要对数据进行频繁的增删, 时间复杂度 O(1) ==> 使用链表等
- 3.对数据进行读取时, 时间复杂度 O(1) ===> 使用哈希表 最终采取双向链表 + 哈希表
- 1.双向链表按最后一次访问的时间的顺序进行排列, 链表头部为最近访问的节点
- 2.哈希表,以关键字为键,以链表节点的地址为值
- 2.put 操作 通过哈希表, 查看传入的关键字对应的链表节点, 是否存在
- 1.如果存在,
- 1.将该链表节点的值更新
- 2.将该该链表节点调整至链表头部
- 2.如果不存在
- 1.如果链表容量未满,
- 1.新生成节点,
- 2.将该节点位置调整至链表头部
- 2.如果链表容量已满
- 1.删除尾部节点
- 2.新生成节点
- 3.将该节点位置调整至链表头部
- 3.将新生成的节点，按关键字为键，节点地址为值插入哈希表
- 3.get 操作 通过哈希表, 查看传入的关键字对应的链表节点, 是否存在
- 1.节点存在
- 1.将该节点位置调整至链表头部
- 2.返回该节点的值
- 2.节点不存在, 返回 null
伪代码如下：
1
var LRUCache = function(capacity) {
2
保存一个该数据结构的最大容量
3
生成一个双向链表,同时保存该链表的头结点与尾节点
4
生成一个哈希表
5
};
6
7
function get (key) {
8
if 哈希表中存在该关键字 {
9
根据哈希表获取该链表节点
10
将该节点放置于链表头部
11
return 链表节点的值
12
} else {
13
return -1
14
}
15
};
16
17
function put (key, value) {
18
if 哈希表中存在该关键字 {
19
根据哈希表获取该链表节点
20
将该链表节点的值更新
21
将该节点放置于链表头部
22
} else {
23
if 容量已满 {
24
删除链表尾部的节点
25
新生成一个节点
26
将该节点放置于链表头部
27
} else {
28
新生成一个节点
29
将该节点放置于链表头部
30
}
31
}
32
};
Copied!
代码
语言支持: JS, Go, PHP, Python3
JS Code:
1
class ListNode{
2
constructor(key, val){
3
this.key = key;
4
this.val = val;
5
this.pre = null;
6
this.next = null;
7
}
8
};
9
10
class LRUCache{
11
constructor(capacity){
12
this.capacity = capacity;
13
this.size = 0;
14
this.data = {};
15
this.head = new ListNode();
16
this.tail = new ListNode();
17
this.head.next = this.tail;
18
this.tail.pre = this.head;
19
}
20
21
get(key){
22
if(!this.data[key]) return -1;
23
else{
24
let node = this.data[key];
25
this.removeNode(node);
26
this.appendHead(node);
27
28
return node.val;
29
}
30
}
31
32
put(key, value){
33
if(!this.data[key]){
34
let node = new ListNode(key, value);
35
36
this.data[key] = node;
37
this.appendHead(node);
38
this.size++;
39
40
if(this.size > this.capacity){
41
const lastKey = this.removeTail();
42
delete this.data[lastKey];
43
this.size--;
44
}
45
46
}else{
47
let node = this.data[key];
48
this.removeNode(node);
49
node.val = value;
50
this.appendHead(node);
51
}
52
}
53
54
removeNode(node){
55
let preNode = node.pre;
56
let nextNode = node.next;
57
58
preNode.next = nextNode;
59
nextNode.pre = preNode;
60
}
61
62
appendHead(node){
63
let firstNode = this.head.next;
64
65
this.head.next = node;
66
node.pre = this.head;
67
node.next = firstNode;
68
firstNode.pre = node;
69
}
70
71
removeTail(){
72
let key = this.tail.pre.key;
73
74
this.removeNode(this.tail.pre);
75
76
return key;
77
}
78
}
Copied!
Go Code:
1
type LRUCache struct {
2
Cap int
3
Hash map[int]*DoubleListNode
4
Cache *DoubleList
5
Size int
6
}
7
8
func Constructor(capacity int) LRUCache {
9
return LRUCache{
10
Cap: capacity,
11
Hash: make(map[int]*DoubleListNode),
12
Cache: NewDoubleList(),
13
}
14
}
15
16
func (this *LRUCache) Get(key int) int {
17
n, ok := this.Hash[key]
18
if !ok {
19
return -1
20
}
21
22
// 设为最近使用过
23
this.Cache.remove(n)
24
this.Cache.append(n)
25
26
return n.Val
27
}
28
29
func (this *LRUCache) Put(key int, value int) {
30
n, ok := this.Hash[key]
31
if !ok { // cache 不存在
32
// 增加节点
33
newNode := &DoubleListNode{Key: key, Val: value}
34
this.Hash[key] = newNode
35
this.Cache.append(newNode)
36
37
if this.Cap == this.Size { // 已满
38
// 删除尾节点
39
tailNode := this.Cache.tail.Pre
40
delete(this.Hash, tailNode.Key)
41
this.Cache.remove(tailNode)
42
} else {
43
this.Size++
44
}
45
} else {
46
// cache 存在
47
// 设为最近使用过
48
this.Cache.remove(n)
49
this.Cache.append(n)
50
51
n.Val = value // 更新值
52
}
53
}
54
55
type DoubleListNode struct {
56
Key, Val int
57
Pre, Next *DoubleListNode
58
}
59
60
type DoubleList struct {
61
Head, tail *DoubleListNode
62
}
63
64
func NewDoubleList() *DoubleList {
65
dl := &DoubleList{
66
Head: &DoubleListNode{},
67
tail: &DoubleListNode{},
68
}
69
dl.Head.Next = dl.tail
70
dl.tail.Pre = dl.Head
71
return dl
72
}
73
74
func (dl *DoubleList) append(n *DoubleListNode) {
75
n.Next = dl.Head.Next
76
n.Pre = dl.Head
77
dl.Head.Next.Pre = n
78
dl.Head.Next = n
79
}
80
81
func (dl *DoubleList) remove(n *DoubleListNode) {
82
n.Pre.Next = n.Next
83
n.Next.Pre = n.Pre
84
}
Copied!
PHP Code:
1
class LRUCache
2
{
3
public $hash = []; // key => DoubleListNode
4
public $cache;
5
public $size = 0;
6
public $cap; // 容量
7
8
/**
9
* @param Integer $capacity
10
*/
11
function __construct($capacity)
12
{
13
$this->cap = $capacity;
14
$this->cache = new DoubleList();
15
}
16
17
/**
18
* @param Integer $key
19
* @return Integer
20
*/
21
function get($key)
22
{
23
if (!isset($this->hash[$key])) return -1;
24
25
// 更新节点
26
/** @var DoubleListNode $node */
27
$node = $this->hash[$key];
28
$this->cache->remove($node);
29
$this->cache->append($node);
30
31
return $node->val;
32
}
33
34
/**
35
* @param Integer $key
36
* @param Integer $value
37
* @return NULL
38
*/
39
function put($key, $value)
40
{
41
if (isset($this->hash[$key])) { // key 存在
42
// 更新节点
43
/** @var DoubleListNode $node */
44
$node = $this->hash[$key];
45
$this->cache->remove($node);
46
$this->cache->append($node);
47
$node->val = $value;
48
} else { // key 不存在, 新增节点
49
$node = new DoubleListNode($key, $value);
50
$this->cache->append($node);
51
$this->hash[$key] = $node;
52
53
if ($this->size == $this->cap) {
54
// 删除原节点
55
$oldNode = $this->cache->tail->pre;
56
$this->cache->remove($oldNode);
57
unset($this->hash[$oldNode->key]);
58
} else {
59
$this->size++;
60
}
61
}
62
}
63
}
64
65
class DoubleListNode
66
{
67
public $key;
68
public $val;
69
public $pre;
70
public $next;
71
72
public function __construct($key = null, $val = null)
73
{
74
if ($key) $this->key = $key;
75
if ($val) $this->val = $val;
76
}
77
}
78
79
class DoubleList
80
{
81
public $head;
82
public $tail;
83
84
public function __construct()
85
{
86
$this->head = new DoubleListNode();
87
$this->tail = new DoubleListNode();
88
$this->head->next = $this->tail;
89
$this->tail->pre = $this->head;
90
}
91
92
public function append(DoubleListNode $node)
93
{
94
$node->pre = $this->head;
95
$node->next = $this->head->next;
96
$this->head->next->pre = $node;
97
$this->head->next = $node;
98
}
99
100
public function remove(DoubleListNode $node)
101
{
102
$node->pre->next = $node->next;
103
$node->next->pre = $node->pre;
104
}
105
}
Copied!
Python Code:
来自 leetcode
1
class DLinkedNode:
2
def __init__(self, key=0, value=0):
3
self.key = key
4
self.value = value
5
self.prev = None
6
self.next = None
7
8
9
class LRUCache:
10
def __init__(self, capacity: int):
11
self.cache = dict()
12
# 使用伪头部和伪尾部节点
13
self.head = DLinkedNode()
14
self.tail = DLinkedNode()
15
self.head.next = self.tail
16
self.tail.prev = self.head
17
self.capacity = capacity
18
self.size = 0
19
20
def get(self, key: int) -> int:
21
if key not in self.cache:
22
return -1
23
# 如果 key 存在，先通过哈希表定位，再移到头部
24
node = self.cache[key]
25
self.moveToHead(node)
26
return node.value
27
28
def put(self, key: int, value: int) -> None:
29
if key not in self.cache:
30
# 如果 key 不存在，创建一个新的节点
31
node = DLinkedNode(key, value)
32
# 添加进哈希表
33
self.cache[key] = node
34
# 添加至双向链表的头部
35
self.addToHead(node)
36
self.size += 1
37
if self.size > self.capacity:
38
# 如果超出容量，删除双向链表的尾部节点
39
removed = self.removeTail()
40
# 删除哈希表中对应的项
41
self.cache.pop(removed.key)
42
self.size -= 1
43
else:
44
# 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
45
node = self.cache[key]
46
node.value = value
47
self.moveToHead(node)
48
49
def addToHead(self, node):
50
node.prev = self.head
51
node.next = self.head.next
52
self.head.next.prev = node
53
self.head.next = node
54
55
def removeNode(self, node):
56
node.prev.next = node.next
57
node.next.prev = node.prev
58
59
def moveToHead(self, node):
60
self.removeNode(node)
61
self.addToHead(node)
62
63
def removeTail(self):
64
node = self.tail.prev
65
self.removeNode(node)
66
return node
Copied!
复杂度分析
- 时间复杂度：$O(1)$
- 空间复杂度：$O(n)$ n 为容量的大小
最近更新 6mo ago