首页 > 代码库 > LRU Cache

LRU Cache

    这个题敲了好久,比较纠结就是用链表加map实现,第一次是用单链表加一个指针标记,提交了几次总是出现runtime error。应该是内存访问出现了问题,原因在指针上,所以我就采用了双链表,修改了几个边界问题终于过了。需要考虑的边界有,catche容量为0,1的情况时head和tail的处理。链表存储的是所有catche中数据的键值,用来确定最近最少访问的顺序,map则存储键和值的对应关系。
    其实题目的算法不难,简单说下思路:
    (1)当增加一个键时,查看其是否存在,若存在,在map中则更新其值,并将链表中对应该键的节点移到链表尾,若不存在,则插入到链表尾。
    (2)如果空间超过catche大小,则删除链表头节点,并删除map中对应的值。
    (3)当访问一个键时,如果没有则直接返回-1,否则,将链表中对应的节点移到链表尾。
struct Node{   int key;   Node* next;   Node* pre;};class LRUCache{private:    Node *head,*tail;    int CatcheSize=0,capacity=0;    map<int,int> m1;public:    LRUCache(int capacity) {        this->capacity = capacity;        head = tail = 0;        CatcheSize = 0;    }    int get(int key) {        map<int,int>::iterator it;        it = m1.find(key);        if(it == m1.end())//如果没有找到,则返回-1            return -1;        //找到了,将其移入末尾        Node* tmp = head;         for (int  i=0;i<CatcheSize;i++)        {            if(key == tmp->key )            {                if(head != tail)                {                    if(tmp == head)                    {                       head = head->next;                       head ->pre =0;                       tail ->next = tmp;                       tmp ->pre = tail;                       tail = tmp;                       tail ->next = 0;                    }                    else if(tmp != tail)                   {                       tmp ->pre ->next = tmp -> next;                       tmp ->next ->pre = tmp ->pre;                       tail -> next = tmp;                       tmp -> pre = tail;                       tail = tmp;                       tail -> next = 0;                   }                }                break;            }            tmp = tmp->next;        }        return m1[key];    }    void set(int key, int value) {        int i=0;        //遍历链表,查看这个键是否存在,若存在,则更新其值;        //否则,插入改组数据。最后将该键数据移到链表尾部。        Node* tmp = head;        for ( i=0;i<CatcheSize;i++)        {            if(key == tmp->key )            {                m1[key] = value;                if(head != tail)                {                    if(tmp == head)                    {                       head = head->next;                       head ->pre =0;                       tail ->next = tmp;                       tmp ->pre = tail;                       tail = tmp;                       tail ->next = 0;                    }                    else if(tmp != tail)                   {                       tmp ->pre ->next = tmp -> next;                       tmp ->next ->pre = tmp ->pre;                       tail -> next = tmp;                       tmp -> pre = tail;                       tail = tmp;                       tail -> next = 0;                   }                }                break;            }            tmp = tmp->next;        }        //如果链表中不存在该键则新建节点,并链入表尾。        if(i == CatcheSize || CatcheSize == 0)        {            m1[key] = value;            Node* tmp1 = new Node;            tmp1 ->key = key;            CatcheSize++;            if(head != 0)            {                tail -> next = tmp1;                tmp1 -> pre = tail;                tail = tmp1 ;                tail ->next =0;            }            else            {                head = tmp1;                tail = tmp1;                tail ->next = 0;                head ->next = 0;                tail ->pre = 0;            }        }        //如果空间已满,则删除头结点        if(CatcheSize > capacity)        {            Node* fre;            fre = head;            m1.erase(fre -> key);            if(head != tail)            head = head ->next;            else            {                head = 0;                tail = 0;            }            delete [] fre;            CatcheSize--;        }    }};
View Code