LRU和LFU力扣题
LRU
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例：
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多调用 2 * 10^5 次 get 和 put
代码：
package main
type LRUCache struct {
kv map[int]*Node
head *Node
tail *Node
capacity int
}
type Node struct {
key int
val int
before *Node
next *Node
}
func Constructor(c int) LRUCache {
lruCache := make(map[int]*Node, 0)
cap := c
h := &Node{
before: nil,
next: nil,
}
t := &Node{
before: nil,
next: nil,
}
h.next = t
t.before = h
return LRUCache{
kv: lruCache,
head: h,
tail: t,
capacity: cap,
}
}
func (this *LRUCache) Get(key int) int {
n, ok := this.kv[key]
if !ok {
return -1
}
// last one
// if n.next==this.tail {
// return n.val
// }
n.before.next = n.next
n.next.before = n.before
this.tail.before.next = n
n.before = this.tail.before
n.next = this.tail
this.tail.before = n
return n.val
}
func (this *LRUCache) Put(key int, value int) {
_, ok := this.kv[key]
if !ok {
cur := &Node{
val: value,
key: key,
before: nil,
next: nil,
}
this.kv[key] = cur
if len(this.kv) > this.capacity {
d := this.head.next.key
node := this.kv[d]
delete(this.kv, d)
this.head.next = node.next
node.next.before = this.head
node.next = nil
}
this.tail.before.next = cur
cur.before = this.tail.before
cur.next = this.tail
this.tail.before = cur
return
}
n := this.kv[key]
n.val = value
n.before.next = n.next
n.next.before = n.before
this.tail.before.next = n
n.before = this.tail.before
n.next = this.tail
this.tail.before = n
}
/**
* Your LRUCache object will be instantiated and called as such:
* obj := Constructor(capacity);
* param_1 := obj.Get(key);
* obj.Put(key,value);
*/
LFU
请你为 最不经常使用（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) 的平均时间复杂度运行。
示例：
输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]
解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1); // cache=[1,_], cnt(1)=1
lfu.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3); // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2); // 返回 -1（未找到）
lfu.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4); // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1); // 返回 -1（未找到）
lfu.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3
提示：
0 <= capacity <= 104
0 <= key <= 105
0 <= value <= 109
最多调用 2 * 105 次 get 和 put 方法
优先队列
记录访问数，最近访问时间，每次都从队列里弹出，然后更改访问时间后再加上，logn时间。
class LFUCache {
class Node {
int key;
int value;
int idx;
int count;
}
int idx;
PriorityQueue<Node> pq;
Map<Integer,Node> map;
int capacity;
public LFUCache(int capacity) {
pq = new PriorityQueue<>((a,b)->{
if(a.count!=b.count) {
return a.count - b.count;
}
return a.idx - b.idx;
});
idx = 0;
map = new HashMap<>();
this.capacity = capacity;
}
public int get(int key) {
if (capacity==0) return -1;
if(!map.containsKey(key)) {
return -1;
}
Node cur = map.get(key);
pq.remove(cur);
cur.idx = idx;
cur.count++;
pq.add(cur);
idx++;
return cur.value;
}
public void put(int key, int value) {
if (capacity==0) return;
if(!map.containsKey(key)) {
if(map.size()==capacity) {
Node t = pq.poll();
map.remove((Integer)(t.key));
}
Node node = new Node();
node.key = key;
node.value = value;
node.count = 1;
node.idx = idx;
map.put(key,node);
pq.add(node);
idx++;
return;
}
Node cur = map.get(key);
pq.remove(cur);
cur.value = value;
cur.idx = idx;
cur.count++;
pq.add(cur);
idx++;
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
双向链表+两个map
类似LRU，只是count更改之后要分层重新添加。
类似这个图：
写下吧。
class LFUCache {
class Node {
int key;
int value;
int count;
Node before;
Node next;
}
class HeadAndTail {
Node head;
Node tail;
}
Map<Integer,Node> kv;
Map<Integer,HeadAndTail> diffCountHead; //保存不同count的head
int capacity;
int curSize;
public LFUCache(int capacity) {
kv = new HashMap<>();
this.capacity = capacity;
diffCountHead = new HashMap<>();
}
public int get(int key) {
if(capacity==0) return -1;
if(!kv.containsKey(key)) {
return -1;
}
Node cur = kv.get(key);
//System.out.println("get");
//System.out.println(cur.value);
switchLayer(cur);
return cur.value;
}
private void switchLayer(Node cur) {
// 删除原来位置的前后链接
cur.before.next = cur.next;
cur.next.before = cur.before;
cur.count++;
int curCount = cur.count;
if(!diffCountHead.containsKey(curCount)) {
InitOneLayer(curCount);
}
Node tail = diffCountHead.get(curCount).tail;
tail.before.next = cur;
cur.before = tail.before;
cur.next = tail;
tail.before = cur;
}
private void InitOneLayer(int curCount) {
Node head = new Node();
Node tail = new Node();
head.next = tail;
tail.before = head;
HeadAndTail ht = new HeadAndTail();
ht.head = head;
ht.tail = tail;
diffCountHead.put(curCount,ht);
}
public void put(int key, int value) {
if(capacity==0) return;
if(!kv.containsKey(key)) {
int i = 1;
if(capacity==curSize) {
while(true) {
HeadAndTail ht = diffCountHead.get(i);
Node head = ht.head;
if(head.next.next!=null) {
Node cur = head.next;
head.next.next.before = head;
head.next = head.next.next;
curSize--;
cur.before = null;
cur.next = null;
kv.remove(cur.key);
break;
}
i++;
}
}
if(!diffCountHead.containsKey(1)) {
InitOneLayer(1);
}
Node cur = new Node();
cur.key = key;
cur.value = value;
cur.count = 1;
kv.put(key,cur);
Node tail = diffCountHead.get(1).tail;
tail.before.next = cur;
cur.before = tail.before;
cur.next = tail;
tail.before = cur;
curSize++;
return;
}
Node cur = kv.get(key);
cur.value = value;
//System.out.println(cur.value);
switchLayer(cur);
}
}
/**
* Your LFUCache object will be instantiated and called as such:
* LFUCache obj = new LFUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/