LeetCode LRU缓存

2024-06-08 10:52
文章标签 leetcode 缓存 lru

本文主要是介绍LeetCode LRU缓存,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

请你设计并实现一个满足  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.get查询功能,put删除功能(如果容器内的数达到容量 capacity,则删除最久未用的那个变量),需要注意的是,这里的最久未被被查询是怎么定义的?就像

  

原本指南针这个应用是再队列的最后一位,当我打开他一次后,他就跑到前面了,另外假设容器的容量为4,我再打开一个新的应用,那么,在最后一位的计算器就要被关掉。

普通的队列可以根据元素被压入的时间进行排序,但不能访问队列中间的元素,也不能提出,哈希表可以实现查询功能,但不能实现按照元素被访问时间进行排序,如果我们把他们结合起来,组成哈希链表,既有了哈希表的查询功能,也有了链表的先后顺序功能。这里采用的是双向链表

代码如下,逻辑比较简单,主要是函数的调用。

struct DLinkedNode {//双向链表的节点int key, value;//两个存变量的int变量DLinkedNode* prev;//指向上个节点DLinkedNode* next;//指向下个节点DLinkedNode() :key(0), value(0), prev(nullptr), next(nullptr){}//初始化节点的函数DLinkedNode(int _key,int _value):key(_key),value(_value),prev(nullptr),next(nullptr){}
};
class LRUCache {
private://这个是声明变量再class外面和内部都可访问unordered_map<int, DLinkedNode*>cache;//DLinkedNode* head;//创建头节点DLinkedNode* tail;//创建尾节点int size;//统计链表内有多少个节点int capacity;//容器容量/*public: 是一个访问说明符(access specifier),它用于指定类的成员(成员变量或成员函数)在类外部是否可见和可访问。public 成员可以从任何地方被访问,包括类的外部和其他文件中的代码。*/
public:LRUCache(int _capacity) : capacity(_capacity), size(0) {//这一步是为两个变量赋值head = new DLinkedNode();//创建两个空节点tail = new DLinkedNode();head->next = tail;tail->prev = head;};int get(int key) {if (!cache.count(key))//看看这个变量在不在队列当中{return -1;}//如果在队列当中。将他提到队列头部DLinkedNode* node = cache[key];moveToHead(node);return node->value;}void put(int key, int value) {if (!cache.count(key)){//如果不存在,创建一个新节点,压入哈希表DLinkedNode* node = new DLinkedNode(key, value);cache[key] = node;// 添加至双向链表的头部addToHead(node);//++size;if (size > capacity){DLinkedNode* removed = removeTail();//删除尾部节点// 删除哈希表中对应的项cache.erase(removed->key);//使用 erase 方法来删除 map 中的单个元素// 防止内存泄漏delete removed;--size;}}else {//如果存在,先定位节点的位置DLinkedNode* node = cache[key];node->value = value;//更改值addToHead(node);//将其移动到前面}}void addToHead(DLinkedNode* node)//将节点指向头节点{node->prev = head;//指向头结点node->next = head->next;//node节点指向未插入之前头节点的下一个节点head->next -> prev = node;//调整未插入之前头结点的下一个节点,指向nodehead->next = node;}void removeNode(DLinkedNode* node) {//这个函数用于从双向链表中移除一个节点node->prev->next = node->next;//前一个结点的next指向下一个节点node->next->prev = node->prev;//后一个节点的perv}void moveToHead(DLinkedNode* Node) {//将一个节点移动到头部removeNode(Node);//删除这个节点addToHead(Node);//将这个节点移动到头节点}DLinkedNode* removeTail() {//这个函数的作用是移除链表尾部的节点并返回他的值DLinkedNode* node = tail->prev;removeNode(node);return node;}};

这篇关于LeetCode LRU缓存的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1041983

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

缓存雪崩问题

缓存雪崩是缓存中大量key失效后当高并发到来时导致大量请求到数据库,瞬间耗尽数据库资源,导致数据库无法使用。 解决方案: 1、使用锁进行控制 2、对同一类型信息的key设置不同的过期时间 3、缓存预热 1. 什么是缓存雪崩 缓存雪崩是指在短时间内,大量缓存数据同时失效,导致所有请求直接涌向数据库,瞬间增加数据库的负载压力,可能导致数据库性能下降甚至崩溃。这种情况往往发生在缓存中大量 k

leetcode-24Swap Nodes in Pairs

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode swapPairs(L

leetcode-23Merge k Sorted Lists

带头结点。 /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode(int x) { val = x; }* }*/public class Solution {public ListNode mergeKLists

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟)

【每日一题】LeetCode 2181.合并零之间的节点(链表、模拟) 题目描述 给定一个链表,链表中的每个节点代表一个整数。链表中的整数由 0 分隔开,表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点,新节点的值为原区间内所有节点值的和。合并后,需要移除所有的 0,并返回修改后的链表头节点。 思路分析 初始化:创建一个虚拟头节点

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

【JavaScript】LeetCode:16-20

文章目录 16 无重复字符的最长字串17 找到字符串中所有字母异位词18 和为K的子数组19 滑动窗口最大值20 最小覆盖字串 16 无重复字符的最长字串 滑动窗口 + 哈希表这里用哈希集合Set()实现。左指针i,右指针j,从头遍历数组,若j指针指向的元素不在set中,则加入该元素,否则更新结果res,删除集合中i指针指向的元素,进入下一轮循环。 /*** @param

Redis中使用布隆过滤器解决缓存穿透问题

一、缓存穿透(失效)问题 缓存穿透是指查询一个一定不存在的数据,由于缓存中没有命中,会去数据库中查询,而数据库中也没有该数据,并且每次查询都不会命中缓存,从而每次请求都直接打到了数据库上,这会给数据库带来巨大压力。 二、布隆过滤器原理 布隆过滤器(Bloom Filter)是一种空间效率很高的随机数据结构,它利用多个不同的哈希函数将一个元素映射到一个位数组中的多个位置,并将这些位置的值置

LeetCode:64. 最大正方形 动态规划 时间复杂度O(nm)

64. 最大正方形 题目链接 题目描述 给定一个由 0 和 1 组成的二维矩阵,找出只包含 1 的最大正方形,并返回其面积。 示例1: 输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 示例2: 输入: 0 1 1 0 01 1 1 1 11 1 1 1 11 1 1 1 1输出: 9 解题思路 这道题的思路是使用动态规划