力扣算法题—460LFU缓存-白红宇

力扣算法题—460LFU缓存

阅读量：4541 次

发布时间：2019-06-08

本文共 5542 字，大约阅读时间需要 18 分钟。

【题目描述】

设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。

get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。

put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。

进阶：

你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /*capacity (缓存容量) */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get(1); // 返回 1

cache.put(3, 3); // 去除 key 2

cache.get(2); // 返回 -1 (未找到key 2)

cache.get(3); // 返回 3

cache.put(4, 4); // 去除 key 1

cache.get(1); // 返回 -1 (未找到 key 1)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

【解题思路】

解题思路见我博客：

【代码实现】

1 #pragma once  2 #include 
     
        3 #include 
        4   5 using namespace std;  6   7 class LFUCache {  8 public:  9     LFUCache(int capacity) { 10         this->capacity = capacity; 11     } 12  13     int get(int key) { 14         if (dataMap.find(key) == dataMap.end())//数据不存在 15             return -1; 16         Node* p = dataMap[key];//找到数据节点 17         NodeList* h = headMap[p->num]; 18         updataNode(p, h); 19  20         return p->val; 21     } 22  23     void put(int key, int value) { 24         if (capacity == 0) 25             return; 26         if (dataMap.find(key) != dataMap.end())//已经存在 27         { 28             Node* p = dataMap[key];//找到数据节点 29             NodeList* h = headMap[p->num];//找到头链表节点         30             p->val = value; 31  32             updataNode(p, h);//更新数据的使用次数         33         } 34         else//如果不存在，则新建 35         { 36             if (dataMap.size() >= this->capacity)//容量不足，需要删除数据 37                 deleteData(); 38  39             Node* p = new Node(key, value, 1);//使用用一次 40             dataMap[key] = p;//记录 41  42             //将新建节点插入使用1次的子链表中 43             if (headMap.find(1) == headMap.end())//当使用1次的子链表不存在 44                 createNode(p, headList); 45             else 46                 moveNode(p, headMap[1]);//插入在使用次数在1的子链表中 47         } 48     } 49  50 private: 51     struct Node//子链表 52     { 53         int key; 54         int val; 55         int num; 56         Node* next; 57         Node* pre; 58         Node(int a, int b, int n) :key(a), val(b), num(n), next(nullptr), pre(nullptr) {} 59     }; 60  61     struct NodeList//主链表 62     { 63         int num; 64         Node* head;//子链表的头节点 65         Node* tail;//子链表的尾结点 66         NodeList* next; 67         NodeList* pre; 68         NodeList(int a) :num(a), next(nullptr), pre(nullptr) 69         { 70             head = new Node(0, 0, a);//新建一个子链表的头结点 71             tail = head; 72         } 73     }; 74  75 private: 76     void getNode(Node*& p, NodeList*& h)//将节点从子链表中取出 77     { 78         p->pre->next = p->next; 79         if (p->next == nullptr) 80             h->tail = p->pre; 81         else 82             p->next->pre = p->pre; 83     } 84     void moveNode(Node*& p, NodeList*& q)//将节点向后移动 85     { 86         p->next = q->tail->next; 87         q->tail->next = p; 88         p->pre = q->tail; 89         q->tail = p; 90     } 91     void deleteNode(int num, NodeList*& h)//删除子链表 92     { 93         headMap.erase(num);//从map中删除 94         h->pre->next = h->next; 95         if (h->next != nullptr) 96             h->next->pre = h->pre; 97         delete h; 98         h = nullptr; 99     }100     void createNode(Node*p, NodeList*& h)//新建子链表,并插入在主链中101     {102         NodeList* q = new NodeList(p->num);//新建一个子链表103         headMap[p->num] = q;//保存对应的地址104 105         moveNode(p, q);////将节点放入子链表中        106 107         //将新子链插入主链表中108         q->next = h->next;109         if (h->next != nullptr)110             h->next->pre = q;111         h->next = q;112         q->pre = h;113     }114     void updataNode(Node*& p, NodeList*& h)//更新函数的使用次数115     {116         int num = p->num;117         p->num++;//使用次数+1118 119         //将p从子链表中取出120         getNode(p, h);121 122         //将该数据向后面移动123         if (headMap.find(p->num) == headMap.end())//不存在num+1的节点,那么新建124             createNode(p, h);125         else126             moveNode(p, headMap[p->num]);////将节点放入子链表中    127 128         //如果该子链表为空，将该子链表删除,并从map中删除129         if (h->head == h->tail)130             deleteNode(num, h);131     }132     void deleteData()//容量不足需要删除133     {134         NodeList* p = headList->next;135         Node* q = p->head->next;//删除子链表排在最前面的数据136         if (q == p->tail)//要删除的数据就是最后一个数据，则删除该节点和子链表137             deleteNode(q->num, p);138         else139         {140             p->head->next = q->next;141             q->next->pre = p->head;142         }143         dataMap.erase(q->key);//删除记录144         delete q;//删除145         q = nullptr;146     }147 148 private:149     int capacity;150     NodeList* headList = new NodeList(0);//主链表的头结点151     map
       
        dataMap;//key  <——>  真实数据节点地址152     map
        
         headMap;//次数 <——>  链表头节点地址153 };154 155 /**156  * Your LFUCache object will be instantiated and called as such:157  * LFUCache* obj = new LFUCache(capacity);158  * int param_1 = obj->get(key);159  * obj->put(key,value);160  */161 162 void Test()163 {164     LFUCache* f = new LFUCache(3);165     f->put(1, 1);166     f->put(2, 2);167     f->put(3, 3);168     f->put(4, 4);169     cout << f->get(4) << endl;170     cout << f->get(3) << endl;171     cout << f->get(2) << endl;172     cout << f->get(1) << endl;173     f->put(5, 5);174     cout << f->get(1) << endl;175     cout << f->get(2) << endl;176     cout << f->get(3) << endl;177     cout << f->get(4) << endl;178     cout << f->get(5) << endl;179 180 181 }

转载于:https://www.cnblogs.com/zzw1024/p/11080799.html

你可能感兴趣的文章