题目
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现
LRUCache类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。函数
get和put必须以O(1)的平均时间复杂度运行。
解题思路
- 由题可知，需要Map来存储数据，List可以通过通过控制添加到的索引位置来将数据提前；
- 对Map进行操作时，通过更新List涉及的数据；
- 溢出时从List获取末尾节点即最近最少使用的数据进行删除更新。
代码展示
class LRUCache { Map< Integer, Integer> lru = null; List<Integer> sort = null; int cap; public LRUCache(int capacity) { lru = new HashMap<>(); sort = new ArrayList<>(capacity); cap = capacity; } public int get(int key) { Integer val = lru.get(key); if(val != null){ sort.remove((Integer) key); sort.add(0, key); return val; } else { return -1; } } public void put(int key, int value) { if(lru.containsKey(key)){ lru.put(key,value); sort.remove((Integer) key); sort.add(0, key); } else { if (lru.size() == cap) { int last = sort.get(cap - 1); sort.remove(cap - 1); lru.remove(last); } lru.put(key, value); sort.add(0, key); } } }
