0%

【数据结构】LeetCode.146 LRU缓存机制

题目描述

原题链接: 146. LRU缓存机制

运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put

  • 获取数据 get(key)
    • 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
  • 写入数据 put(key, value)
    • 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
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

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作?

题目分析

实现 LRU 缓存机制, 需要在 O(1) 时间内完成添加、修改、查找

首先想到的肯定是 字典(哈希表)来存储 key-value, 但是由于字典是因为字典本身是无序, 无法做到淘汰最久未使用的元素

还需要有类似于队列的来存储访问的时间先后顺序, 需要指出以下操作:

  • 在末尾加入一项(插入)
  • 删除头部元素(LRU淘汰)
  • 将某一项移到末尾(修改/查找)

首先考虑列表和双端队列:

  • 满足在O(1)时间内插入到尾部与删除头部元素
  • 但是不到在O(1)时间内将任意元素移到队尾(将元素后面的内容往前移需要O(n复杂度)

之后考虑单链表:

单链表可以实现在O(1)时间内在表头和表尾插入元素
但是单链表需要遍历一遍才能找到指定元素的前一个元素, 也做不到在O(1)时间内将任意元素移到队尾

哈希 + 双链表就能很好的解决这个问题:

key为键值对, 值为双链表节点。

结构如图所示:

lrucache结构

代码:

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
class ListNode:
"""
双端链表
"""
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None

class LRUCache:
"""
字典 + 双端链表
"""
def __init__(self, capacity: int):
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
self.capacity = capacity
self.ht = {}

def remove_head_node(self):
"""
删除双链表头结点(最久没有访问过的节点)
head 的 next 指向表头节点的下一个节点
表头节点下一节点的 prev 指向 head, 中间的节点就相当于被删了
:return: 被删除的节点的键, 需要拿到这个去删除字典中键
"""
node = self.head.next
self.head.next = node.next
node.next.prev = node.prev
return node.key

def append_to_tail(self, node: ListNode):
"""
将 node 节点(最近访问的节点)加到表尾
表尾节点(tail.prev)的 next 指针指向node
node 的 prev 指针指向表尾节点, next 指针指向 tail
tail 的 prev 指针指向 node
:param node: 要加到表尾的节点
:return:
"""
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node

def move_to_tail(self, node: ListNode) -> None:
"""
将链表节点移至表尾
1. 节点 node 的前一个节点的 next 指针指向node后一个节点
节点 node 的后一个节点的 prev 指针指向node前一个节点
2. node 插到表尾
:param node: 要移动的节点
:return:
"""
node.prev.next = node.next
node.next.prev = node.prev
self.append_to_tail(node)

def get(self, key: int) -> int:
"""
查找元素 时间复杂度 O(1):=
1. 元素不存在, 返回 -1
2. 元素存在, 将节点提到链表尾, 返回节点的 val 值
:param key: 要查找的键
:return:
"""
node = self.ht.get(key)
if not node:
return -1
self.move_to_tail(node)
return node.val

def put(self, key: int, value: int) -> None:
"""
1. key不存在的情况, 插入元素
缓存未满, 插到表尾
缓存已满, 且key在字典中不存在, 插到表尾, 删除表头, 删除字典中的键值对
2. key已经存在的情况, 修改值, 节点移到表尾
:param key: 要插入的键
:param value: 插入键对应的值
:return:
"""
if (not key in self.ht):
if (len(self.ht) >= self.capacity):
removed_key = self.remove_head_node()
self.ht.pop(removed_key)
node = ListNode(key, value)
self.ht[key] = node
self.append_to_tail(node)
else:
node = self.ht[key]
node.val = value
self.move_to_tail(node)

参考: