第六章 - 高频考题(困难)
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.
    确定需要使用的数据结构
    1. 1.
      根据题目要求,存储的数据需要保证顺序关系(逻辑层面) ===> 使用数组,链表等保证顺序关系
    2. 2.
      同时需要对数据进行频繁的增删, 时间复杂度 O(1) ==> 使用链表等
    3. 3.
      对数据进行读取时, 时间复杂度 O(1) ===> 使用哈希表 最终采取双向链表 + 哈希表
      1. 1.
        双向链表按最后一次访问的时间的顺序进行排列, 链表头部为最近访问的节点
      2. 2.
        哈希表,以关键字为键,以链表节点的地址为值
  2. 2.
    put 操作 通过哈希表, 查看传入的关键字对应的链表节点, 是否存在
    1. 1.
      如果存在,
      1. 1.
        将该链表节点的值更新
      2. 2.
        将该该链表节点调整至链表头部
    2. 2.
      如果不存在
      1. 1.
        如果链表容量未满,
        1. 1.
          新生成节点,
        2. 2.
          将该节点位置调整至链表头部
      2. 2.
        如果链表容量已满
        1. 1.
          删除尾部节点
        2. 2.
          新生成节点
        3. 3.
          将该节点位置调整至链表头部
      3. 3.
        将新生成的节点,按关键字为键,节点地址为值插入哈希表
  3. 3.
    get 操作 通过哈希表, 查看传入的关键字对应的链表节点, 是否存在
    1. 1.
      节点存在
      1. 1.
        将该节点位置调整至链表头部
      2. 2.
        返回该节点的值
    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 为容量的大小