LRU Cache--leetcode

原题链接:https://oj.leetcode.com/problems/lru-cache/

题目大意:设计操作系统中资源管理算法所使用的一种数据结构,即LRU算法。是一道偏向于综合的题。

方法:一个哈希表+一个双端链表

思路:一方面LRU Cache算法要求可以快速访问结点,所以我们很容易想到使用哈希表或者数组。另一方面,该算法要求在达到容量上限时,删除最久未访问的数据结点。这要求所设计的数据结构必须满足快速插入和删除,显然数组达不到要求,链表恰恰有该效果。我们可以设计一种数据结构,同时具有哈希表的快速访问优势,又有链表的插入删除优势。即采用哈希表+双端链表的形式,设计其内部算法get和set。实现快速访问,我们可以通过哈希表来实现。快速插入删除,我们可以将每个key值对应在链表中的位置(迭代器)存入哈希表中,这样就可以快速找到key值所在的位置,然后删除。

复杂度分析:时间复杂度实现了O(1),空间上用到了一个hashtable和一个双端链表。属于空间换时间的典型。

struct Node  
{  
    int value;  
    list<int>::iterator iter;  
    Node(int value, list<int>::iterator iter)  
    {  
        this->value = value;  
        this->iter = iter;  
    }  
};  
class LRUCache{
public:
    LRUCache(int capacity) {
        this->capacity=capacity;
    }
    
    int get(int key) {
        if(0<mp.count(key))
        {
            moveToEnd(key);
            return mp[key]->value;
        }
        return -1;
    }
    
    void set(int key, int value) {
        if(0<mp.count(key)){
            mp[key]->value=value;
            moveToEnd(key);
        }
        else if(mp.size()<capacity)
        {
            l.push_back(key);
            mp[key]=new Node(value,--l.end());
        }
        else
        {
            int delKey=l.front();
            l.pop_front();
            mp.erase(delKey);
            l.push_back(key);
            mp[key]=new Node(value,--l.end());
        }
    }
    void moveToEnd(int key)
    {
        list<int>::iterator iter=mp[key]->iter;
        l.erase(iter);
        l.push_back(key);
        mp[key]->iter=--l.end();
    }
private:
    map<int,Node*> mp;
    list<int> l;
    int capacity;
};

这是一道很不错的综合题,不仅考虑编程,还涉及操作系统,资源管理等知识。一个同学在面阿里的时候就被问到了,看来这题还是很不错的。

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。