腾讯真喜欢问这个算法啊。。。
吴师兄约 6 分钟最近几个互联网大厂都开启了实习招聘，相比于去年的这个时候，数量居然多了一些，难道是互联网开始回暖了？？？
在某客网上看了一些同学的面经分享，发现有几道算法题考察的还蛮频繁的，比如 LeetCode 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) 的平均时间复杂度运行。
提示：
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105最多调用 2 * 10^5次get和put
题目解析
通过结合使用哈希表（HashMap）和双向链表来高效实现缓存策略，使得其访问和修改的时间复杂度都是O(1)。
ALNode 类定义
ALNode类定义了双向链表的节点，每个节点包含一个值val、一个指向下一个节点的指针nextNode和一个指向上一个节点的指针preNode。
LRUCache 类定义
LRUCache类是 LRU 缓存的主体实现。maps哈希表用于存储键和对应的值（以及其在双向链表中的节点），以实现快速查找。head和tail是哨兵节点，分别代表双向链表的头部和尾部，用于简化节点插入和删除操作。capacity表示缓存的容量。length表示当前缓存中的元素数量。
LRUCache 方法解释
构造函数 LRUCache(int capacity)
初始化 head和tail节点，并将它们互相连接，初始化maps为新的哈希表，设置缓存容量capacity。
get(int key) 方法
如果 key存在于哈希表中，则需要将对应的节点移动到双向链表的头部（表示最近使用）。先从哈希表中获取节点，然后从双向链表中断开该节点，并将其插入到头部节点的后面。 返回哈希表中对应 key的值。如果key不存在，返回-1。
put(int key, int value) 方法
首先检查 key 是否已存在于哈希表中： 如果达到上限，则删除双向链表尾部的节点（最久未使用的数据）并从哈希表中移除对应的键值对。 接着，创建一个新的节点，将其添加到双向链表的头部，并在哈希表中添加键值对。 如果存在，更新其值，并将对应的节点移动到双向链表的头部。 如果不存在，首先检查当前缓存长度是否已达到容量上限： 每次添加新节点时，如果是新插入的键，则递增 length。
通过上述方法，LRU 缓存能够确保最近被访问或修改的元素始终靠近双向链表的头部，而最久未被访问的元素会被移动到尾部并在需要时被淘汰，从而实现了LRU缓存策略。
代码虽然比较长，但逻辑捋清楚之后还是非常好写出来的。
参考代码
// 使用双向链表来实现
class ALNode{ // 节点值
public int val;
// 当前节点的下一个节点
public ALNode nextNode;
// 当前节点的上一个节点
public ALNode preNode;
// 构造
ALNode(int val){
this.val = val;
}
}
public class LRUCache {
// 利用哈希表来存储元素
public Map<Integer, Object[]> maps;
// 为了方便使用，默认双向链表有两个节点
// 这样，哪怕只有一个节点时，依旧有上节点、下节点
// 头节点
public ALNode head;
// 头节点
public ALNode tail;
// 实际容量，意味着最多存储这么多节点
private int capacity;
// 长度
public int length;
public LRUCache(int capacity) {
// 初始化 head
head = new ALNode(-1);
// 初始化 tail
tail = new ALNode(-1);
// 初始化 maps
maps = new HashMap<>();
// 初始化 capacity
this.capacity = capacity;
// 连接 head 和 tail
head.nextNode = tail;
tail.preNode = head;
}
public int get(int key) {
// 判断哈希表中是否存储了 key
// 如果存在，不仅需要返回 key 的 value
// 同样，需要操作双向链表，使得
// 1、当前这个 key 对应的节点放到链表的最前面，即 head 的下一个节点
// 2、其余节点维持原来的顺序
if(maps.containsKey(key)){
// 获取节点值
ALNode cur = (ALNode) maps.get(key)[0];
// 获取当前节点的上一个节点
ALNode preNode = cur.preNode;
// 获取当前节点的下一个节点
ALNode nextNode = cur.nextNode;
// 让这两个上下节点连接起来，cur 也就消失了
preNode.nextNode = nextNode;
nextNode.preNode = preNode;
// 把 cur 挪到 head 的 nextNode 位置
// 1、先获取原先 head 的 nextNode 节点
ALNode tmp = head.nextNode;
// 2、修改 head 的 nextNode 节点为 cur
head.nextNode = cur;
// 3、cur 重新连接上 tmp
cur.nextNode = tmp;
// 4、tmp 也连接上 cur
tmp.preNode = cur;
// 5、cur 上一个节点指向 head
cur.preNode = head;
// 最后才返回 map 的值
return (Integer) maps.get(key)[1];
}
// 否则返回 -1
return -1;
}
public void put(int key, int value) {
// 判断哈希表中是否存储了 key
// 如果存在，不仅需要返回 key 的 value
// 同样，需要操作双向链表，使得
// 1、key 对应的节点值 value 需要修改，采取节点替换的操作
// 2、这个节点需要挪到最前面
if(maps.containsKey(key)){
// 获取节点值
ALNode cur = (ALNode) maps.get(key)[0];
// 获取当前节点的上一个节点
ALNode preNode = cur.preNode;
// 获取当前节点的下一个节点
ALNode nextNode = cur.nextNode;
// 让这两个上下节点连接起来，cur 也就消失了
preNode.nextNode = nextNode;
nextNode.preNode = preNode;
// 把 cur 挪到 head 的 nextNode 位置
// 1、先获取原先 head 的 nextNode 节点
ALNode tmp = head.nextNode;
// 2、修改 head 的 nextNode 节点为 cur
head.nextNode = cur;
// 3、cur 重新连接上 tmp
cur.nextNode = tmp;
// 4、tmp 也连接上 cur
tmp.preNode = cur;
// 5、cur 上一个节点指向 head
cur.preNode = head;
// 更新节点
maps.put(key, new Object[]{cur, value});
return;
}
// 如果哈希表中不包含 key 对应的节点，那么需要判断缓存是否满了
// 如果满了，需要把最后一个节点删除掉
if(length == capacity){
// 即将被删除的节点
ALNode delNode = tail.preNode;
// 即将被删除的节点的上一个节点
ALNode delPreNode = tail.preNode.preNode;
// delPreNode 跳过了 delNode
delPreNode.nextNode = tail;
tail.preNode = delPreNode;
// 哈希表移除 delNode 对应的值
maps.remove(delNode.val);
// 链表的长度更新一下
length--;
}
// 再把 key 节点添加到最前面去
ALNode cur = new ALNode(key);
// 把 cur 挪到 head 的 nextNode 位置
// 1、先获取原先 head 的 nextNode 节点
ALNode tmp = head.nextNode;
// 2、修改 head 的 nextNode 节点为 cur
head.nextNode = cur;
// 3、cur 重新连接上 tmp
cur.nextNode = tmp;
// 4、tmp 也连接上 cur
tmp.preNode = cur;
// 5、cur 上一个节点指向 head
cur.preNode = head;
// 更新哈希表
maps.put(key, new Object[]{cur, value});
// 更新 length
length++;
return;
}
}
作者：吴师兄
来源：吴师兄学算法