题目

请你设计并实现一个满足 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

解题思路

首先实现查询的时间复杂度为 O(1) 的数据结构，那一定是要使用哈希表来存储 key 和 value 的映射关系。而为了实现 LRU 的功能，我们需要在哈希表中维护一个顺序，表示每个元素的使用顺序。插入的时间复杂度也是 O(1)，所以可以使用一个双向链表来维护这个顺序。每次查询时，将查询到的元素移动到链表的头部，表示它是最近使用的元素；每次插入时，将新插入的元素放在链表的头部，如果超过了容量，就将链表尾部的元素删除。

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
111
112
type CacheNode struct {
	key   int
	value int
	next  *CacheNode
	prev  *CacheNode
}

type LRUCache struct {
	capacity int
	size     int
	head     *CacheNode
	tail     *CacheNode
	cache    map[int]*CacheNode
}

// Add the node to the head of the doubly linked list
func (node *CacheNode) AddToHead(head *CacheNode, tail *CacheNode) (*CacheNode, *CacheNode) {
	if head == nil && tail == nil {
		node.prev = nil
		node.next = nil
		return node, node
	}

	head.prev = node
	node.prev = nil
	node.next = head

	return node, tail
}

// Move the node to the head of the doubly linked list
func (node *CacheNode) MoveToHead(head *CacheNode, tail *CacheNode) (*CacheNode, *CacheNode) {
	if node != head {
		// Remove the node from its current position
		prev := node.prev
		next := node.next
		prev.next = next
		if node == tail {
			tail = prev // Update tail if the node was the tail
		} else {
			next.prev = prev
		}

		// Add the node to the head
		node.next = head
		node.prev = nil
		head.prev = node
		head = node
	}

	return head, tail
}

// Remove the tail node from the doubly linked list
func RemoveTail(head *CacheNode, tail *CacheNode) (*CacheNode, *CacheNode) {
	if tail == nil {
		return head, tail
	}

	if head == tail {
		return nil, nil
	}

	prev := tail.prev
	prev.next = nil
	tail.prev = nil

	return head, prev
}

// Constructor initializes the LRUCache with a given capacity
func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		size:     0,
		head:     nil,
		tail:     nil,
		cache:    make(map[int]*CacheNode, 0),
	}
}

// Get retrieves the value of the key if it exists in the cache
func (lru *LRUCache) Get(key int) int {
	if node, exists := lru.cache[key]; exists {
		lru.head, lru.tail = node.MoveToHead(lru.head, lru.tail)
		return node.value
	}

	return -1
}

// Put inserts or updates the value of the key in the cache
func (lru *LRUCache) Put(key int, value int) {
	if node, exists := lru.cache[key]; exists {
		// Update the value and move the node to the head
		lru.head, lru.tail = node.MoveToHead(lru.head, lru.tail)
		node.value = value
	} else {
		// If the cache is full, remove the least recently used node
		if lru.size == lru.capacity {
			delete(lru.cache, lru.tail.key)
			lru.head, lru.tail = RemoveTail(lru.head, lru.tail)
			lru.size--
		}

		// Add the new node to the head
		node := &CacheNode{key: key, value: value}
		lru.head, lru.tail = node.AddToHead(lru.head, lru.tail)
		lru.cache[key] = node
		lru.size++
	}
}

思路并不复杂，关键是手动维护双向链表的代码会比较繁琐，容易出错。还有一些细节，比如从链表中删除节点时，要同步删除哈希表中的节点。还有就是在 Get 和 Put 方法中，要注意更新链表的头尾指针。总之，是个熟能生巧的活，当然写完需要多测试一下，确保没有遗漏的边界情况。