文章目录
  1. 1. LRU Cache
  2. 2.

LRU Cache

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

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

LRUCache,最近最少使用Cache.
原理很简单,维护一个key的列表,每当一个key被访问,就把它提到列表最前面.
当列表的大小超过预设的大小时,把列表最后的一个key删除.
不过如果用普通的数组实现这个列表的话,”把它提到列表最前面”这个操作就需要O(n)的时间复杂度.
所以使用一个双向链表来做这个列表就可以了.
双向链表的操作稍微有点繁琐,其他逻辑都十分简单.
然而这个题是个Hard难度,通过率还特低,只有15%,不知道为啥.

代码如下:

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
class Node
attr_accessor :data
attr_accessor :pre
attr_accessor :post
def initialize(data)
@data = data
end
end
class LRUCache
attr_accessor :capacity
def initialize(capacity)
@capacity = capacity
@head = nil
@foot = nil
@size = 0
@map = {}
end
def get(key)
node = @map[key]
if node != nil
active_key key
node.data[1]
else
-1
end
end
def set(key, value)
ori = @map[key]
if ori == nil
if @size >= @capacity
remove_lru
else
@size += 1
end
node = Node.new([key,value])
@map[key] = node
if @head == nil
@head = node
@foot = node
else
@head.pre = node
node.post = @head
@head = node
end
else
@map[key].data[1] = value
active_key key
end
end
def active_key(key)
node = @map[key]
return if @head == node
node.pre.post = node.post if node.pre != nil
node.post.pre = node.pre if node.post != nil
@foot = node.pre if @foot == node
node.pre = nil
node.post = @head
@head.pre = node
@head = node
end
def remove_lru
@map[@foot.data[0]] = nil
@foot.pre.post = nil if @foot.pre != nil
@foot = @foot.pre
end
end
文章目录
  1. 1. LRU Cache
  2. 2.