146. LRU 缓存

标题-中等难度

请你计划并实现一个满意 LRU (近来最少使用) 缓存 束缚的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 假如关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 假如关键字 key 已经存在，则变更其数据值 value ；假如不存在，则向缓存中插入该组 key-value 。假如插入使用导致关键字数目凌驾 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的匀称时间复杂度运行。
示例

示例：
   输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
表明
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该使用会使得关键字 2 取消，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该使用会使得关键字 1 取消，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
  提示：
   

• 1 <= capacity <= 3000
  
• 0 <= key <= 10000
  
• 0 <= value <= 105
  
• 最多调用 2 * 105 次 get 和 put
  

  泉源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络全部。商业转载请接洽官方授权，非商业转载请注明出处。
1. 链表

时间
2428ms
击败 96.49%使用 Python 的用户
内存
75.66mb
击败 44.44%使用 Python 的用户

1. class DoubleLinkedNode:
2.     def __init__(self, key=0,value=0):
3.         self.key = key
4.         self.value = value
5.         self.prev = None
6.         self.next = None
8. class LRUCache(object):
10.     def __init__(self, capacity):
11.         """
12.         :type capacity: int
13.         """
14.         self.capacity = capacity
15.         self.dic = {}
16.         # 创建节点作为列表头
17.         self.head = DoubleLinkedNode()
18.         # 创建节点作为列表尾
19.         self.tail = DoubleLinkedNode()
20.         # 新建链表只有表头和表尾，让表头下一项为表尾
21.         self.head.next = self.tail
22.         # 让表尾前一项为表头，完成链表连接
23.         self.tail.prev = self.head
24.         self.l = 0
27.     def get(self, key):
28.         """
29.         :type key: int
30.         :rtype: int
31.         """
32.         # 如果key不存在于字典，返回-1
33.         if key not in self.dic:
34.             return -1
35.         # 如果存在，获取节点
36.         node = self.dic[key]
37.         # 把节点移至头
38.         self.moveToHead(node)
39.         # 返回节点值
40.         return node.value
43.     def put(self, key, value):
44.         """
45.         :type key: int
46.         :type value: int
47.         :rtype: None
48.         """
49.         # 如果未在字典中
50.         if key not in self.dic:
51.             # 创建新节点
52.             node = DoubleLinkedNode(key,value)
53.             # 将节点添加至字典
54.             self.dic[key] = node
55.             # 将节点添加至头部
56.             self.addToHead(node)
57.             # 计数字典中节点个数
58.             self.l += 1
59.             # 如果数量超出容量
60.             if self.l > self.capacity:
61.                 # 获取尾部节点
62.                 exNode = self.tail.prev
63.                 # 移除尾部节点
64.                 self.removeNode(exNode)
65.                 # 移除字典中的尾部节点
66.                 self.dic.pop(exNode.key)
67.                 # 字典节点数-1
68.                 self.l -= 1
69.         # 如果存在于字典
70.         else:
71.             # 获取原先存在的节点
72.             node = self.dic[key]
73.             # 更新节点值
74.             node.value = value
75.             # 更新过后移到链表头
76.             self.moveToHead(node)
78.     def addToHead(self, node):
79.         # node在self.head后面
80.         node.prev = self.head
81.         # node在self.head下一个节点的前面
82.         node.next = self.head.next
83.         # self.head和它下一个节点中间插入node节点
84.         self.head.next.prev = node
85.         # 让node成为self.head下一个节点
86.         self.head.next = node
88.     def removeNode(self, node):
89.         # 让节点前一项的next存储节点下一项的地址
90.         node.prev.next = node.next
91.         # 节点的下一项的prev存储节点前一项的地址，删除了节点并重新连接链表结构
92.         node.next.prev = node.prev
94.     def moveToHead(self, node):
95.         # 移除原先的node
96.         self.removeNode(node)
97.         # 将node添加到链表头
98.         self.addToHead(node)
100. # Your LRUCache object will be instantiated and called as such:
101. # obj = LRUCache(capacity)
102. # param_1 = obj.get(key)
103. # obj.put(key,value)

复制代码

来源：https://blog.csdn.net/Ashiu/article/details/132287967
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！