LeetCode-146.LRU缓存 - sheep44044的小站

链表#

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

示例：

1
输入
2
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
3
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
4
输出
5
[null, null, null, 1, null, -1, null, -1, 3, 4]
6

7
解释
8
LRUCache lRUCache = new LRUCache(2);
9
lRUCache.put(1, 1); // 缓存是 {1=1}
10
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
11
lRUCache.get(1);    // 返回 1
12
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
13
lRUCache.get(2);    // 返回 -1 (未找到)
14
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
15
lRUCache.get(1);    // 返回 -1 (未找到)
16
lRUCache.get(3);    // 返回 3
17
lRUCache.get(4);    // 返回 4

解法

思路：这里用map来存储数据，双向链实现先后性

这里的难点是很多的指针的操作，所以我们把它化为多个简单的操作(单纯从逻辑上理解是不难的)

removeNode(node): 把某个节点从链表里抠出来。

让它前一个节点的 next 绕过它，指向它的后一个节点。

让它后一个节点的 prev 绕过它，指向它的前一个节点。

addToHead(node): 将节点插入到虚拟头节点之后（代表变成了最新使用的数据）。
moveToHead(node): = 先 removeNode (把它从原位置抠出来) + 再 addToHead (放到最前面)。
removeTail(): 找到最没用的那个节点（就是 tail.prev，虚拟尾节点的前一个），把它 removeNode 抠出来，并返回这个节点（为了后面能在哈希表里删掉它的 key）。

1
type DLinkedNode struct {
2
   key, val int
3
   pre, next *DLinkedNode
4
}
5

6
type LRUCache struct {
7
    capacity int
8
    cache map[int]*DLinkedNode
9
    head *DLinkedNode
10
    tail *DLinkedNode
11
}
12

13
func Constructor(capacity int) LRUCache {
14
    l := LRUCache{
15
        capacity: capacity,
16
        cache: map[int]*DLinkedNode{},
17
        head: &DLinkedNode{},
18
        tail: &DLinkedNode{},
19
    }
20

21
    l.head.next = l.tail
22
    l.tail.pre = l.head
23

24
    return l
25
}
26

27

28
func (this *LRUCache) Get(key int) int {
29
    if node, ok := this.cache[key]; ok {
30
        this.removeNode(node)
31
        this.addToHead(node)
32

33
        return node.val
34
    }else {
35
        return -1
36
    }
37
}
38

39

40
func (this *LRUCache) Put(key int, value int) {
41
    if node, ok := this.cache[key]; ok {
42
        node.val = value
43
        this.removeNode(node)
44
        this.addToHead(node)
45
    }else {
46
        node := &DLinkedNode {
47
            key: key,
48
            val: value,
49
        }
50
        this.cache[key] = node
51
        this.addToHead(node)
52

53
        if len(this.cache) > this.capacity {
54
            node := this.removeTail()
55
            delete(this.cache, node.key)
56
        }
57
    }
58
}
59

60
func (this *LRUCache) removeNode(node *DLinkedNode) {
61
    node.pre.next = node.next
62
    node.next.pre = node.pre
63
}
64

65
func (this *LRUCache) addToHead(node *DLinkedNode) {
66
    node.pre = this.head
67
    node.next = this.head.next
68
    this.head.next.pre = node
69
    this.head.next = node
70
}
71

72
func (this *LRUCache) removeTail() *DLinkedNode {
73
    node := this.tail.pre
74
    node.pre.next = this.tail
75
    this.tail.pre = node.pre
76
    return node
77
}