一、算法题描述
1.1 算法描述
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
Solution(int capacity)以正整数作为容量capacity初始化 LRU 缓存get(key)：如果关键字key存在于缓存中，则返回key对应的value值，否则返回-1。set(key, value)：将记录(key, value)插入该结构，如果关键字key已经存在，则变更其数据值value，如果不存在，则向缓存中插入该组key-value，如果key-value的数量超过capacity，弹出最久未使用的key-value
1.2 提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
数据范围:
- 1≤capacity<=10^5
- 0≤key,val≤2×10^9
- 1≤n≤10^5
1.3 示例
输入
["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2
输出
["null","null","1","null","-1","null","-1","3","4"]
说明
我们将缓存看成一个队列，最后一个参数为2代表capacity，所以
Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
output=s.get(1); // 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null"
output=s.get(2); // 因为get(2)操作，不存在对应的key，故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null"
output=s.get(1); // 因为get(1)操作，不存在对应的key，故get操作返回"-1"
output=s.get(3); //因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
output=s.get(4); //因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"
1.4 提供的代码
import java.util.*;public class Solution {public Solution(int capacity) {// write code here}public int get(int key) {// write code here}public void set(int key, int value) {// write code here}
}/*** Your Solution object will be instantiated and called as such:* Solution solution = new Solution(capacity);* int output = solution.get(key);* solution.set(key,value);*/
二、算法实现
这是典型的 LRU 缓存问题，可以使用 HashMap 和 双向链表 来实现，以保证 get 和 set 操作都在 O(1)时间复杂度内完成。
2.1 解题思路
- 使用 HashMap：将
key映射到对应的节点，这样可以在 O(1) 时间内查找元素。 - 使用双向链表：保存缓存的顺序，最久未使用的元素在链表的尾部，最近使用的在头部。
- 每次访问
get或set，将对应节点移动到链表头部。 - 当缓存超出容量
capacity时，移除链表尾部节点（最久未使用）。
- 每次访问
2.2 实现细节
- 构造函数
Solution(int capacity)：初始化capacity，以及HashMap和双向链表的头尾哨兵节点（dummy nodes），方便处理边界条件。 - 方法
get(int key)：如果key存在，则将该节点移动到链表头部并返回其value；否则返回-1。 - 方法
set(int key, int value)：如果key已存在，则更新其value并移动到链表头部；否则，插入新节点到头部。若超过容量，则移除链表尾部节点。
2.3 代码实现
代码实现如下：
import java.util.HashMap;public class Solution {// 定义双向链表节点private class Node {int key, value; // 键值对Node prev, next; // 前后指针指向前后节点Node(int k, int v) { // 构造方法this.key = k;this.value = v;}}private int capacity; // LRU 缓存的最大容量private HashMap<Integer, Node> map; // 存储键值对<key, Node> 的映射，用于O(1)访问private Node head, tail; // 双向链表的哨兵头节点和尾节点public Solution(int capacity) {this.capacity = capacity; // 初始化缓存的容量this.map = new HashMap<>(); // 初始化哈希表// 初始化双向链表的哨兵节点（不存储实际数据，方便边界操作）this.head = new Node(0, 0); // 头哨兵节点this.tail = new Node(0, 0); // 尾哨兵节点head.next = tail; // 初始化链表，将头尾哨兵节点相连tail.prev = head;}// 获取缓存中指定键的值public int get(int key) {if (map.containsKey(key)) { // 检查键是否存在Node node = map.get(key); // 获取对应节点moveToHead(node); // 将该节点移到链表头部，标记为最近使用return node.value; // 返回对应的值}return -1; // 不存在则返回 -1}// 插入或更新缓存中的键值对public void set(int key, int value) {if (map.containsKey(key)) { // 如果键已存在Node node = map.get(key); // 获取已有节点node.value = value; // 更新节点的值moveToHead(node); // 将节点移到链表头部，标记为最近使用} else {// 若键不存在，则创建新节点Node newNode = new Node(key, value);map.put(key, newNode); // 将新节点加入哈希表addNode(newNode); // 插入新节点到链表头部// 如果超过容量，移除最久未使用节点（链表尾部节点）if (map.size() > capacity) {Node tail = removeTail(); // 删除尾部节点map.remove(tail.key); // 从哈希表中移除对应的键}}}// 辅助方法：在链表头部添加节点private void addNode(Node node) {node.next = head.next; // 将新节点的 next 指向 head 的 nextnode.prev = head; // 新节点的 prev 指向 headhead.next.prev = node; // 将 head 原来的 next 的 prev 指向新节点head.next = node; // head 的 next 指向新节点}// 辅助方法：从链表中移除节点private void removeNode(Node node) {node.prev.next = node.next; // 将 node 的前节点的 next 指向 node 的 nextnode.next.prev = node.prev; // 将 node 的后节点的 prev 指向 node 的 prev}// 辅助方法：将节点移动到链表头部（表示最近使用）private void moveToHead(Node node) {removeNode(node); // 先从链表中删除节点addNode(node); // 然后再添加到链表头部}// 辅助方法：移除链表尾部节点并返回该节点（最久未使用节点）private Node removeTail() {Node res = tail.prev; // 获取尾节点前的节点removeNode(res); // 从链表中删除return res; // 返回被移除的节点}
}
复杂度分析
- 时间复杂度：
get和set操作都是O(1)，因为HashMap查找、插入和双向链表操作都在常数时间内完成。 - 空间复杂度：
O(capacity)，用于存储HashMap和双向链表中的节点。
代码详解
-
Node类：Node是双向链表的节点类，包含key和value，以及prev和next指针用于双向链接。
-
构造方法
Solution(int capacity)：- 初始化
capacity和map，并创建链表的head和tail哨兵节点。 - 通过将
head.next指向tail，tail.prev指向head，形成一个空的双向链表（仅有哨兵节点）。
- 初始化
-
方法
get(int key)：- 检查
key是否在map中。 - 如果在，则通过
moveToHead(node)将对应节点移到链表头部，以标记该节点为最近使用。 - 返回节点的
value。 - 如果
key不在map中，则返回-1。
- 检查
-
方法
set(int key, int value)：- 检查
key是否在map中。- 如果
key已存在，更新其value，并调用moveToHead(node)将节点移到链表头部。 - 如果
key不存在，创建新节点，并插入到链表头部。 - 检查
map的大小是否超过capacity，若超过则调用removeTail()删除链表尾部节点，并从map中移除对应键。
- 如果
- 检查
-
辅助方法：
addNode(Node node)：将新节点插入到链表头部，链表更新顺序为head <-> node <-> head.next。removeNode(Node node)：从链表中删除指定节点。moveToHead(Node node)：将节点先删除，再插入链表头部，更新为最近使用。removeTail()：删除链表尾部节点（最久未使用节点），并返回该节点。
关键点总结
- HashMap 作为缓存记录的快速查找结构，使得
get和set操作在 O(1) 时间完成。 - 双向链表 维护 LRU 顺序，头部表示最近使用，尾部表示最久未使用。
- 容量管理：当超出容量时，通过
removeTail()删除尾节点（最久未使用），并从map中移除。
