C++题解

访问时间复杂度O（1）则用hash表，插入删除时间复杂度O(1)则用链表。此题可用STL list+unordered_map组合的方式，双向链表用于维护key值得访问时间，最久未访问的位于链表表头。哈希表用于保存key-value键值对：

set:
1、当缓存结构中的元素不足k个时，直接插入；
2、当缓存元素中的个数满了之后插入元素，则先在map中查找key，找到说明key在缓存结构中，则更新链表和map；若找不到则将链表表头移除（删除最久未访问节点），然后将表头对应的map中的键值对删除，之后在插入新的键值对即可。
get:
在map中查找key，找到则更新链表并返回相应value值，找不到则返回-1。

代码如下：

class Solution {
public:
    list<int> lru;//记录更新信息
    unordered_map<int, int> Map;//记录具体key-value键值对
    int Max;//缓存结构最大值

    void set(vector<int>& opt)
    {
        if(Max-- > 0)//元素个数小雨k时，直接插入即可
        {
           lru.push_back(opt[1]);
           Map[opt[1]] = opt[2];
        }
        else
        {
           if(Map.find(opt[1]) != Map.end())//该key值已存在
           {
               //更新链表中key的访问优先级（表头表示最久未访问）
              lru.remove(opt[1]);   //删除链表中的已存在的key
              lru.push_back(opt[1]);//将将key插入链表尾
              Map[opt[1]] = opt[2];
           }
           else//key不存在
           {
              int key = lru.front();
              Map.erase(key);
              Map[opt[1]] = opt[2];
              lru.erase(lru.begin());
              lru.push_back(opt[1]);
           }
        }
    }

    int get(vector<int>&opt)
    {
        if(Map.find(opt[1]) != Map.end())//该key值已存在
        {
            lru.remove(opt[1]);
            lru.push_back(opt[1]);
            return Map[opt[1]];
        }
        else return -1;
    }

    vector<int> LRU(vector<vector<int> >& operators, int k) {
        // write code here
        vector<int> res;
        Max = k;
        for(auto& opt:operators)
        {
            if(opt[0] == 1) set(opt);
            else res.push_back(get(opt));
        }
        return res;
    }
};