LeetCode讲解篇之面试题 16.25. LRU 缓存

面试题 16.25. LRU 缓存

题目描述

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

解答思路

对于这道题，我们可以采用哈希表+双向链表的方式构造数据结构。哈希表保存key，value的映射，保证能在O(1)的时间复杂度中查找数据。双向链表保存操作的时间顺序，保证能在O(1)的时间复杂度中完成增加数据，删除数据，修改数据。我们每次增改查操作，将该节点移动至双向链表头部

解答代码

type LRUCache struct {
    // 当前缓存的大小
    size int
    // 缓存最大的容量
    capacity int
    // key, value映射
    cache map[int]*DLinkedNode
    // 双向链表的头节点和尾节点
    head, tail *DLinkedNode
}

// 双向链表的节点
type DLinkedNode struct {
    // 当前节点的key, value数据
    key, value int
    // 当前节点的上一个节点和下一个节点
    prev, next *DLinkedNode
}

// 初始化双向链表的节点
func initDLinkedNode(key, value int) *DLinkedNode {
    return &DLinkedNode{
        key: key,
        value: value,
    }
}

func Constructor(capacity int) LRUCache {
    // 初始化LRUCache
    l := LRUCache{
        cache: map[int]*DLinkedNode{},
        head: initDLinkedNode(0, 0),
        tail: initDLinkedNode(0, 0),
        capacity: capacity,
    }
    l.head.next = l.tail
    l.tail.prev = l.head
    return l
}

func (this *LRUCache) Get(key int) int {
    // 数据不存在返回-1
    if _, ok := this.cache[key]; !ok {
        return -1
    }
    // 查找哈希表，返回当前节点
    node := this.cache[key]
    // 将该节点移动至头部（及更新节点操作的时间顺序）
    this.moveToHead(node)
    return node.value
}


func (this *LRUCache) Put(key int, value int)  {
    if _, ok := this.cache[key]; !ok {
        // 当前添加的节点不存在

        node := initDLinkedNode(key, value)
        // 加入哈希表
        this.cache[key] = node
        // 添加节点至双向链表头部（及更新当前添加的节点操作的时间顺序）
        this.addToHead(node)
        // 更新缓存的大小
        this.size++
        // 如果缓存的大小大于缓存的容量
        if this.size > this.capacity {
            // 删除当前节点
            removed := this.removeTail()
            delete(this.cache, removed.key)
            // 更新缓存的大小
            this.size--
        }
    } else {
        // 当前添加的节点存在

        // 查找哈希表，返回当前节点
        node := this.cache[key]
        // 更新当前节点的数据
        node.value = value
        // 将该节点移动至头部（及更新节点操作的时间顺序）
        this.moveToHead(node)
    }
}

// 将当前节点加入双向链表的头部
func (this *LRUCache) addToHead(node *DLinkedNode) {
    node.prev = this.head
    node.next = this.head.next
    this.head.next.prev = node
    this.head.next = node
}

// 删除当前节点
func (this *LRUCache) removeNode(node *DLinkedNode) {
    node.prev.next = node.next
    node.next.prev = node.prev
}

// 将当前节点移动至双向链表的头部
func (this *LRUCache) moveToHead(node *DLinkedNode) {
    this.removeNode(node)
    this.addToHead(node)
}

// 删除双向链表的尾部
func (this *LRUCache) removeTail() *DLinkedNode {
    node := this.tail.prev
    this.removeNode(node)
    return node
}
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
97
98
99
100
101
102
103
104
105
106
107
108
109
110