算法----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? = null
        var nex: Node? = null
        var value: Int
        var key: Int

        init {
            this.value = value
            this.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 = capacity

        init {
            dumpHead.nex = dumpTail
            dumpTail.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 = node
                node.nex = dumpHead.nex
                dumpHead.nex = node
                node.pre = dumpHead
                map[key] = node
            }

            while (map.size > mCapability) {
                dumpTail.pre?.let {
                    it.pre!!.nex = dumpTail
                    dumpTail.pre = it.pre
                    map.remove(it.key)
                }
            }
        }

        private fun updateNodeToHeadNext(find: Node?) {
            if (find != null) {
                find.nex!!.pre = find.pre
                find.pre!!.nex = find.nex

                dumpHead.nex!!.pre = find
                find.nex = dumpHead.nex

                dumpHead.nex = find
                find.pre = dumpHead
            }
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

偷懒版：

    class CacheMap(initialCapacity: Int, loadFactor: Float, accessOrder: Boolean) :
        LinkedHashMap<Int, Int>(initialCapacity, loadFactor, accessOrder) {
        private val initC = initialCapacity


        override 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
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

总结

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

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

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