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

package main
import "time"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
type LFUCache struct {
	capacity      int
	keyToVal      map[int]int
	keyToFreq     map[int]int
	freqToKeys    map[int]map[int]bool
	minFreq       int
	keyToLastUsed map[int]time.Time
}

func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity:      capacity,
		keyToVal:      make(map[int]int),
		keyToFreq:     make(map[int]int),
		freqToKeys:    make(map[int]map[int]bool),
		minFreq:       0,
		keyToLastUsed: make(map[int]time.Time),
	}
}

func (this *LFUCache) Get(key int) int {
	if val, ok := this.keyToVal[key]; ok {
		this.IncreaseFreq(key)
		this.keyToLastUsed[key] = time.Now()
		return val
	}
	return -1
}

func (this *LFUCache) Put(key int, value int) {
	if this.capacity <= 0 {
		return
	}
	if _, ok := this.keyToVal[key]; ok {
		this.keyToVal[key] = value
		this.IncreaseFreq(key)
		this.keyToLastUsed[key] = time.Now()
		return
	}
	if len(this.keyToVal) >= this.capacity {
		this.RemoveMinFreqKey()
	}
	this.keyToVal[key] = value
	this.keyToFreq[key] = 1
	if _, ok := this.freqToKeys[1]; !ok {
		this.freqToKeys[1] = make(map[int]bool)
	}
	this.freqToKeys[1][key] = true
	this.minFreq = 1
	this.keyToLastUsed[key] = time.Now()
}

func (this *LFUCache) IncreaseFreq(key int) {
	freq := this.keyToFreq[key]
	delete(this.freqToKeys[freq], key)
	if len(this.freqToKeys[freq]) == 0 {
		delete(this.freqToKeys, freq)
		if this.minFreq == freq {
			this.minFreq++
		}
	}
	this.keyToFreq[key]++
	if _, ok := this.freqToKeys[this.keyToFreq[key]]; !ok {
		this.freqToKeys[this.keyToFreq[key]] = make(map[int]bool)
	}
	this.freqToKeys[this.keyToFreq[key]][key] = true
}

func (this *LFUCache) RemoveMinFreqKey() {
	keys := this.freqToKeys[this.minFreq]
	oldestTime := time.Now()
	var oldestKey int
	for key := range keys {
		if this.keyToLastUsed[key].Before(oldestTime) {
			oldestTime = this.keyToLastUsed[key]
			oldestKey = key
		}
	}
	delete(this.keyToVal, oldestKey)
	delete(this.keyToFreq, oldestKey)
	delete(this.keyToLastUsed, oldestKey)
	delete(this.freqToKeys[this.minFreq], oldestKey)
	if len(this.freqToKeys[this.minFreq]) == 0 {
		delete(this.freqToKeys, this.minFreq)
	}
}

func LFU(operators [][]int, k int) []int {
	cache := Constructor(k)
	var res []int
	for _, op := range operators {
		switch op[0] {
		case 1:
			cache.Put(op[1], op[2])
		case 2:
			res = append(res, cache.Get(op[1]))
		}
	}
	return res
}