146.LRU缓存

LeetCode LeetCode 热题100 哈希表 链表 设计 双向链表
发布时间 :
字数:3.9k 阅读 : 评论:
  1. 146.LRU缓存
    1. 146.1 题目
    2. 146.2 题解
      1. 方法一：双向链表 + 哈希表
        1. 思路
        2. 复杂度分析
        3. 代码
    3. 146.3 代码
    4. 146.4 运行结果

146.LRU缓存

146.1 题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。

示例：

输入：

["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]

输出：

[null, null, null, 1, null, -1, null, -1, 3, 4]

解释：

LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); 缓存是 {1=1}
lRUCache.put(2, 2); 缓存是 {1=1, 2=2}
lRUCache.get(1); 返回 1
lRUCache.put(3, 3); 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); 返回 -1（未找到）
lRUCache.put(4, 4); 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); 返回 -1（未找到）
lRUCache.get(3); 返回 3
lRUCache.get(4); 返回 4

提示：

  • 1 <= capacity <= 3000
  • 0 <= key <= 10^4
  • 0 <= value <= 10^5
  • 最多调用 2 * 10^5 次 get 和 put

146.2 题解

方法一：双向链表 + 哈希表

思路

LRU 的核心是：最近使用的放前面，最久未使用的放后面。需要两个数据结构配合：

  • 哈希表：key → 链表节点，实现 O(1) 查找
  • 双向链表：维护访问顺序，头部是最近使用的，尾部是最久未使用的

为什么用双向链表？因为删除节点时需要知道前驱节点，单向链表做不到 O(1) 删除。

具体操作：

  • get(key)：哈希表找到节点，移到链表头部，返回值
  • put(key, value)：
    • key 存在：更新值，移到头部
    • key 不存在：新建节点放头部，如果超出容量，删除尾部节点

举个例子：容量为2

  • put(1,1)：{1=1}
  • put(2,2)：{1=1, 2=2}
  • get(1)：返回1，1变成最近使用，{2=2, 1=1}
  • put(3,3)：超出容量，删除最久未使用的2，{1=1, 3=3}
  • get(2)：返回-1

复杂度分析

  • 时间复杂度：get 和 put 都是 O(1)
  • 空间复杂度：O(capacity)

代码

// 方法一：双向链表 + 哈希表实现 LRU 缓存
// 核心思路：双向链表维护访问顺序，哈希表 O(1) 查找节点
public class LRUCache
{
    private class CacheNode
    {
        public int key;
        public int value;
        public CacheNode? prev;
        public CacheNode? next;

        public CacheNode() { }

        public CacheNode(int key, int value)
        {
            this.key = key;
            this.value = value;
        }
    }

    private readonly Dictionary<int, CacheNode> cacheDict;
    private readonly CacheNode head;
    private readonly CacheNode tail;
    private readonly int capacity;

    public LRUCache(int capacity)
    {
        if (capacity <= 0)
            throw new ArgumentOutOfRangeException(nameof(capacity), "capacity must be positive.");

        this.capacity = capacity;
        cacheDict = new Dictionary<int, CacheNode>(capacity);
        head = new CacheNode();
        tail = new CacheNode();
        head.next = tail;
        tail.prev = head;
    }

    public int Get(int key)
    {
        if (!cacheDict.TryGetValue(key, out CacheNode? node))
            return -1;

        MoveToHead(node!);
        return node!.value;
    }

    public void Put(int key, int value)
    {
        if (cacheDict.TryGetValue(key, out CacheNode? node))
        {
            node!.value = value;
            MoveToHead(node!);
            return;
        }

        CacheNode newNode = new CacheNode(key, value);
        cacheDict.Add(key, newNode);
        AddToHead(newNode);

        if (cacheDict.Count > capacity)
        {
            CacheNode tailNode = RemoveTail();
            cacheDict.Remove(tailNode.key);
        }
    }

    private void AddToHead(CacheNode node)
    {
        node.prev = head;
        node.next = head.next;
        head.next!.prev = node;
        head.next = node;
    }

    private void RemoveNode(CacheNode node)
    {
        node.prev!.next = node.next;
        node.next!.prev = node.prev;
        node.prev = null;
        node.next = null;
    }

    private void MoveToHead(CacheNode node)
    {
        if (node.prev == head)
            return;
        RemoveNode(node);
        AddToHead(node);
    }

    private CacheNode RemoveTail()
    {
        CacheNode tailNode = tail.prev!;
        RemoveNode(tailNode);
        return tailNode;
    }
}

