leetcode146 LRU Cache

朴灿烈づ我的快乐病毒、 2021-12-10 17:51 216阅读 0赞

**思路：**

使用unordered\_map和list实现O(1)的put和get。

**实现：**

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 
     4 class LRUCache
     5 {
     6 public:
     7     
     8     int c;
     9     list<int> l; // list of key
    10     unordered_map<int, pair<int, list<int>::iterator>> mp; // <key, <value, it>>
    11 
    12     LRUCache(int capacity) { c = capacity; }
    13     
    14     int get(int key)
    15     {
    16         if (!mp.count(key)) return -1;
    17         l.erase(mp[key].second);
    18         l.push_front(key);
    19         mp[key].second = l.begin();
    20         return mp[key].first;
    21     }
    22     
    23     void put(int key, int value)
    24     {
    25         if (mp.count(key))
    26         {
    27             l.erase(mp[key].second);
    28             mp.erase(key);
    29         }
    30         else if (l.size() == c)
    31         {
    32             mp.erase(l.back());
    33             l.pop_back();
    34         }
    35         l.push_front(key);
    36         mp[key] = make_pair(value, l.begin());
    37     }
    38 };
    39 
    40 int main()
    41 {
    42     LRUCache* obj = new LRUCache(2);
    43     obj->put(1, 1);
    44     obj->put(2, 2);
    45     cout << obj->get(1) << endl;
    46     obj->put(3, 3);
    47     cout << obj->get(2) << endl;
    48     obj->put(4, 4);
    49     cout << obj->get(1) << endl;
    50     cout << obj->get(3) << endl;
    51     cout << obj->get(4) << endl;
    52     return 0;
    53 }

转载于:https://www.cnblogs.com/wangyiming/p/11161490.html

发表评论取消回复

表情：

评论列表（有 0 条评论，216人围观）

还没有评论，来说两句吧...

相关阅读

相关 146. LRU Cache

Design and implement a data structure for [Least Recently Used (LRU) cache][Least Recent

Myth丶恋晨/ 2023年07月03日 07:26/ 0 赞/ 7 阅读

相关 Leetcode146--LRU Cache

题目分析对于LRU缓存淘汰算法，这里是基于链表实现的。对于get操作，如果不存在缓存中，直接返回-1,如果存在的话，当前我们又是在get他，那么我们就需要把当前的缓存节

ゝ一纸荒年。/ 2023年01月16日 11:19/ 0 赞/ 109 阅读

相关 LeetCode-146. LRU Cache

Problem: > Design and implement a data structure for Least Recently Used (LRU) cache.

逃离我推掉我的手/ 2022年07月28日 11:43/ 0 赞/ 131 阅读

相关 leetcode 146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should sup

本是古典何须时尚/ 2022年07月26日 06:30/ 0 赞/ 139 阅读

相关 LeetCode146—LRU Cache

原题 [原题链接][Link 1] > Design and implement a data structure for Least Recently Used (L

喜欢ヅ旅行/ 2022年07月15日 02:52/ 0 赞/ 182 阅读

相关 LeetCode-146.LRU缓存机制

题目运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。获取数据 get(k

女爷i/ 2022年04月25日 10:12/ 0 赞/ 198 阅读

相关 leetcode:146. LRU缓存机制

题目: 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。获取数据 get(

Myth丶恋晨/ 2022年03月14日 11:52/ 0 赞/ 194 阅读

相关 leetcode146 LRU Cache

思路：使用unordered\_map和list实现O(1)的put和get。实现： 1 include <bits/stdc++.h> 2 usi

朴灿烈づ我的快乐病毒、/ 2021年12月10日 17:51/ 0 赞/ 217 阅读

相关 [LeetCode] 146. LRU Cache_Hard tag: Hash, Linked List

Design and implement a data structure for [Least Recently Used (LRU) cache][Least Recent

﹏ヽ暗。殇╰゛Y/ 2021年11月16日 07:20/ 0 赞/ 205 阅读

相关 leetcode：146. LRU缓存机制

题目描述：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。获取数据 get(

「爱情、让人受尽委屈。」/ 2021年10月29日 07:38/ 0 赞/ 267 阅读