题解 | #设计LRU缓存结构#

基本思想

需要O(1)时间的插入删除，必须要一个map，此外需要判断时间，那么还需要一个双链表。如果自己实现双链表，会很麻烦，可以直接使用list。

需要设置一个节点类型，Node{k,v}，list存储Node*指针。注意必须要有k，方便后续删除最后一个节点的时候，根据k去删除map。

接下来就是map了，注意这里的value需要指向list中的元素的位置，因此不能是Node*，这样会没法直接定位到链表的节点，需要 list<Node*>::iterator 存储一个迭代器，这样*解引用就可以指向那个被访问的list节点了，方便插入和删除。

核心结构如下

struct Node {
	int k, v;
};
map<int, list<Node*>::iterator> kv;
list<Node*> li;

代码演示

代码很详细，按照我的注释逻辑，手动推演一下，很容易明白。

struct Node {
	int k, v;
};

struct Solution {
	map<int, list<Node*>::iterator> kv; // O1查找
	list<Node*> li;   // 区分前后，begin() 最新，
	int capacity ; 

	Solution(int c): capacity(c){

	}
	~Solution() {
		for (Node* pn : li) {
			delete pn;
		}
	}
	void set(int k, int v) {
		// 如果存在 更新即可
		if (kv.count(k)) {
			auto node = kv[k];
			(*node)->v = v; // 把迭代器解引用，然后取出v
			get(k); // update
		}
		else {
			// 否则插入
			Node* cur=new Node{ k,v };
			li.push_front(cur); //前面是最新的
			kv[k] = li.begin(); //map存储的是迭代器
			

			if (kv.size() > capacity) {
				// 删除多余的
				Node* del = li.back();
				kv.erase(del->k); // map和list中同时删除
				li.pop_back();
				delete del; //记得别内存泄露了
			}

		}
	}

	int get(int k) {
		int ret = -1;
		// 如果存在
		if (kv.count(k)) {
			auto cur = kv[k];
			ret = (*cur)->v;
			// 更新位置
			li.push_front(*cur); // 这两步别反了，先把Node*插入头，再反过头删除原来的迭代器位置
			li.erase(cur); 
			kv[k] = li.begin(); // 重新指向新的迭代器
			return ret;
		}
		else {
			//否则 返回-1
			return ret;
		}
	}

};