BM100 设计LRU缓存结构
题意
链接：设计LRU缓存结构_牛客题霸_牛客网 (nowcoder.com)
思路
linkedHashMap可以维护元素插入顺序或者元素访问顺序，那么第一个元素即为最远没有访问过的，
set和get在通常情况是O(1),最坏情况是O(logn)
- 使用LinkedHashMap设置为访问次序
- set的时候要注意容量，移除最久未使用的key
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
| package com.yan.simulation;
import com.yan.base.Solution;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.LinkedHashMap;
public class LRUCacheSolution implements Solution {
private LinkedHashMap<Integer,Integer> map;
private int capacity;
@Override
public void solve(InputStream in, OutputStream outputStream) {
System.out.println("test");
LRUCacheSolution lruCacheSolution=new LRUCacheSolution(2);
lruCacheSolution.set(1,1);
lruCacheSolution.set(2,2);
System.out.println(lruCacheSolution.get(1));
lruCacheSolution.set(3,3);
System.out.println(lruCacheSolution.get(2));
lruCacheSolution.set(4,4);
System.out.println(lruCacheSolution.get(1));
System.out.println(lruCacheSolution.get(3));
System.out.println(lruCacheSolution.get(4));
}
public LRUCacheSolution() {
}
public LRUCacheSolution(int capacity) {
this.capacity=capacity;
map= new LinkedHashMap<>(capacity,0.75f,true);
}
public int get(int key) {
if (!map.containsKey(key)){
return -1;
}
int val=map.get(key);
return val;
}
public void set(int key, int value) {
if(map.size()==capacity&&!map.containsKey(key)){
int temp= map.entrySet().iterator().next().getKey();
map.remove(temp);
}
map.put(key,value);
}
}
|
BM101 设计LFU缓存结构
题意
思路
个人思路（非最佳）
使用优先队列，记录查找和查询次数以及相对位置，按照次数最少排序，使用懒删除的思想在容量满的时候才对前面的元素去除脏数据
使用数据结构
1
2
3
4
5
6
7
8
9
10
| private HashMap<Integer, Integer> map;
private HashMap<Integer, Integer> countMap;
private HashMap<Integer, Integer> opMap;
private int capacity;
private int op;
class Node {
int key;
int cnt;
int pos;
}
|
插入时：
容量为满的的时候，会先查询队首元素是否为正确节点步骤如下
- 判断这个节点是否正确的操作数
- 判断这个节点是否已删除
不正确的话就弹出节点，并重复操作，直至正确。countMap和map中回删除这个key；
插入和获取节点，countMap，map和queue更新数据，同时op操作数++
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
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
| package com.yan.simulation;
import com.yan.base.Solution;
import org.springframework.stereotype.Service;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.*;
@Service
public class LFUCacheSolution implements Solution {
private HashMap<Integer, Integer> map;
private HashMap<Integer, Integer> countMap;
private HashMap<Integer, Integer> opMap;
private int capacity;
private int op;
private PriorityQueue<Node> queue;
@Override
public void solve(InputStream in, OutputStream outputStream) {
LFUCacheSolution lfuCacheSolution = new LFUCacheSolution(3);
lfuCacheSolution.set(2054879058, -121373736);
lfuCacheSolution.set(2054879053, -121373736);
lfuCacheSolution.set(2054879025, -121373736);
lfuCacheSolution.set(2, 4);
lfuCacheSolution.set(3, 5);
System.out.println(lfuCacheSolution.get(2));
lfuCacheSolution.set(4, 4);
System.out.println(lfuCacheSolution.get(1));
}
public int[] LFU(int[][] operators, int k) {
ArrayList<Integer> arrayList = new ArrayList<>();
for (int i = 0; i < operators.length; i++) {
if (operators[i][0] == 1) {
set(operators[i][1], operators[i][2]);
} else {
int temp = get(operators[i][1]);
arrayList.add(temp);
}
}
int[] d = new int[arrayList.size()];
for (int i = 0; i < arrayList.size(); i++) {
d[i] = arrayList.get(i);
}
return d;
}
public LFUCacheSolution() {
}
public LFUCacheSolution(int capacity) {
this.capacity = capacity;
map = new HashMap<>(capacity);
countMap = new HashMap<>(capacity);
opMap = new HashMap<>(capacity);
queue = new PriorityQueue<>(capacity * 4, new Comparator<Node>() {
@Override
public int compare(Node o1, Node o2) {
if (o1.cnt != o2.cnt) {
return o1.cnt - o2.cnt;
} else {
return o1.pos - o2.pos;
}
}
});
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
int val = map.get(key);
int cnt = countMap.get(key);
countMap.put(key, cnt + 1);
opMap.put(key, op);
queue.add(new Node(key, cnt + 1, op));
op++;
return val;
}
public void set(int key, int value) {
if (map.size() == capacity && !map.containsKey(key)) {
Node temp = queue.peek();
while (!map.containsKey(temp.key) || (temp.pos != opMap.get(temp.key))) {
queue.poll();
temp = queue.peek();
}
temp=queue.poll();
map.remove(temp.key);
countMap.remove(temp.key);
}
map.put(key, value);
countMap.put(key, 1);
opMap.put(key, op);
queue.add(new Node(key, 1, op));
op++;
}
class Node {
int key;
int cnt;
int pos;
public Node() {
}
public Node(int key, int cnt, int pos) {
this.key = key;
this.cnt = cnt;
this.pos = pos;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Node)) return false;
Node node = (Node) o;
if (key != node.key) return false;
if (cnt != node.cnt) return false;
return pos == node.pos;
}
@Override
public int hashCode() {
int result = key;
result = 31 * result + cnt;
result = 31 * result + pos;
return result;
}
}
}
|
题解思路
题解 | #设计LFU缓存结构#_牛客博客 (nowcoder.net)
需要在O(1)时间内实现两个操作，我们第一时间想到的还是哈希表，利用哈希表保存LFU的key值，而哈希表的value值对应了另一边存着每个缓存需要的类的节点，这样就实现了直接访问。
但是我们还需要每次最快找到最久未使用的频率最小的节点，这时候我们可以考虑使用一个全局变量，跟踪记录最小的频率，有了最小的频率（当你使用set方法的时候每次进来的都是最小频率的，所以需要更新的时候通常更新为1，或者频率为最小频率的没有了进行++操作），怎样直接找到这个频率最小的节点，还是使用哈希表，key值记录各个频率，而value值就是后面接了一串相同频率的节点。如何保证每次都是最小频率的最久为使用，我们用双向链表将统一频率的节点连起来就好了，每次新加入这个频率的都在链表头，而需要去掉的都在链表尾。
算法全部代码参考leonyan18/AlgorithmCodeInJava (github.com)
