题解 | #设计LRU缓存结构#
设计LRU缓存结构
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84
设计思路:通过HashMap查找是否存在对应的key,双向链表进行插入和删除。时间复杂度O(1),空间复杂度O(N)。
-
对于get操作
- 若HashMap中存在,先从链表中删除此节点,再将此节点添加到末尾保持最新,最后返回节点值即可;
- 否则,直接返回-1;
-
对于set操作
- 若HashMap中存在,更新HashMap,同时从链表中删除此节点,再将此节点添加到末尾保持最新;
- 否则
- 若当前容量等于缓存容量,先获取链首元素(最不常用元素)old,从链表中删除,同时将old节点对应的key从HashMap中删除。最后将当前节点添加到HashMap中,并插入到链表的末尾;
- 否则,直接插入HashMap,同时添加到链表末尾。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
public class Solution {
private Dictionary<int, Node> cache; // 用于缓存节点键和节点的对应关系
private LinkedList<Node> nodes; // 单链表作为队列,队首最常用,队尾最不常用
private int capacity; // 缓存容量
public Solution(int capacity) {
this.capacity = capacity;
cache = new Dictionary<int, Node>();
nodes = new LinkedList<Node>();
}
/**
* 查看cache中是否存在,若存在将节点从链表中删除,并添加到末尾保持最新,若不存在返回-1;
*/
public int get(int key) {
if (cache.ContainsKey(key)) {
Node node = cache[key];
nodes.Remove(node); // 先移除
nodes.AddLast(node); // 再添加到末尾
return node.value; // 返回结果
}
return -1;
}
public void set(int key, int value) {
Node curNode = new Node(key, value);
if (!cache.ContainsKey(key)) { // 不存在,添加
int curCapacity = cache.Count; // 当前缓存中的容量
if (curCapacity == capacity) { // 满了,将不常用的移除
Node old = nodes.First(); // 先保留
nodes.RemoveFirst(); // 从队列中移除
cache.Remove(old.key); // 从缓存中移除
}
nodes.AddLast(curNode); // 添加到链表末尾,保持最新
cache.Add(key, curNode); // 添加到缓存中
} else { // 已存在,更新
Node node = cache[key];
cache.Remove(key); // 从缓存中移除
cache.Add(key, curNode); // 添加到缓存
nodes.Remove(node); // 移除
nodes.AddLast(curNode); // 追加末尾
}
}
}
public class Node
{
public int key, value;
public Node(int key, int value)
{
this.key = key;
this.value = value;
}
}
#缓存设计#