首页 > 编程语言 >C++ LRU缓存

C++ LRU缓存

时间:2024-03-06 21:34:18浏览次数:35  
标签:node Node pre 缓存 int C++ next LRU key

题目:

//构建双向链表的节点结构(要有两个构造函数)
struct Node{
    int key, val;
    Node* pre;
    Node* next;
    Node():key(0), val(0), pre(nullptr), next(nullptr) {}
    Node(int _key, int _val): key(_key), val(_val), pre(nullptr), next(nullptr) {}
};

class LRUCache {
private:
    //哈希表存放key和节点的映射
    unordered_map<int, Node*> m;
    Node* head;
    Node* tail;
    int capacity, size;
public:
    //LRU构造函数中,设定capacity和size(当前容量)、创建伪头、尾节点并相连
    LRUCache(int _capacity) : capacity(_capacity), size(0){
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->pre = head;
    }
    
    //取值:如果表里没有这个key,返回-1;如果有,更新节点值,并将其移动至头部
    int get(int key) {
        if(!m.count(key)) return -1;
        Node* node = m[key];
        remove(node);
        add(node);
        return node->val;
    }
    
    //放值:如果表里找到,更新值并移动到头部;如果没找到,执行插入操作,插入前先判断是否溢出容量,是的话移除尾部节点,还要将其从表里删除,当前容量减一,然后将新节点加入头部、表、容量加一
    void put(int key, int value) {
        if(m.count(key)){
            Node* node = m[key];
            node->val = value;
            remove(node);
            add(node);
        }else{
            Node* node = new Node(key, value);
            if(size==capacity){
                Node* del = tail->pre;
                m.erase(del->key);
                remove(del);
                size--;
            }
            add(node);
            size++;
            m[key] = node;
        }
    }
    
    //删除节点
    void remove(Node* node){
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    
    //将节点移动至头结点
    void add(Node* node){
        node->next = head->next;
        node->pre = head;        
        head->next->pre = node;
        head->next = node;
    }

};

参考视频:LeetCode 每日一题146. LRU 缓存 | 手写图解版思路 + 代码讲解

标签:node,Node,pre,缓存,int,C++,next,LRU,key
From: https://www.cnblogs.com/fly-smart/p/18057645

相关文章

  • C++派生类构造函数
    实例#include<iostream>usingnamespacestd;classBase1{//基类Base1,构造函数有参数public:Base1(inti){cout<<"ConstructingBase1"<<i<<endl;}};classBase2{//基类Base2,构造函数有参数public:Base2(intj){cout<&l......
  • C++中的不规则二维数组
    技术背景最近刚学习C++的一些编程技巧,对于一些相对比较陌生的问题,只能采取一些简单粗暴的方案来实现。就比如说,我们可以在Python中定义一个[[0,0,0],[1,2],[1,1,1],[3]]这样的不规则的二维数组(list)。那么如果我们想在C++中实现一个类似的数据结构,应该怎么去设计呢?更具体一点的......
  • (持续更新)c++中的继承、封装、多态
    c++面向对象的三大特性为:继承、封装和多态c++认为万事万物都皆为对象,对象上有其属性和行为例如:人可以作为对象,属性有姓名、年龄、身高、体重…,行为有走、跑、跳、吃饭、唱歌⋯车也可以作为对象,属性有轮胎、方向盘、车灯…行为有载人、放音乐、放空调…具有相同性......
  • 【c++八股】手撕单例模式
    懒汉模式classSingleton{public:staticSingleton&Instance(){if(instance_==nullptr)instance_=newSingleton();}returninstance_;}private:Singleton(){}~Singleton(){} //防拷贝 Singleton(c......
  • C++的4种强制类型
    C++提供了4种强制类型转换的语法:静态转换(static_cast)static_cast是用于在没有二义性的前提下进行基本数据类型转换的一种转换方式。它只能用于具有相关性的数据类型之间的转换,如将int类型转换为double类型。如果进行无关的数据类型之间的转换,编译器将报错。用途:通常用......
  • C++ (3)
    3.函数1)函数声明中可以不写形参名而只写形参类型,这种函数声明成为函数原型。函数声明的位置可以在调用函数所在的函数中,也可以在函数之外。2)内置函数:编译时将所调用函数的代码直接嵌入到主调函数中,这种嵌入到主调函数中的函数称为内置函数(inlinefunction)。3)函数的重......
  • 店小密芒果店长商品搬家API接口PHP Java C++
    随着电子商务的迅猛发展,淘宝作为中国最大的电商平台之一,拥有着海量的商品数据和用户行为数据。为了更好地整合资源、提高运营效率,淘宝开放了商品详情API数据接口,为商家和第三方开发者提供了丰富的功能与应用。一、淘宝商品详情API数据接口概述淘宝商品详情API数据接口是淘宝开放......
  • C++ Qt开发:运用QThread多线程组件
    Qt是一个跨平台C++图形界面开发库,利用Qt可以快速开发跨平台窗体应用程序,在Qt中我们可以通过拖拽的方式将不同组件放到指定的位置,实现图形化开发极大的方便了开发效率,本章将重点介绍如何运用QThread组件实现多线程功能。多线程技术在程序开发中尤为常用,Qt框架中提供了QThread库来......
  • 01_C++基本数据类型_算数类型
    1.算数类型算数类型主要分为两类——整型和浮点型带符号和无符号类型带符号:int、short、long和longlong,通过在这些类型名前添加unsigned可以得到无符号类型。 选择符号的准则:(1)数值不可能为负时,选择无符号类型。(2)使用int执行整数运算。(3)算数表达式不要使用char或bool,存放字......
  • 【C++】判断一颗二叉树是否对称
    四步法:(1)如果两个子树都为空指针,则它们相等或对称(2)如果两个子树只有一个为空指针,则它们不相等或不对称(3)如果两个子树根节点的值不相等,则它们不相等或不对称(4)根据相等或对称要求,进行递归处理。//四步法判断一颗二叉树是否对称//主函数boolisSymmetric(TreeNode*root){......