LeetCode 460. LFU Cache

版权声明:本文为博主原创文章,转载请注明出处,谢谢!

版权声明:本文为博主原创文章,转载请注明出处:http://blog.jerkybible.com/2017/01/17/LeetCode-460-LFU-Cache/

访问原文「LeetCode 460. LFU Cache

题目要求

Design and implement a data structure for Least Frequently Used (LFU) 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 reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

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

Example:
>

LFUCache cache = new LFUCache( 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.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

题意解析

做一个符合LFU的cache,cache有两个方法,一个是get,一个是setget的作用是从cache中获取是否存在一个值;set的作用是往cache中放一个键值对,如果cache已满,则删除应当删除的键值对然后再把新的键值对放入。

解法分析

这道题最主要的就是熟悉什么是LFU。LFU是Least Frequently Used 近期最少使用算法。即最不经常使用页置换算法,要求在页置换时置换引用计数最小的页,因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多,但以后就不再使用,这类页将会长时间留在内存中,因此可以将引用计数寄存器定时右移一位,形成指数衰减的平均使用次数。

然后这道题要求在cache满的时候进行删除能够保持很快的速度。这里用到了java的HashMap以及双向指针,因为双向指针本身删除就很快。

解题代码

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
private CacheElement head = null;
private int capacity = 0;
private HashMap<Integer, Integer> valueHash = null;
private HashMap<Integer, CacheElement> cache = null;
public LFUCache(int _capacity) {
capacity = _capacity;
valueHash = new HashMap<Integer, Integer>();
cache = new HashMap<Integer, CacheElement>();
}
public int get(int key) {
if (valueHash.containsKey(key)) {
refreshUsage(key);
return valueHash.get(key);
}
return -1;
}
public void put(int key, int value) {
if ( capacity == 0 ) return;
if (valueHash.containsKey(key)) {
valueHash.put(key, value);
} else {
if (valueHash.size() < capacity) {
valueHash.put(key, value);
} else {
removeOne();
valueHash.put(key, value);
}
addToHead(key);
}
refreshUsage(key);
}
private void addToHead(int key) {
if (head == null) {
head = new CacheElement(0);
head.keys.add(key);
} else if (head.count > 0) {
CacheElement element = new CacheElement(0);
element.keys.add(key);
element.next = head;
head.prev = element;
head = element;
} else {
head.keys.add(key);
}
cache.put(key, head);
}
private void refreshUsage(int key) {
CacheElement element = cache.get(key);
element.keys.remove(key);
if (element.next == null) {
element.next = new CacheElement(element.count+1);
element.next.prev = element;
element.next.keys.add(key);
} else if (element.next.count == element.count+1) {
element.next.keys.add(key);
} else {
CacheElement tmp = new CacheElement(element.count+1);
tmp.keys.add(key);
tmp.prev = element;
tmp.next = element.next;
element.next.prev = tmp;
element.next = tmp;
}
cache.put(key, element.next);
if (element.keys.size() == 0) remove(element);
}
private void removeOne() {
if (head == null) return;
int old = 0;
for (int n: head.keys) {
old = n;
break;
}
head.keys.remove(old);
if (head.keys.size() == 0) remove(head);
cache.remove(old);
valueHash.remove(old);
}
private void remove(CacheElement element) {
if (element.prev == null) {
head = element.next;
} else {
element.prev.next = element.next;
}
if (element.next != null) {
element.next.prev = element.prev;
}
}
class CacheElement {
public int count = 0;
public LinkedHashSet<Integer> keys = null;
public CacheElement prev = null, next = null;
public CacheElement(int count) {
this.count = count;
keys = new LinkedHashSet<Integer>();
prev = next = null;
}
}