Leetcode进阶之路——LRU Cache C++三种解法

去年网易秋招面试的时候有一道现场手撕LRU的题，跟这道几乎一样，现记录如下：
146. LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

先说一下题意，总共有三个操作：

LRUCache obj = new LRUCache(capacity);
obj.put(1, 1);
obj.get(1);

第一个是创建大小为capacity的cache
第二个是在key=1的位置放入value=1的值
第三个是取出key=1位置的value
需要清楚的几点：若重复在某个key的位置放入值，则原值会被新值覆盖，例如现在又执行obj.put(1, 2)，则现在位置1存放的是2，而不是原先的1
此外，题目也写了是LRU，即最近最少使用，这是操作系统中非常常见的一道题，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页，则访问顺序为：

即一旦内存被放满，则首先淘汰距当前最远时间的页中的值
那么回到这道题本身，根据这个流程的理解，最容易想到的一个方法就是：

用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。
每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。

这种方法实现很方便，就不写了，很明显，这样做每次都要访问内存页中的所有数据，复杂度太高，这道题如果用这种方法，也将超时，这时候就想到，这个<key, value>的对应形式不就是C++中map的方法，而同时，也可以用一个向量来保存每次读入的key，对于新key则置顶，实现如下：

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity, cur = 0; //cur表示已存放的容量
    }
    
    int get(int key) {
        vector<int>::iterator it = find(v.begin(), v.end(), key); //在vector中找对应的key
        if(it == v.end()) return -1; 
        v.erase(it); 
        v.emplace_back(key); //每次get都将该key置顶
        return m[key];
    }
    
    void put(int key, int value) {
        if(m[key])  //如果原先key中就有值，则覆盖原值，同时置顶该key
        {
            m[key] = value;
            vector<int>::iterator it = find(v.begin(), v.end(), key);
            v.erase(it);
            v.emplace_back(key);
            return;
        }
                
        if(cur == cap)
        {
            int p = v.front();
            m[p] = 0;
            v.erase(v.begin());
            m[key] = value;
            v.emplace_back(key);
        }
        else
        {
            cur++;
            v.emplace_back(key);
            m[key] = value;
        }
    }
    int cap, cur;
    vector<int> v;
    map<int, int> m;
};

然后想，这段代码能否再精简呢？可以看到

v.erase(v.begin());
v.emplace_back(key);

这一段重复了很多次，完全可以用一个函数代替，且vector在头尾的操作很不方便，C++有已实现的list双向链表。此外，既然每次都要找key的位置，为什么不把这个位置也用一个map存放起来呢？
于是有了下面这段代码：

class LRUCache {
public:
	LRUCache(int capacity) {
		cap = capacity, cur = 0;
	}

	int get(int key) {
		if (cache.find(key) == cache.end())
			return -1;
		set(key);
		return cache[key];
	}

	void put(int key, int value) {
		set(key);
		cache[key] = value;
	}

private:
	int cap, cur;
	list<int> recent;
	unordered_map<int, int> cache;
	unordered_map<int, list<int>::iterator> pos;
	void set(int key)
	{
		if (cache.find(key) != cache.end())
		{
			list<int>::iterator it = pos[key];
			recent.erase(it);
			pos.erase(key);
		}
		else
		{
			if (cur >= cap)
			{
				int last = recent.back();
				recent.pop_back();
				cache.erase(last);
				pos.erase(last);
			}
			else
			{
				cur++;
			}
		}
		recent.emplace_front(key);
		pos[key] = recent.begin();
	}
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

set函数是将key置顶，由于无论是put还是get，都会使得“最近使用”的值更新，因此单独用一个函数封装
最后结果如下，当然这还不算最elegant最高效的，还有待学习~