找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1898|回复: 1
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【LRU Cache 】【刷题第一弹2014】

[复制链接]

11

主题

10

精华

641

积分

超级会员

Rank: 4

积分
641
发表于 10-24-2014 08:49 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 MengMa 于 12-7-2014 12:10 AM 编辑

leetcode: https://oj.leetcode.com/problems/lru-cache/
汇总帖:http://www.meetqun.com/forum.php?mod=viewthread&tid=703
1. 题目:

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.

2. 分析
考察对基本数据结构哈希表、链表的掌握,
为了使查找、插入和删除都有较高的性能,首先定义一个CacheNode节点存储key和value,使用一个双向链表 (std::list) 和一个哈希表操作
(std::unordered_map),因为:
• 哈希表保存每个节点的地址,可以基本保证在 O(1) 时间内查找节点
• 双向链表插入和删除效率高,单向链表插入和删除时,还要查找节点的前驱节点
具体实现细节:
• 越靠近链表头部,表示节点上次访问距离现在时间最短,尾部的节点表示最近访问最少
• 访问节点时,如果节点存在,把该节点交换到链表头部,同时更新 hash 表中该节点的地址
• 插入节点时,如果 cache 的 size 达到了上限 capacity,则删除尾部节点,同时要在 hash 表中删
除对应的项;新节点插入链表头部
3. 复杂度
get()采样哈希表查找,时间复杂度O(1),set()采用双向链表,删除插入时间复杂度O(n),空间复杂度O(n)
4. 代码
  1. class LRUCache{
  2. public:
  3.     LRUCache(int capacity) {
  4.         this->capacity = capacity;
  5.     }
  6.     int get(int key){
  7.         if(cache_map.find(key) == cache_map.end()) return -1;
  8.         //移动当前访问节点到双向链表头部
  9.         cache_list.splice(cache_list.begin(), cache_list, cache_map[key]);
  10.         cache_map[key] = cache_list.begin();
  11.         return cache_map[key]->value;
  12.     }
  13.     void set(int key, int value){
  14.         if(cache_map.find(key) != cache_map.end()){
  15.             cache_map[key]->value = value;
  16.             cache_list.splice(cache_list.begin(), cache_list, cache_map[key]);
  17.             cache_map[key] = cache_list.begin();            
  18.         }
  19.         else{
  20.             if(cache_list.size() >= capacity){
  21.                 cache_map.erase(cache_list.back().key);
  22.                 cache_list.pop_back();
  23.             }
  24.             cache_list.push_front(CacheNode(key, value));
  25.             cache_map[key] = cache_list.begin();
  26.         }
  27.     }
  28. private:
  29.     struct CacheNode{
  30.         int key;
  31.         int value;
  32.         CacheNode(int k, int v):key(k), value(v){}
  33.     };
  34.    
  35.     list<CacheNode> cache_list;
  36.     unordered_map<int, list<CacheNode>::iterator>  cache_map;
  37.     int capacity;
  38. };
复制代码

【i】【i】【i】【i】5. 相关题目:


本帖被以下淘专辑推荐:

37

主题

2

精华

240

积分

高级会员

Rank: 3Rank: 3

积分
240
发表于 2-3-2015 02:14 PM | 显示全部楼层
这个题set()方法复杂度也是O(n)吧?因为有hashmap可以直接到达所需要的Node点,然后如果存在,插入到队尾,也可直接到达。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表