leetcode

//LRU: least recently used //方法一：分别用unordered_map和list数据结构各存储一份数据，所以时间复杂度很高，很耗时 #include<iostream> #include<list> #include<unordered_map> #include <utility> #define Error -1 using namespace std;

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

    int get(int key) {         if (map.find(key) != map.end())         {             list_key.remove(key);                list_key.push_back(key);             return map[key];         }         else             return Error;     }

    void put(int key, int value) {         //判断dict中是否有这个dict值，有的话更正value值，同时更新list_key         if (map.find(key) != map.end())         {             map[key] = value;             list_key.remove(key);             list_key.push_back(key);         }         else         {             if (map.size() >= this->size)             {                 map.erase(map.find(list_key.front()));                 list_key.pop_front();             }             //unordered_map插入键值对             //创建接收 insert() 方法返回值的pair类型变量，std::可以省略             //pair<unordered_map<int, int>::iterator, bool> ret;             std::pair<unordered_map<int, int>::iterator, bool> ret;             ret = map.insert(std::make_pair(key, value)); //map调用insert返回pair型返回值             cout << "bool = " << ret.second << endl;

            //list_key插入列表             list_key.push_back(key);         }     } private:     unordered_map<int, int> map;     list<int> list_key;     int size; };

//方法二：看了网友答案后，发现可以通过迭代器完成对unordered_map中key-value的指向（即key-value的iterator和指针变量作用一样），同时学习了容器list 的splice函数，通过其他博主的讲解得知，splice完成两个链表的拼接的时间复杂度是常数级（如果对一个链表操作就是链表元素的移动了） //LRU: least recently used #include<iostream> #include<list> #include<unordered_map> #include <utility> #define Error -1 using namespace std;

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

    int get(int key) {         if (map.find(key) != map.end())         {             //可以用字典的迭代器访问first和second元素来得到key值和map[key]值             //list_key.splice(list_key.begin(),list_key, map.find(key)->second);             list_key.splice(list_key.begin(),list_key, map[key]);             return map[key]->second;         }         else             return Error;     }

    void put(int key, int value) {         //判断dict中是否有这个dict值，有的话更正value值，同时更新list_key         if (map.find(key) != map.end())         {             map[key]->second = value;             list_key.splice(list_key.begin(), list_key, map[key]);         }         else         {             if (map.size() >= this->size)             {                 //这里直接按照map的key进行删除，另一个方式是用map的迭代器删除                 map.erase((list_key.back()).first);                 list_key.pop_back();             }

            //list_key插入列表             //插入字典/pair的两种方式如下             //list_key.push_front({ key,value });             list_key.push_front(make_pair(key, value));                          //unordered_map插入键值对             //创建接收 insert() 方法返回值的pair类型变量，std::可以省略             //pair<unordered_map<int, int>::iterator, bool> ret;             std::pair<unordered_map<int, list<pair<int, int>>::iterator>::iterator, bool> ret;             ret = map.insert(std::make_pair(key, list_key.begin())); //map调用insert返回pair型返回值             cout << "bool = " << ret.second << endl;         }     } private:     unordered_map<int, list<pair<int,int>>::iterator> map;     list<pair<int, int>> list_key;     int size; };