前言
2020年了。
正文
问题来源
本问题来自leetcode上的460题。
问题描述
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
示例 1:
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
分析：
用一个map来记录key与slice下标的映射关系。查找时先查询对应key是否有，若有则返回该值，并将该节点计数加一并存活时间更新，若无返回-1；存储时先看缓存中是否有对应的key，若有则先更新，若没有则判断是否超过达到了预定的缓冲长度，若没有则直接插入，若已到达则删除第一个节点并删除key-value映射。
type LFUNode struct {
key int
value int
count int
ttl int
}
type LFUSlice []LFUNode
type LFUCache struct {
time int
lfu LFUSlice
m map[int]int
}
func (h *LFUCache) Less(i, j int) bool {
if h.lfu[i].count < h.lfu[j].count {
return true
}
if h.lfu[i].count == h.lfu[j].count && h.lfu[i].ttl < h.lfu[j].ttl {
return true
}
return false
}
func (h *LFUCache) Swap(i, j int) {
h.m[h.lfu[j].key], h.m[h.lfu[i].key] = i, j
h.lfu[i], h.lfu[j] = h.lfu[j], h.lfu[i]
}
func (h *LFUCache) Len() int {
return len(h.lfu)
}
func (h *LFUCache) Pop() (v interface{}) {
h.lfu, v = h.lfu[:len(h.lfu)-1], h.lfu[len(h.lfu)-1]
delete(h.m, v.(LFUNode).key)
return
}
func (h *LFUCache) Push(v interface{}) {
h.m[v.(LFUNode).key] = len(h.lfu)
//fmt.Println(v.(LFUNode).key, len(h.lfu))
h.lfu = append(h.lfu, v.(LFUNode))
}
func Constructor(capacity int) LFUCache {
return LFUCache{
0,
make(LFUSlice, 0, capacity),
make(map[int]int),
}
}
func (this *LFUCache) Get(key int) int {
if cap(this.lfu) == 0 {
return -1
}
v, ok := this.m[key]
if !ok {
//fmt.Println("here")
return -1
}
this.time++
this.lfu[v].count++
value := this.lfu[v].value
this.lfu[v].ttl = this.time
heap.Fix(this, v)
return value
}
func (this *LFUCache) Put(key int, value int) {
if cap(this.lfu) == 0 {
return
}
this.time++
v, ok := this.m[key]
if ok {
this.lfu[v].count++
this.lfu[v].value = value
this.lfu[v].ttl = this.time
heap.Fix(this, v)
//Fix(&(this.lfu), )
return
}
if len(this.lfu) < cap(this.lfu) {
heap.Push(this, LFUNode{key,value,1,this.time})
return
}
heap.Pop(this)
heap.Push(this, LFUNode{key,value,1,this.time})
}
总结：
勤思考。
结语
不管怎么样好好加油。
