题解 | #设计LFU缓存结构#

package main

import (
	"time"
	"container/heap"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
type entry struct {
    key int
    val int
    updatedAt time.Time
}

type LfuEntry struct {
    entry entry
    count int
    index int
}

type mypriority []*LfuEntry
func (p mypriority) Len() int {
    return len(p)
}
func (p mypriority) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
    p[i].index = i
    p[j].index = j
}
func (p mypriority) Less(i, j int) bool {
    if p[i].count == p[j].count {
        return p[i].entry.updatedAt.Before(p[j].entry.updatedAt)
    }
    return p[i].count < p[j].count
}
func (p *mypriority) Push(x interface{}) {
    lfuEntry := x.(*LfuEntry)
    lfuEntry.index = p.Len()
    (*p) = append((*p), lfuEntry)
}
func (p *mypriority) Pop() interface{} {
    oldp := *p
    n := len(oldp)
    entry := oldp[n-1]
    oldp[n-1] = nil
    newp := oldp[:n-1]
    // 1 2 3 4 5 -> 2 3 4 5(索引 1 2 3 4) 更新为（0 1 2 3） 
    for i := 0; i < len(newp); i++ {
        newp[i].index = i
    }
    *p = newp
    return entry
}

type LFUCache struct {
    maxCacheSize int
    nSize        int
    m            map[int]*LfuEntry
    priority     *mypriority
}

func NewLFUCache(cachesize int) LFUCache {
    priority := make(mypriority, 0)
    return LFUCache{
        maxCacheSize: cachesize,
        m: make(map[int]*LfuEntry),
        priority: &priority,
    }
}

func NewLFUEntry(key, val int) *LfuEntry {
    return &LfuEntry{
        entry: entry{
            key: key,
            val: val,
            updatedAt: time.Now(),
        },
    }
}
func (l *LFUCache) Get(key int) int {
    if lfuEntry, ok := l.m[key]; ok {
        lfuEntry.touch()
        heap.Fix(l.priority, lfuEntry.index)
        return lfuEntry.entry.val
    }
    return -1
}

func (l *LFUCache) Put(key, val int) {
    if lfuEntry, ok := l.m[key]; ok {
        lfuEntry.touch()
        // index 节点 count 发生变化，调整堆
        heap.Fix(l.priority, lfuEntry.index)
        lfuEntry.entry.val = val
    } else {
        newLfuEntry := NewLFUEntry(key, val)
        newLfuEntry.touch()
        if l.nSize == l.maxCacheSize {
            l.Remove()
        }
        l.nSize++
        l.m[key] = newLfuEntry
        heap.Push(l.priority, newLfuEntry)
    }
}

func (l *LFUCache) Remove() {
        lfuEntry := heap.Pop(l.priority).(*LfuEntry)
        delete(l.m, lfuEntry.entry.key)
        l.nSize--
}

func (l *LfuEntry) touch() {
    l.count++
    l.entry.updatedAt = time.Now()
}

func LFU( operators [][]int ,  k int ) []int {
    // write code here
    lfu, ans := NewLFUCache(k), []int{}
    for _, operator := range operators {
        if operator[0] == 1 {
            lfu.Put(operator[1], operator[2])
        } else {
            ans = append(ans, lfu.Get(operator[1]))
        }
    }
    return ans
}