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

package main

import (
	"container/heap"
	"time"
)

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * lfu design
 * @param operators int整型二维数组 ops
 * @param k int整型 the k
 * @return int整型一维数组
 */
func LFU(operators [][]int, k int) []int {
	cache := Constructor(k)
	var result []int
	for _, op := range operators {
		switch op[0] {
		case 1: // set操作
			cache.Set(op[1], op[2])
		case 2: // get操作
			result = append(result, cache.Get(op[1]))
		}
	}
	return result
}

// lfuCacheItem 表示缓存中的一个条目
type lfuCacheItem struct {
	key       int
	value     int
	frequency int
	timestamp time.Time
	index     int // 堆中的索引
}

// lfuHeap 实现了一个最小堆
type lfuHeap []*lfuCacheItem

func (h lfuHeap) Len() int { return len(h) }
func (h lfuHeap) Less(i, j int) bool { // 优先比较频率，然后比较时间戳
	return h[i].frequency < h[j].frequency || (h[i].frequency == h[j].frequency && h[i].timestamp.Before(h[j].timestamp))
}
func (h lfuHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	h[i].index = i
	h[j].index = j
}
func (h *lfuHeap) Push(x interface{}) {
	n := len(*h)
	item := x.(*lfuCacheItem)
	item.index = n
	*h = append(*h, item)
}
func (h *lfuHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	item.index = -1 // for safety
	*h = old[0 : n-1]
	return item
}

// LFUCache 是LFU缓存的主结构
type LFUCache struct {
	capacity int
	items    map[int]*lfuCacheItem
	heap     lfuHeap
}

// Constructor 创建一个新的LFU缓存
func Constructor(capacity int) LFUCache {
	return LFUCache{
		capacity: capacity,
		items:    make(map[int]*lfuCacheItem),
		heap:     make(lfuHeap, 0, capacity),
	}
}

// Get 从缓存中获取一个值
func (cache *LFUCache) Get(key int) int {
	if item, exists := cache.items[key]; exists {
		item.frequency++
		item.timestamp = time.Now()
		heap.Fix(&cache.heap, item.index)
		return item.value
	}
	return -1
}

// Set 向缓存中插入一个值
func (cache *LFUCache) Set(key int, value int) {
	if cache.capacity == 0 {
		return
	}
	if item, exists := cache.items[key]; exists {
		item.value = value
		item.frequency++
		item.timestamp = time.Now()
		heap.Fix(&cache.heap, item.index)
		return
	}
	if len(cache.items) == cache.capacity {
		// 移除使用频率最低且时间戳最早的条目
		removed := heap.Pop(&cache.heap).(*lfuCacheItem)
		delete(cache.items, removed.key)
	}
	// 添加新条目
	newItem := &lfuCacheItem{
		key:       key,
		value:     value,
		frequency: 1,
		timestamp: time.Now(),
	}
	cache.items[key] = newItem
	heap.Push(&cache.heap, newItem)
}