题解 | #设计LRU缓存结构#

设计思路：通过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;
    }   
}