146.3 代码

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        #region 题目

        // 请你设计并实现一个满足 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) 的平均时间复杂度运行。

        // 示例：
        // 输入
        // ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
        // [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
        // 输出
        // [null, null, null, 1, null, -1, null, -1, 3, 4]

        // 解释
        // LRUCache lRUCache = new LRUCache(2);
        // lRUCache.put(1, 1); // 缓存是 {1=1}
        // lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
        // lRUCache.get(1);    // 返回 1
        // lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        // lRUCache.get(2);    // 返回 -1 (未找到)
        // lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        // lRUCache.get(1);    // 返回 -1 (未找到)
        // lRUCache.get(3);    // 返回 3
        // lRUCache.get(4);    // 返回 4

        // 提示：
        // 1 <= capacity <= 3000
        // 0 <= key <= 104
        // 0 <= value <= 105
        // 最多调用 2 * 105 次 get 和 put

        #endregion

        #region 测试

        Console.WriteLine("=== 示例测试 ===");

        // 示例测试
        LRUCache lruCache = new LRUCache(2);

        lruCache.Put(1, 1); // 缓存是 {1=1}
        lruCache.Put(2, 2); // 缓存是 {1=1, 2=2}

        Console.WriteLine($"get(1) = {lruCache.Get(1)}"); // 返回 1

        lruCache.Put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        Console.WriteLine($"get(2) = {lruCache.Get(2)}"); // 返回 -1 (未找到)

        lruCache.Put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
        Console.WriteLine($"get(1) = {lruCache.Get(1)}"); // 返回 -1 (未找到)
        Console.WriteLine($"get(3) = {lruCache.Get(3)}"); // 返回 3
        Console.WriteLine($"get(4) = {lruCache.Get(4)}"); // 返回 4

        Console.WriteLine("\n=== 边界测试 ===");

        // 边界测试：容量为1
        LRUCache lruCache1 = new LRUCache(1);
        lruCache1.Put(1, 1);
        Console.WriteLine($"容量1测试 - get(1) = {lruCache1.Get(1)}"); // 返回 1
        lruCache1.Put(2, 2);
        Console.WriteLine($"容量1测试 - get(1) = {lruCache1.Get(1)}"); // 返回 -1
        Console.WriteLine($"容量1测试 - get(2) = {lruCache1.Get(2)}"); // 返回 2

        Console.WriteLine("\n=== 更新值测试 ===");

        // 更新值测试
        LRUCache lruCache2 = new LRUCache(2);
        lruCache2.Put(1, 1);
        lruCache2.Put(2, 2);
        lruCache2.Put(1, 10); // 更新值
        Console.WriteLine($"更新值测试 - get(1) = {lruCache2.Get(1)}"); // 返回 10
        Console.WriteLine($"更新值测试 - get(2) = {lruCache2.Get(2)}"); // 返回 2

        #endregion
    }

    #region 答案

    // 方法一：双向链表 + 哈希表实现LRU缓存
    /// <summary>
    /// 实现 LRU (最近最少使用) 缓存约束的数据结构。
    /// 核心思路：使用双向链表维护访问顺序，哈希表提供 O(1) 查找。
    /// </summary>
    /// <remarks>
    /// 时间复杂度：Get 和 Put 操作的平均时间复杂度均为 O(1)。
    /// 空间复杂度：O(capacity)，其中 capacity 为缓存的最大容量。
    /// </remarks>
    public class LRUCache
    {
        /// <summary>
        /// 双向链表节点类，用于存储缓存条目及维护访问顺序。
        /// </summary>
        /// <remarks>
        /// 每个节点包含 key、value 以及指向前后节点的 prev/next 指针。
        /// 必须存储 key 的原因：当删除尾部节点时，需要用 key 从哈希表中移除对应条目。
        /// </remarks>
        private class CacheNode
        {
            /// <summary>
            /// 缓存条目的关键字，用于哈希表查找。
            /// </summary>
            public int key;

            /// <summary>
            /// 缓存条目的值，存储实际需要缓存的数据。
            /// </summary>
            public int value;

            /// <summary>
            /// 指向双向链表中前一个节点的指针，可为 null（虚拟头节点的 prev 为 null）。
            /// </summary>
            public CacheNode? prev;

            /// <summary>
            /// 指向双向链表中后一个节点的指针，可为 null（虚拟尾节点的 next 为 null）。
            /// </summary>
            public CacheNode? next;

            /// <summary>
            /// 无参构造函数，用于初始化虚拟头尾节点。
            /// </summary>
            public CacheNode()
            {
            }

            /// <summary>
            /// 带参构造函数，用于初始化存储实际缓存条目的节点。
            /// </summary>
            /// <param name="key">缓存条目的关键字。</param>
            /// <param name="value">缓存条目的值。</param>
            public CacheNode(int key, int value)
            {
                this.key = key;
                this.value = value;
            }
        }

        /// <summary>
        /// 哈希表，用于建立 key 到双向链表节点的映射，实现 O(1) 时间复杂度的节点定位。
        /// </summary>
        /// <remarks>
        /// 哈希表的键为缓存的 key，值为对应的 CacheNode 节点。
        /// 初始化时按容量预分配空间，减少后续扩容和 rehash 的开销。
        /// </remarks>
        private readonly Dictionary<int, CacheNode> cacheDict;

        /// <summary>
        /// 双向链表的虚拟头节点（哨兵节点），用于简化链表的边界处理。
        /// </summary>
        /// <remarks>
        /// 虚拟头节点不存储实际的缓存数据，其 next 指针始终指向链表中“最近使用”的节点。
        /// 链表不变量：head <-> (most recent) ... (least recent) <-> tail。
        /// </remarks>
        private readonly CacheNode head;

        /// <summary>
        /// 双向链表的虚拟尾节点（哨兵节点），用于简化链表的边界处理。
        /// </summary>
        /// <remarks>
        /// 虚拟尾节点不存储实际的缓存数据，其 prev 指针始终指向链表中“最久未使用”的节点。
        /// 当缓存容量超限时，需要删除 tail.prev 指向的节点。
        /// </remarks>
        private readonly CacheNode tail;

        /// <summary>
        /// 缓存的最大容量，即最多可存储的缓存条目数量。
        /// </summary>
        /// <remarks>
        /// 容量必须为正整数，初始化时会进行参数校验。
        /// 当缓存条目数量超过 capacity 时，会自动逐出最久未使用的条目。
        /// </remarks>
        private readonly int capacity;

        /// <summary>
        /// 初始化 LRU 缓存，指定最大容量。
        /// </summary>
        /// <param name="capacity">缓存的最大容量，必须为正整数。</param>
        /// <exception cref="ArgumentOutOfRangeException">当 capacity 小于等于 0 时抛出。</exception>
        /// <remarks>
        /// 初始化操作包括：
        /// 1. 校验 capacity 的合法性；
        /// 2. 按容量预分配哈希表空间；
        /// 3. 初始化双向链表的虚拟头尾节点，并建立 head <-> tail 的连接。
        /// </remarks>
        public LRUCache(int capacity)
        {
            if (capacity <= 0)
            {
                throw new ArgumentOutOfRangeException(nameof(capacity), "capacity must be positive.");
            }

            this.capacity = capacity;

            // 按容量预分配哈希表，减少后续扩容/rehash
            cacheDict = new Dictionary<int, CacheNode>(capacity);

            // 初始化双向链表的虚拟头尾节点
            head = new CacheNode();
            tail = new CacheNode();
            head.next = tail;
            tail.prev = head;
        }

        /// <summary>
        /// 根据关键字 key 获取缓存中的值。
        /// </summary>
        /// <param name="key">要查找的缓存关键字。</param>
        /// <returns>如果 key 存在于缓存中，返回对应的值；否则返回 -1。</returns>
        /// <remarks>
        /// 当 key 命中缓存时，会将对应的节点移动到双向链表的头部，标记为“最近使用”。
        /// 此操作的平均时间复杂度为 O(1)。
        /// </remarks>
        public int Get(int key)
        {
            // 哈希表中查找 key，不存在则直接返回 -1
            if (!cacheDict.TryGetValue(key, out CacheNode? node))
            {
                return -1;
            }

            // 命中缓存：将节点移动到链表头部，标记为“最近使用”
            MoveToHead(node!);

            // 返回缓存的值
            return node!.value;
        }

        /// <summary>
        /// 向缓存中插入或更新键值对 (key, value)。
        /// </summary>
        /// <param name="key">要插入或更新的缓存关键字。</param>
        /// <param name="value">要插入或更新的缓存值。</param>
        /// <remarks>
        /// 操作逻辑：
        /// 1. 如果 key 已存在：更新对应的值，并将节点移动到头部（标记为最近使用）；
        /// 2. 如果 key 不存在：创建新节点，添加到头部和哈希表；
        /// 3. 如果插入后缓存数量超过 capacity：删除链表尾部节点（最久未使用），并从哈希表中移除对应 key。
        /// 此操作的平均时间复杂度为 O(1)。
        /// </remarks>
        public void Put(int key, int value)
        {
            if (cacheDict.TryGetValue(key, out CacheNode? node))
            {
                // key 已存在：更新值，并移动到头部
                node!.value = value;
                MoveToHead(node!);
                return;
            }

            // key 不存在：创建新节点，添加到头部和哈希表
            CacheNode newNode = new CacheNode(key, value);
            cacheDict.Add(key, newNode);
            AddToHead(newNode);

            // 超过容量：逐出尾部节点（最久未使用）
            if (cacheDict.Count > capacity)
            {
                CacheNode tailNode = RemoveTail();
                cacheDict.Remove(tailNode.key);
            }
        }

        /// <summary>
        /// 将指定节点添加到双向链表的头部（虚拟头节点的后面）。
        /// </summary>
        /// <param name="node">要添加到头部的 CacheNode 节点。</param>
        /// <remarks>
        /// 添加后，该节点会成为链表中“最近使用”的节点。
        /// 操作会调整节点的 prev/next 指针，以及虚拟头节点和原头部节点的指针。
        /// 此操作的时间复杂度为 O(1)。
        /// </remarks>
        private void AddToHead(CacheNode node)
        {
            // 新节点的 prev 指向虚拟头，next 指向原头部节点
            node.prev = head;
            node.next = head.next;
            // 原头部节点的 prev 指向新节点
            head.next!.prev = node;
            // 虚拟头的 next 指向新节点
            head.next = node;
        }

        /// <summary>
        /// 从双向链表中移除指定节点（不修改哈希表）。
        /// </summary>
        /// <param name="node">要从链表中移除的 CacheNode 节点。</param>
        /// <remarks>
        /// 此操作仅调整链表中前后节点的 prev/next 指针，不会修改哈希表。
        /// 移除后会断开该节点自身的 prev/next 引用，避免误用并利于 GC 回收。
        /// 此操作的时间复杂度为 O(1)。
        /// </remarks>
        private void RemoveNode(CacheNode node)
        {
            // 前一个节点的 next 指向后一个节点
            node.prev!.next = node.next;
            // 后一个节点的 prev 指向前一个节点
            node.next!.prev = node.prev;
            // 断开节点自身的引用，避免误用，利于 GC 回收
            node.prev = null;
            node.next = null;
        }

        /// <summary>
        /// 将已存在的节点移动到双向链表的头部。
        /// </summary>
        /// <param name="node">要移动到头部的 CacheNode 节点。</param>
        /// <remarks>
        /// 操作逻辑：
        /// 1. 如果节点已经在头部（prev 为虚拟头），则无需操作；
        /// 2. 否则，先从原位置移除节点，再添加到头部。
        /// 此操作用于标记节点为“最近使用”，时间复杂度为 O(1)。
        /// </remarks>
        private void MoveToHead(CacheNode node)
        {
            // 已经在头部（虚拟头的后面），无需操作
            if (node.prev == head)
            {
                return;
            }

            // 先从原位置移除，再添加到头部
            RemoveNode(node);
            AddToHead(node);
        }

        /// <summary>
        /// 移除双向链表尾部的节点（虚拟尾节点的前面，即最久未使用的节点）。
        /// </summary>
        /// <returns>被移除的尾部 CacheNode 节点。</returns>
        /// <remarks>
        /// 此操作用于缓存容量超限时逐出“最久未使用”的条目。
        /// 返回的节点包含 key，用于从哈希表中移除对应的条目。
        /// 此操作的时间复杂度为 O(1)。
        /// </remarks>
        private CacheNode RemoveTail()
        {
            // 尾部节点是虚拟尾的 prev
            CacheNode tailNode = tail.prev!;
            // 从链表中移除尾部节点
            RemoveNode(tailNode);
            // 返回被移除的节点（用于获取 key 删哈希表）
            return tailNode;
        }
    }

    #endregion
}

146.4 运行结果

=== 示例测试 ===
get(1) = 1
get(2) = -1
get(1) = -1
get(3) = 3
get(4) = 4

=== 边界测试 ===
容量1测试 - get(1) = 1
容量1测试 - get(1) = -1
容量1测试 - get(2) = 2

=== 更新值测试 ===
更新值测试 - get(1) = 10
更新值测试 - get(2) = 2
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 785293209@qq.com

赏

©2016-2026 Tao

Built with Hexo and 3-hexo theme

×

喜欢就点赞,疼爱就打赏