[leetcode] LRU缓存机制

https://leetcode-cn.com/problems/lru-cache/

思路：
这道题的关键是最近最少使用。“最少使用”就是说使用的次数越少越有可能被清除，“最近最少使用”说明，长时间没有使用的变量，即使使用次数很多也有可能被清除，因为最近没有被使用。

给每个 key 记录一个 cnt 值。每发生一次对这个key的操作（get 或 put），这个 cnt 就加1（新 key ，cnt初始化为1）。每发生一次 get 或 put 操作，将其他无关的 key 的值减去 1 （时间衰减），但是这样操作太没有效率， 所以维护一个时间变量time，每次有get或者put操作就给time 加1,同时对每个 key 加一个变量 latest_time记录最后使用时间。
当空间不够需要删除变量时，就将每个变量的 cnt-（time - latest_time）值进行排序，删除值最小的那个。为了使删除操作更有效率，可以使用堆排序算法。

进阶
题目要求 O(1)时间复杂度。上面的思路行不通。

get操作的时间要为O(1)，考虑用哈希表查找，但不能用哈希表本身去存储，否则就失去了缓存机制本身的意义。put操作为O(1)，考虑用链表。
所以整体的思路大概是这样的，在哈希表中存储链表指针，在链表中存储value。每次访问一个key之后，就将对应的链表节点移动到最末端。这样能保证最近访问的在末端，长时间没访问的在链表头部，删除节点时从头部删除，从尾部插入。
为了避免反复新建新节点，可以使用循环链表，首尾相连，这样在删除节点时只需要移动头部节点的位置即可。
为了提高链表的访问速度，可以分配连续的内存，用数组构造链表。
从这道题具体来看int get(int key) key是int型 ，因为链表指针占据空间很小，因此可以使用 直接寻址表 建哈希表。其他建哈希表的方法还有散列法、链接法。