leetcode-146-LRU-Cache

发表于   |  

描述

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

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

分析

LRU 即 Least Recently Used, 这是操作系统的内存管理中比较重要的内存页面置换算法，在其他的程序中也经常用到，LRU 算法的原则是：如果一段数据在很长一段时间内没有被访问到，那么将来它被访问的可能性也很小。在这个算法中，我们应该维护一个数据集，当数据集满时，我们应该将最久未被访问的数据淘汰。那么用什么数据结构来实现 LRU 算法呢，这个问题的要求实际上是需要维护一个有序数据集，每次命中时，该数据项需要排在第一位，插入时，也应该放在数据集的第一位，如果数据集满了再插入，需移除数据集的最后一位，将问题描述清楚了，是不是就发现最佳的数据结构是双向链表？

如果用 hash map 来维护数据节点，将数据节点组成一个双向链表，更新，查询操作的复杂度都是 O(1)

解决方案1(Golang)

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
type node struct {
    prev *node
    val int
    key int
    next *node
}

type dList struct {
    head *node
    tail *node
}

func (root *dList) PushFront(key, value int) {
    newNode := new(node)
    newNode.val = value
    newNode.key = key
    if root.head == nil {
        root.head = newNode
        root.tail = newNode
    } else {
        newNode.next = root.head
        root.head.prev = newNode
        root.head = newNode
    }
}

func (root *dList) EvictTail() {
    if root.tail != nil {
        if root.tail.prev == nil {
            root.head = nil
            root.tail = nil
        } else {
            root.tail.prev.next = nil
            root.tail = root.tail.prev
        }
    }
}

func (root *dList) MoveToFront(n *node) {
    if n.prev != nil {
        if n.next == nil {
            n.prev.next = nil
            root.tail = n.prev
        } else {
            n.prev.next = n.next
            n.next.prev = n.prev
        }
        n.prev = nil
        root.head.prev = n
        n.next = root.head
        root.head = n
    }
}

type LRUCache struct {
    maxCap int
    curCap int
    vMap map[int]*node
    dNode *dList
}

func Constructor(capacity int) LRUCache {
    newCache := new(LRUCache)
    newCache.maxCap = capacity
    newCache.vMap = make(map[int]*node)
    newCache.dNode = new(dList)
    return *newCache
}

func (this *LRUCache) Get(key int) int {
    if valNode, ok := this.vMap[key]; ok {
        this.dNode.MoveToFront(valNode)
        return valNode.val
    } else {
        return -1
    }
}

func (this *LRUCache) Put(key, value int) {
    if this.maxCap == 0 {
        return
    }
    if valNode, ok := this.vMap[key]; ok {
        valNode.val = value
        this.dNode.MoveToFront(valNode)
    } else {
        if this.curCap < this.maxCap {
            this.curCap += 1
        } else {
            delete(this.vMap, this.dNode.tail.key)
            this.dNode.EvictTail()
        }
        this.dNode.PushFront(key, value)
        this.vMap[key] = this.dNode.head
    }
}

leetcode 提交的代码貌似不能引入标准库，所以这里需要维护一个双向链表，否则的话，在 Golang 中我们可以使用 container/list。

lru 是一个很常用的算法，已经有很多工业级的实现，hashicorp/golang-lru 和 syndtr/goleveldb 都是非常好的学习资料。

相关问题

题目来源

References