leetcode-146 LRU 缓存机制

题目描述:运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类:

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  • void put(int key, int value) 如果关键字已经存在,则变更其数据值;如果关键字不存在,则插入该组「关键字-值」。当缓存容量达到上限时,它应该在写入新数据之前删除最久未使用的数据值,从而为新的数据值留出空间。

代码实现

递归实现

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
class LRUCache {
/**
* 容量大小
*/
private int cap;

/**
* 有序HashMap
*/
private LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

/**
* 构造函数
*
* @param capacity 容量大小
*/
public LRUCache(int capacity) {
this.cap = capacity;
}

/**
* 获取值
*
* @param key key
* @return value
*/
public int get(int key) {
if (!this.cache.containsKey(key)) {
return -1;
}
makeRecently(key);
return this.cache.get(key);
}

/**
* 插入值
*
* @param key key
* @param value value
*/
public void put(int key, int value) {
if (this.cache.containsKey(key)) {
this.cache.put(key, value);
makeRecently(key);
} else {
if (this.cache.size() >= this.cap) {
this.cache.remove(this.cache.keySet().iterator().next());
}
this.cache.put(key, value);
}
}

/**
* 更新key为最近
*
* @param key key
*/
public void makeRecently(int key) {
int val = this.cache.remove(key);
this.cache.put(key, val);
}
}