134. LRU Cache

Description

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:getandset.

get(key)- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.

set(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. Finally, you need to return the data from each get

Example

Example1

Input:

LRUCache(2)

set(2, 1)

set(1, 1)

get(2)

set(4, 1)

get(1)

get(2)

Output: [1,-1,1]

Explanation：

cache cap is 2，set(2,1)，set(1, 1)，get(2) and return 1，set(4,1) and delete (1,1)，because （1,1）is the least use，get(1) and return -1，get(2) and return 1.

Example 2:

Input：

LRUCache(1)

set(2, 1)

get(2)

set(3, 2)

get(2)

get(3)

Output：[1,-1,2]

Explanation：

cache cap is 1，set(2,1)，get(2) and return 1，set(3,2) and delete (2,1)，get(2) and return -1，get(3) and return 2.

思路：

链表模拟

涉及删除和移动操作，使用链表，链表是有序的，一直维护，近期最多使用的放于尾部，那么每次缓存达到上限的时候，删除头部即可，其余为链表的基础操作模拟即可。

答案值得借鉴的是将node移到最后，还有删除头节点以及加入新节点用分开的函数实现，调用起来十分清晰，还有就是将前序节点存储在hash_map中，非常方便。

还要注意pop_front的时候要先把元素加进去再pop不然会报错。

代码：