设计LFU缓存结构
描述
一个缓存结构需要实现如下功能。
- set(key, value)：将记录(key, value)插入该结构
- get(key)：返回key对应的value值
但是缓存结构中最多放K条记录，如果新的第K 1条记录要加入，就需要根据策略删掉一条记录，然后才能把新记录加入。这个策略为：在缓存结构的K条记录中，哪一个key从进入缓存结构的时刻开始，被调用set或者get的次数最少，就删掉这个key的记录；
如果调用次数最少的key有多个，上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构，K作为参数给出若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，返回一个答案
示例1
输入：
代码语言：javascript复制[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3复制
返回值：
代码语言：javascript复制[4,-1]复制
说明：
代码语言：javascript复制在执行"1 4 4"后，"1 1 1"被删除。因此第二次询问的答案为-1解题思路：
1，lfu和lru思路一样都是hash加双链表
2，不同的地方是node上需要保存频率数据
3，需要一个map保存频率到相同频率的最前面节点的映射
4，每次访问的时候需要把节点摘除，如果存在频率加1的节点，移动到加1节点前面
5，如果不存在，移动到当前频率节点前面，频率加16，如果当前节点后续节点和当前节点频率一样，当前频率指向下一个节点，否则删除这个频率
7，插入的时候如果容量没有满，插入在频率为1的节点的前面，或者末尾
8，如果满了删除末尾节点和频率，如果末尾节点和前面频率一致，不删除
代码实现package main
import . "nc_tools"
//import "fmt"
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
func LFU( operators [][]int , k int ) []int {
// write code here
l:=NewLFU(k)
var r []int
for _,op:=range operators{
if op[0]==1{
l.set(op[1],op[2])
}else{
r=append(r,l.get(op[1]))
}
/* for k,v:=range l.freqToNode{
fmt.Print(v.key,k)
}
fmt.Print(":")
for v:=l.head.next;v!=l.tail;v=v.next{
fmt.Print(v.key)
}
fmt.Println("")*/
}
return r
}
type Node struct{
prev,next *Node
key,val,frequency int
}
type LFUCache struct{
m map[int]*Node
head,tail *Node
freqToNode map[int]*Node
capacity int
}
func NewLFU(capacity int)*LFUCache{
c:=&LFUCache{
head:&Node{},
tail:&Node{},
m:make(map[int]*Node),
freqToNode:make(map[int]*Node),
capacity:capacity,
}
c.head.next=c.tail
c.tail.prev=c.head
return c
}
func (l*LFUCache)get(key int)int{
v,ok:=l.m[key]
if !ok{
return -1
}
if l.freqToNode[v.frequency]==v{
if v.next!=l.tail && v.next.frequency==v.frequency{
l.freqToNode[v.frequency]=v.next
}else{
delete(l.freqToNode,v.frequency)
}
}
v.frequency
if v.prev==l.head{
l.freqToNode[v.frequency]=v
return v.val
}
prev,ok:=l.freqToNode[v.frequency]
l.remove(v)
if ok{
l.addPrev(prev,v)
l.freqToNode[v.frequency]=v
return v.val
}
prev=l.freqToNode[v.frequency-1]
l.addPrev(prev,v)
l.freqToNode[v.frequency]=v
return v.val
}
func (l*LFUCache)addPrev(cur,node *Node){
cur.prev.next=node
node.prev=cur.prev
cur.prev=node
node.next=cur
}
func (l*LFUCache)remove(node *Node){
node.prev.next=node.next
node.next.prev=node.prev
}
func (l*LFUCache)set(key,val int){
if l.get(key)!=-1{
v:=l.m[key]
v.val=val
return
}
node:=&Node{
key:key,
val:val,
frequency:1,
}
if len(l.m)>=l.capacity{
cur:=l.tail.prev
if cur==l.head{
return
}
if cur.prev.frequency!=cur.frequency{
delete( l.freqToNode,cur.frequency)
}
l.remove(cur)
delete(l.m,cur.key)
}
l.m[key]=node
cur,ok:=l.freqToNode[1]
if ok{
l.addPrev(cur,node)
l.freqToNode[1]=node
return
}
l.addPrev(l.tail,node)
l.freqToNode[1]=node
return
}
