【牛客算法】某司面试算法题：设计LRU缓存结构

一、算法题描述

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()：删除链表尾部节点（最久未使用节点），并返回该节点。