首页 > 代码库 > LRU Cache

LRU Cache

2024-07-17 02:56:12   226人阅读

    这个题敲了好久，比较纠结就是用链表加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

 


联系
我们