当前位置： 首页 > article >正文

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

article 2024/10/27 17:20:23

一、算法题描述

1.1 算法描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

  1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
  3. 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)O(1)O(1) 时间复杂度内完成。

2.1 解题思路

  1. 使用 HashMap：将 key 映射到对应的节点，这样可以在 O(1)O(1)O(1) 时间内查找元素。
  2. 使用双向链表：保存缓存的顺序，最久未使用的元素在链表的尾部，最近使用的在头部。
    • 每次访问 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 的 next
        node.prev = head; // 新节点的 prev 指向 head
        head.next.prev = node; // 将 head 原来的 next 的 prev 指向新节点
        head.next = node; // head 的 next 指向新节点
    }

    // 辅助方法：从链表中移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next; // 将 node 的前节点的 next 指向 node 的 next
        node.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 和双向链表中的节点。

代码详解

  1. Node 类：

    • Node 是双向链表的节点类，包含 key 和 value，以及 prev 和 next 指针用于双向链接。

  2. 构造方法 Solution(int capacity)：

    • 初始化 capacity 和 map，并创建链表的 head 和 tail 哨兵节点。
    • 通过将 head.next 指向 tail，tail.prev 指向 head，形成一个空的双向链表（仅有哨兵节点）。

  3. 方法 get(int key)：

    • 检查 key 是否在 map 中。
    • 如果在，则通过 moveToHead(node) 将对应节点移到链表头部，以标记该节点为最近使用。
    • 返回节点的 value。
    • 如果 key 不在 map 中，则返回 -1。

  4. 方法 set(int key, int value)：

    • 检查 key 是否在 map 中。
      • 如果 key 已存在，更新其 value，并调用 moveToHead(node) 将节点移到链表头部。
      • 如果 key 不存在，创建新节点，并插入到链表头部。
      • 检查 map 的大小是否超过 capacity，若超过则调用 removeTail() 删除链表尾部节点，并从 map 中移除对应键。

  5. 辅助方法：

    • addNode(Node node)：将新节点插入到链表头部，链表更新顺序为 head <-> node <-> head.next。
    • removeNode(Node node)：从链表中删除指定节点。
    • moveToHead(Node node)：将节点先删除，再插入链表头部，更新为最近使用。
    • removeTail()：删除链表尾部节点（最久未使用节点），并返回该节点。

关键点总结

  • HashMap 作为缓存记录的快速查找结构，使得 get 和 set 操作在 O(1) 时间完成。
  • 双向链表 维护 LRU 顺序，头部表示最近使用，尾部表示最久未使用。
  • 容量管理：当超出容量时，通过 removeTail() 删除尾节点（最久未使用），并从 map 中移除。

http://www.kler.cn/news/367548.html

相关文章：

  • python构建flask服务用于视频文件的处理后返回
  • PG数据库之事务处理
  • 从蚂蚁金服面试题窥探STW机制
  • 改进YOLOv8系列：引入低照度图像增强网络Retinexformer | 优化低光照目标检测那题
  • 算法与竞赛(第15章) - 矩阵高级运算
  • css 切角实现（全）
  • static 关键字的用法
  • 【Java】LinkedList实现类的使用
  • 苹果预告下周发布Mac新品：全系标配M4系列芯片
  • 前端处理API接口故障：多接口自动切换的实现方案
  • bluez hid host介绍，连接键盘/鼠标/手柄不是梦，安排
  • 日常实习与暑期实习详解
  • java使用正则表达式校验字符串pwd,是否符合包含大写小写数字特殊字符长度超过8位
  • Codeforces Round 981 (Div. 3) A - E 详细题解(C++)
  • maven分模块设计与私服
  • 如何用mmclassification训练多标签多分类数据
  • 如何理解前端与后端开发
  • entwine 和 conda环境下 使用和踩坑 详细步骤! 已解决
  • uptime kuma拨测系统
  • 身份证归属地查询接口-在线身份证归属地查询-身份证归属地查询API
  • 论文略读：Less is More: on the Over-Globalizing Problem in Graph Transformers
  • 2FA-双因素认证
  • 基于Python的智能求职分析系统
  • python 使用 企微机器人发送消息
  • 安全日志记录的重要性
  • 今天不分享技术，分享秋天的故事