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

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能
set(key, value)：将记录(key, value)插入该结构
get(key)：返回key对应的value值
[要求]
set和get方法的时间复杂度为O(1)
某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。
若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

• 使用unorder_map<int, node>记录缓存中现有key及对应节点；

  set和get方法的时间复杂度为O(1)

• 使用双向链表反映新鲜度,离head越近越新鲜，离tail越远越不常用

  某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。

set或get后，维护链表，将相应节点放到head后面；将该动作封装成moveToHead(node);

• 使用vector<int> res 记录输出

  对于每个操作2（get），输出一个答案

  </int>

get动作将涉及到res；

当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

set可能增加链表长度，需要维护mp和链表和缓存剩余空间
当链表长度发生改变时，可能发生移除操作；将该动作封装成removeLast(node);