陈中正的网络日志

LeetCode: LRU Cache

题目

https://oj.leetcode.com/problems/lru-cache/

分析

这道题主要考察的是数据结构的设计能力。

首先考虑用hash_map来存储数据,这样get()可以达到O(1);不过hash_map没有淘汰LRU Cache的高效办法:一种方法是每个node存放一个最近使用的时间,每次set()时遍历时找出LRU node,这样set()是O(n)的时间复杂度,而且这样设计的话每次还要计算出哪个节点和现在的时间差值最大,实现起来特别麻烦。

之前面试的时候面试官提示可以用list实现:每次把最近用到的节点放到list最前面。但是当时觉得这种方法不太好,因为get()和set()的时间复杂度都是O(n),效率实在太低。

现在来看,应该是把hash_map和链表结合起来来用,使得get()和set()都能够达到O(1)的时间复杂度:每次用到的数据添加到list最前面,每次需要淘汰数据时,淘汰list的最后面的元素。同时用hash_map记录每个key在list中的位置,这样每次要根据key查询数据时,便到hash_map中查找数据。

代码

class LRUCache
{
public:
    LRUCache(int capacity)
    {
        capacity_ = capacity;
    }

    int get(int key)
    {
        if (cache_map_.find(key) == cache_map_.end())
            return -1;
        else
        {
            //delete old node and push a new node in front of list
            int temp = cache_map_[key]->second;
            cache_.erase(cache_map_[key]);
            cache_.push_front(pair<int, int>(key, temp));
            cache_map_[key] = cache_.begin();
            return temp;
        }
    }

    void set(int key, int value)
    {
        if (cache_map_.find(key) == cache_map_.end())
        {
            if (cache_.size() >= capacity_)
            {
                //delete the last node of list
                cache_map_.erase(cache_.back().first);
                cache_.pop_back();
            }
            //push new node in front of list
            cache_.push_front(pair<int, int>(key, value));
            cache_map_[key] = cache_.begin();
        }
        else
        {
            //delete old node and push a new node in front of  list
            cache_.erase(cache_map_[key]);
            cache_.push_front(pair<int, int>(key, value));
            cache_map_[key] = cache_.begin();
        }
    }

private:
    int capacity_;
    list<pair<int, int>> cache_;
    unordered_map<int, list<pair<int, int>>::iterator> cache_map_;
};

Note

在写代码的过程中,犯了很多2B的错误,导致花了很久才找出错误。

  1. 在更新list中的node时,忘记了同时更新map中的数据。

  2. 错误的把list.end()当做了list最后一个节点。 list.back()才是list最后一个节点。

参考

http://fisherlei.blogspot.com/2013/11/leetcode-lru-cache-solution.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40954059

Categories:  OJ题解 

« LeetCode: Restore IP Address LeetCode: Partition List »