算法----LRU缓存机制

题目

请你设计并实现一个满足 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) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

解决思路

使用Map加双链表实现即可，参考Java里LinkedHashMap

解决方法

    class Node(key: Int, value: Int) {var pre: Node? = nullvar nex: Node? = nullvar value: Intvar key: Intinit {this.value = valuethis.key = key}}class LRUCache(capacity: Int) {var map = mutableMapOf<Int, Node>()private var dumpHead: Node = Node(-1, -1)private var dumpTail: Node = Node(-1, -1)var mCapability = capacityinit {dumpHead.nex = dumpTaildumpTail.pre = dumpHead}fun get(key: Int): Int {val value = map.getOrDefault(key, null)if (value != null) {updateNodeToHeadNext(map[key])}return value?.value ?: -1}fun put(key: Int, value: Int) {if (map.containsKey(key)) {updateNodeToHeadNext(map[key])map[key]!!.value = value} else {val node = Node(key, value)dumpHead.nex!!.pre = nodenode.nex = dumpHead.nexdumpHead.nex = nodenode.pre = dumpHeadmap[key] = node}while (map.size > mCapability) {dumpTail.pre?.let {it.pre!!.nex = dumpTaildumpTail.pre = it.premap.remove(it.key)}}}private fun updateNodeToHeadNext(find: Node?) {if (find != null) {find.nex!!.pre = find.prefind.pre!!.nex = find.nexdumpHead.nex!!.pre = findfind.nex = dumpHead.nexdumpHead.nex = findfind.pre = dumpHead}}}

偷懒版：

    class CacheMap(initialCapacity: Int, loadFactor: Float, accessOrder: Boolean) :LinkedHashMap<Int, Int>(initialCapacity, loadFactor, accessOrder) {private val initC = initialCapacityoverride fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {return size > initC}}class LRUCache(capacity: Int) {var map = CacheMap(capacity, 0.5f, true)fun get(key: Int): Int {return map.getOrDefault(key,-1)}fun put(key: Int, value: Int) {map[key] = value}}

总结

1.事非经过不知难。 本以为很简单 结果还是一个小时下来了

2.哎 之前面试过这个题 但是自己直接说用LinkedHashMap

3.为了保证时间复杂度为O（1），Map 里 value 为 Node
方便对Node进行调整。