伯牙绝弦少冰少糖是你的武器吗 Wanna touch your body all night投我那够一加那 那咪加那 内呢gin 木漏 打啦哇Put you on my back seat Back seat Back seat uh woo uh 一gi不露 内泼料多 You don't have to fight 不哥漏我哈几马 Put you on my back seat Back seat Back seat Now let's get it on on my back seat

我狗头发都这么长了 你不染不卷什么意思[微笑]不变发型是你的武器吗 投我那一够 加那 那加咪 那 内呢gin 木漏 打啦哇Put you on my back seatBack seat Back seat uh woo uh 一gi不露 内泼You don't have to fight 不漏哥 我哈几马Put you on my back seat Back seat Back seatNow let's get it on on my back seat

【每天一道算法题(75/150)】LRU 缓存
思路：一道中等写一下午

首先，LRU 是最近最少使用算法，也被称为页面置换算法。是怎么实现的呢。给每一个页面一个访问字段，记为 T，T 为这个页面自上次被访问以来所经历的时间。当必须要淘汰一个页面时，找出所有 T 中最大的，即最少使用的那个页面淘汰。

其次，题目要求所实现的 LRU 算法的类（后文简称 cache）的 get 和 put 方法的时间复杂度为 o(1)。

那么问题来了，get 还好说，map 的 get 方法时间复杂度本身就为 o(1)，put 方法难在需要：

1. 先找到最大的 T
2. 将新的 key, value 放入 cache

那么无论是哈希表，还是链表，双向链表，有序链表及有序双向链表都无法做到时间复杂度为 0(1)，除非

哈希表 + 双向链表。

下面操作步骤讲讲双向链表的 get 方法：

操作步骤：
put [1,1]
put[2,2]
get[1]

初始化双向链表为：
head <-> tail

第一步：put [1,1]
head <-> (1,1) <-> tail

第二步：put [2,2]
head <-> (2,2) <-> (1,1) <-> tail

第三步：get [1]

a. 先通过哈希表找到链表所在位置，返回 node
b. 在链表中将 [1,1] 移除
此时链表状态：head <-> (2,2) <-> tail
c. 在链表中将 [1,1] 插入到链表头部
此时链表状态：had <-> (1,1) <-> (2,2) <-> tail

返回 node.val = 1；

经过上述操作，把 get 的 Key 的 value 返回了，链表也更新了，保证了最新使用节点（页面）的在最前面（链表头部）。