罗湖网站建设费用,京东的网站建设分析,金融适合什么颜色做网站,外国游戏概念设计网站运用你所掌握的数据结构#xff0c;设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作#xff1a; 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中#xff0c;则获取密钥的值#xff08;总是正数#xff09;#xff…运用你所掌握的数据结构设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作 获取数据 get 和 写入数据 put 。 获取数据 get(key) - 如果密钥 (key) 存在于缓存中则获取密钥的值总是正数否则返回 -1。写入数据 put(key, value) - 如果密钥不存在则写入其数据值。当缓存容量达到上限时它应该在写入新数据之前删除最近最少使用的数据值从而为新的数据值留出空间。 进阶: 你是否可以在 O(1) 时间复杂度内完成这两种操作 示例: LRUCache cache new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4参考博客http://www.cnblogs.com/grandyang/p/4587511.html解答通过构建一个list表内容为pairint,int即键-值对用于存放当前的缓存值。同时构建一个Hash表unordered_mapint, listpairint,int::iterator m 用于存放key-list内容目的是用于快速查询键值对。get函数查询哈希表中是否有输入的key值没有则返回 -1 否则返回相应的值并用list.splice更新当前键值对在list最前处。put函数如果存在键值对那么则在list中删除该键值对。将新输入的键值对放在list的最前处并同时更新Hash表中的键值对。如果容量已经超过最大值那么将最不常用的键值对位于list最后处弹出。同时删除Hash表中的键值对。 函数说明【1】unordered_mapint, listpairint,int::iterator m; auto itm.find(key); 相当于 listpairint,int::iterator it;【2】it-second 表示取到了pairint,int【3】l.splice(l.begin(),l, it-second); 表示将pairint,int放置在list的最前端其余顺序不变。 class LRUCache {
public:LRUCache(int capacity) {this-capacitycapacity; }int get(int key) {// listpairint,int::iterator it;auto itm.find(key);if(itm.end()) return -1;l.splice(l.begin(),l, it-second);return it-second-second;}void put(int key, int value) {// listpairint,int::iterator it;auto it m.find(key);if (it ! m.end()) l.erase(it-second);l.push_front(make_pair(key, value));m[key] l.begin();if ((int)m.size() capacity) {int k l.rbegin()-first;l.pop_back();m.erase(k);}}private:int capacity;listpairint,int l;unordered_mapint, listpairint,int::iterator m;
};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj new LRUCache(capacity);* int param_1 obj-get(key);* obj-put(key,value);*/ 转载于:https://www.cnblogs.com/2Bthebest1/p/10853521.html
