Leetcode 146 LRU Cache 模拟操作系统LRU

科研学习压力比较大,最近更新的不多,有时间尽量多做一点吧!上来就是一个大模拟。

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

模拟实现一个LRU,LRU是操作系统里的一个算法,当存储空间满的时候,需要换掉使用时间离现在最远的数据。

分析:有一个内存容量 size,通过构造函数赋予大小

get操作,获取指定键的值,没有则返回-1,如果获取成功相当于成功访问了数据,需要将它提到最前面。

get不会改变数据的多少,所以不会出现超过容量size的情况。

set操作分三种情况:1.找到key,那么修改value值,将它提到前面就行了。

2. 没有找到key,当前容量未满,创建key-value对,把它放在最前面。

3. 没有找到key,当前容量已满,创建key-value对,把它放在最前面,把最后面的移除。

代码如下,详见注释:

class LRUCache{
public:
    LRUCache(int capacity) //初始化容量
    {
        size = capacity;
    }
    
    int get(int key) 
    {
        if(mp.find(key) != mp.end()) //get到了
        {
            node* p = mp[key];
            node* q = mp[key]->next;
            p->next = q->next;
            if(q->next) 
                mp[q->next->k] = p;
            else
                tail = p;
            q->next = head->next;
            if(head->next) 
                mp[head->next->k] = q;
            else
                tail = q;
            head->next = q;
            mp[q->k] = head;
            return mp[key]->next->val;
        }
        return -1; //没有get到
    }
    
    void set(int key, int value) 
    {
        if(mp.find(key) != mp.end()) //有这个key
        {
            node* p = mp[key];
            node* q = mp[key]->next;
            p->next = q->next;
            if(q->next) 
                mp[q->next->k] = p;
            else
                tail = p;
            q->next = head->next;
            if(head->next) 
                mp[head->next->k] = q;
            else
                tail = q;
            head->next = q;
            mp[q->k] = head;
            q->val = value;
            return ;
        }
        if(now < size) //没有key,但是还有容量
        {
            now++;
            node* p = new node(key, value);
            mp[key] = head;
            if(head->next) mp[head->next->k] = p;
            
            p->next = head->next; 
            head->next = p;
            if(!p->next) tail = p;
            return ;
        }
        if(tail) //没有key,但没有容量了,有tail说明容量不为0,可以装入新键值对
        {
            node* p = new node(key, value);
            mp[key] = head;
            if(head->next) mp[head->next->k] = p;
            p->next = head->next; 
            head->next = p;
            tail = mp[tail->k];
            mp.erase(tail->next->k);
            delete tail->next;
            tail->next = NULL;
        }
    }
    
private:
    struct node 
    {
        int k,val;
        node* next;
        node(int a, int b)
        {
            k = a;
            val = b;
            next = NULL;
        }
    };
    node* head = new node(-1, -1);
    node* tail;
    int size, now = 0; //最大容量和当前容量
    unordered_map<int, node*> mp; //键对应的链表节点的前驱
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏不会写文章的程序员不是好厨师

伪共享(False Sharing)和缓存行(Cache Line) 大杂烩

在上篇介绍LongAdder的文章中,我们最后留下了一个问题,为什么Cell中要插入很多个实际上并没有使用的Long变量?这个问题就得从False Sharin...

1281
来自专栏H2Cloud

C++ FFLIB 之FFDB: 使用 Mysql&Sqlite 实现CRUD

摘要: C++ 操作DB真心不是太省心的事,一方面C++操作DB的接口大部分都使用C API,如Mysql、Sqlite 提供的API。尽管其C API文档已经...

3445
来自专栏Python攻城狮

十一假期即将结束 不如复习下Python基础

博客地址:https://ask.hellobi.com/blog/zhiji 欢迎大家来交流学习。

781
来自专栏JetpropelledSnake

Django学习笔记之Queryset的高效使用

对象关系映射 (ORM) 使得与SQL数据库交互更为简单,不过也被认为效率不高,比原始的SQL要慢。

1253
来自专栏漏斗社区

代码审计|禅道7.3SQL注入复现

上周的zentaopms漏洞复现你们觉得还OK吗? 斗哥想要的是一个肯定。 如果你们觉得意犹未尽, 本期将进入, 代码审计的小练习。 Zentaopms v7....

3876
来自专栏北京马哥教育

Redis 基础、高级特性与性能调优 | 一文看全

本文将从Redis的基本特性入手,通过讲述Redis的数据结构和主要命令对Redis的基本能力进行直观介绍。之后在性能调优等方面进行更深入的介绍和指导。 概述...

7316
来自专栏MYSQL轻松学

MySQL大小写敏感总结

在MySQL中,数据库、表、triggers实际上都对应了datadir目录(或子目录)下的文件,因此,这些对象的名字是否大小写敏感主要是依赖于操作系统和文件系...

3474
来自专栏数据结构与算法

1777:文件结构“图”

1777:文件结构“图” 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 在计算机上看到文件系统的结构通常很有用。Micr...

36410
来自专栏程序员的知识天地

使用 JS 实现一个本地数据库

前端很多时候还是需要保存一些数据的,这里的保存指的是长久的保存。以前的思想是把数据保存在 Cookie 中,或者将 key 保存在 Cookie 中,将其他数据...

2952
来自专栏信安之路

PHP 代码审计之死磕 SQL 注入

代码审计中对 SQL 注入的审计是很常见的,那么要怎样才能审计出一个 SQL 注入呢?

1560

扫码关注云+社区