---

前言

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。
为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

LFU词频是第一的权限，词频一样的删除时间较早的那个
当Cache满的时候,新数据进去时,删除策略:
如果词频最小的只有一条, 删除即可
如果词频最小的有多条,删除距离你操作最远的记录
删除的元素一旦出了结构,下次再进入结构,次数重新开始计算没有历史累加
C出了结构,下次再进重新计算词频

节点放到了哪个桶里
Node:双向链表结构, last, next指针
词频桶:每一个词频一个桶，二维双向链表结构,有一个头， 有一个尾,
桶内部的指针:双向链表连接,桶与桶之间也是双向链表连接
二维桶结构,支持动态添加删除，当桶里没有数据时需要删除
有一张Map表: Key跟Node对应的, (Key, Node)
Map表:某一个节 点在哪个桶里的对应表，(Node,桶的内存地址)
当一个节点从一个桶里分离出来时要看有没有下一个桶,如果没有下一个桶,需要新建
或者下一个桶的词频不是当前桶词频+1,也需要新建
每次调整都是0(1),因为没有遍历
当Cache容量满了，新数据加入时,删除最头部的桶的最上面的一-条记录
数据结构实现描述:
首先所有的桶是一个双向链表，有一个头桶, 一个尾桶
其次,一个桶的内部有一个头点 一个尾点 任何一个节点(包括头,尾点)从桶里分离出来时,需要保证这个小桶里面头和尾的指针要指对,如果数据分离后，当前桶如果没有数据需要删除
而且当前桶被删除后，整个桶序列的头指针跟尾指针也需要调整正确

代码

public class LFUCache {

	public LFUCache(int K) {
		capacity = K;
		size = 0;
		records = new HashMap<>();
		heads = new HashMap<>();
		headList = null;
	}

	private int capacity; // 缓存的大小限制，即K
	private int size; // 缓存目前有多少个节点
	private HashMap<Integer, Node> records;// 表示key(Integer)由哪个节点(Node)代表
	private HashMap<Node, NodeList> heads; // 表示节点(Node)在哪个桶(NodeList)里
	private NodeList headList; // 整个结构中位于最左的桶

	// 节点的数据结构
	public static class Node {
		public Integer key;
		public Integer value;
		public Integer times; // 这个节点发生get或者set的次数总和
		public Node up; // 节点之间是双向链表所以有上一个节点
		public Node down;// 节点之间是双向链表所以有下一个节点

		public Node(int k, int v, int t) {
			key = k;
			value = v;
			times = t;
		}
	}

	// 桶结构
	public static class NodeList {
		public Node head; // 桶的头节点
		public Node tail; // 桶的尾节点
		public NodeList last; // 桶之间是双向链表所以有前一个桶
		public NodeList next; // 桶之间是双向链表所以有后一个桶

		public NodeList(Node node) {
			head = node;
			tail = node;
		}

		// 把一个新的节点加入这个桶，新的节点都放在顶端变成新的头部
		public void addNodeFromHead(Node newHead) {
			newHead.down = head;
			head.up = newHead;
			head = newHead;
		}

		// 判断这个桶是不是空的
		public boolean isEmpty() {
			return head == null;
		}

		// 删除node节点并保证node的上下环境重新连接
		public void deleteNode(Node node) {
			if (head == tail) {
				head = null;
				tail = null;
			} else {
				if (node == head) {
					head = node.down;
					head.up = null;
				} else if (node == tail) {
					tail = node.up;
					tail.down = null;
				} else {
					node.up.down = node.down;
					node.down.up = node.up;
				}
			}
			node.up = null;
			node.down = null;
		}
	}

	// removeNodeList：刚刚减少了一个节点的桶
	// 这个函数的功能是，判断刚刚减少了一个节点的桶是不是已经空了。
	// 1）如果不空，什么也不做
	//
	// 2)如果空了，removeNodeList还是整个缓存结构最左的桶(headList)。
	// 删掉这个桶的同时也要让最左的桶变成removeNodeList的下一个。
	//
	// 3)如果空了，removeNodeList不是整个缓存结构最左的桶(headList)。
	// 把这个桶删除，并保证上一个的桶和下一个桶之间还是双向链表的连接方式
	//
	// 函数的返回值表示刚刚减少了一个节点的桶是不是已经空了，空了返回true；不空返回false
	private boolean modifyHeadList(NodeList removeNodeList) {
		if (removeNodeList.isEmpty()) {
			if (headList == removeNodeList) {
				headList = removeNodeList.next;
				if (headList != null) {
					headList.last = null;
				}
			} else {
				removeNodeList.last.next = removeNodeList.next;
				if (removeNodeList.next != null) {
					removeNodeList.next.last = removeNodeList.last;
				}
			}
			return true;
		}
		return false;
	}

	// 函数的功能
	// node这个节点的次数+1了，这个节点原来在oldNodeList里。
	// 把node从oldNodeList删掉，然后放到次数+1的桶中
	// 整个过程既要保证桶之间仍然是双向链表，也要保证节点之间仍然是双向链表
	private void move(Node node, NodeList oldNodeList) {
		oldNodeList.deleteNode(node);
		// preList表示次数+1的桶的前一个桶是谁
		// 如果oldNodeList删掉node之后还有节点，oldNodeList就是次数+1的桶的前一个桶
		// 如果oldNodeList删掉node之后空了，oldNodeList是需要删除的，所以次数+1的桶的前一个桶，是oldNodeList的前一个
		NodeList preList = modifyHeadList(oldNodeList) ? oldNodeList.last : oldNodeList;
		// nextList表示次数+1的桶的后一个桶是谁
		NodeList nextList = oldNodeList.next;
		if (nextList == null) {
			NodeList newList = new NodeList(node);
			if (preList != null) {
				preList.next = newList;
			}
			newList.last = preList;
			if (headList == null) {
				headList = newList;
			}
			heads.put(node, newList);
		} else {
			if (nextList.head.times.equals(node.times)) {
				nextList.addNodeFromHead(node);
				heads.put(node, nextList);
			} else {
				NodeList newList = new NodeList(node);
				if (preList != null) {
					preList.next = newList;
				}
				newList.last = preList;
				newList.next = nextList;
				nextList.last = newList;
				if (headList == nextList) {
					headList = newList;
				}
				heads.put(node, newList);
			}
		}
	}

	public void put(int key, int value) {
		if (capacity == 0) {
			return;
		}
		if (records.containsKey(key)) {
			Node node = records.get(key);
			node.value = value;
			node.times++;
			NodeList curNodeList = heads.get(node);
			move(node, curNodeList);
		} else {
			if (size == capacity) {
				Node node = headList.tail;
				headList.deleteNode(node);
				modifyHeadList(headList);
				records.remove(node.key);
				heads.remove(node);
				size--;
			}
			Node node = new Node(key, value, 1);
			if (headList == null) {
				headList = new NodeList(node);
			} else {
				if (headList.head.times.equals(node.times)) {
					headList.addNodeFromHead(node);
				} else {
					NodeList newList = new NodeList(node);
					newList.next = headList;
					headList.last = newList;
					headList = newList;
				}
			}
			records.put(key, node);
			heads.put(node, headList);
			size++;
		}
	}

	public int get(int key) {
		if (!records.containsKey(key)) {
			return -1;
		}
		Node node = records.get(key);
		node.times++;
		NodeList curNodeList = heads.get(node);
		move(node, curNodeList);
		return node.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
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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198