题目大意
#
要求：实现一个 LRU（最近最少使用）缓存机制，并且在 O(1) 时间复杂度内完成 get、put 操作。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存。int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
解题思路
#
LRU（最近最少使用缓存）是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。LRU 更新和插入新页面都发生在链表首，删除页面都发生在链表尾。
代码
#
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
|
class Node:
def __init__(self, key=None, val=None, prev=None, next=None):
self.key = key
self.val = val
self.prev = prev
self.next = next
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.hashmap = dict()
self.head = Node()
self.tail = Node()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.hashmap:
return -1
node = self.hashmap[key]
self.move_node(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.hashmap:
node = self.hashmap[key]
node.val = value
self.move_node(node)
return
if len(self.hashmap) == self.capacity:
self.hashmap.pop(self.head.next.key)
self.remove_node(self.head.next)
node = Node(key=key, val=value)
self.hashmap[key] = node
self.add_node(node)
def remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_node(self, node):
self.tail.prev.next = node
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev = node
def move_node(self, node):
self.remove_node(node)
self.add_node(node)
|