題目

請你為 最不經常使用（LFU）快取演算法設計並實現資料結構。它應該支援以下操作：get 和 put。

get(key) - 如果鍵存在於快取中，則獲取鍵的值（總是正數），否則返回 -1。

put(key, value) - 如果鍵已存在，則變更其值；如果鍵不存在，請插入鍵值對。

當快取達到其容量時，則應該在插入新項之前，使最不經常使用的項無效。

在此問題中，當存在平局（即兩個或更多個鍵具有相同使用頻率）時，應該去除最久未使用的鍵。

「項的使用次數」就是自插入該項以來對其呼叫 get 和 put 函式的次數之和。使用次數會在對應項被移除後置為 0 。

進階：你是否可以在 O(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

解題思路分析

1、雜湊+雙向連結串列；時間複雜度O(1)，空間複雜度O(n)

type Node struct {	key   int	value int	count int	next  *Node	prev  *Node}type LFUCache struct {	cap     int	minFreq int	kv      map[int]*Node	fk      map[int]*DoubleList}func Constructor(capacity int) LFUCache {	return LFUCache{		cap:     capacity,		kv:      make(map[int]*Node),		fk:      make(map[int]*DoubleList),		minFreq: 0,	}}func (this *LFUCache) Get(key int) int {	node, ok := this.kv[key]	if ok == false {		return -1	}	this.increaseFreq(node)	return node.value}func (this *LFUCache) Put(key int, value int) {	if this.cap <= 0 {		return	}	// 已經存在的key，修改並增加次數	node, ok := this.kv[key]	if ok {		node.value = value		this.increaseFreq(node)		return	}	if this.cap <= len(this.kv) {		last := this.remove()		delete(this.kv, last.key)	}	temp := &Node{		key:   key,		value: value,		count: 1,	}	this.kv[key] = temp	if this.fk[1] == nil {		this.fk[1] = NewDoubleList()	}	this.fk[1].Push(temp)	this.minFreq = 1 // 新插入的頻率為1}func (this *LFUCache) increaseFreq(node *Node) {	freq := node.count	this.fk[freq].Remove(node)	if this.fk[freq+1] == nil {		this.fk[freq+1] = NewDoubleList()	}	node.count++	this.fk[freq+1].Push(node)	if this.fk[freq].head.next == this.fk[freq].tail {		if freq == this.minFreq {			this.minFreq++		}	}	return}func (this *LFUCache) remove() *Node {	temp := this.fk[this.minFreq]	last := temp.tail.prev	temp.Remove(temp.tail.prev) // 刪除尾部節點	return last}type DoubleList struct {	head *Node	tail *Node}func NewDoubleList() *DoubleList {	node := &DoubleList{		head: &Node{},		tail: &Node{},	}	node.head.next = node.tail	node.tail.prev = node.head	return node}// 插入頭部func (this *DoubleList) Push(node *Node) {	next := this.head.next	node.next = next	node.prev = this.head	next.prev = node	this.head.next = node}// 刪除指定節點func (this *DoubleList) Remove(node *Node) {	node.prev.next = node.next	node.next.prev = node.prev	node.next = nil	node.prev = nil}

2、內建List；時間複雜度O(1)，空間複雜度O(n)

type Node struct {	key   int	value int	count int}type LFUCache struct {	cap     int	minFreq int	kv      map[int]*list.Element	fk      map[int]*list.List}func Constructor(capacity int) LFUCache {	return LFUCache{		cap:     capacity,		minFreq: 0,		kv:      make(map[int]*list.Element),		fk:      make(map[int]*list.List),	}}func (this *LFUCache) Get(key int) int {	node, ok := this.kv[key]	if ok == false {		return -1	}	return this.increaseFreq(node)}func (this *LFUCache) Put(key int, value int) {	data, ok := this.kv[key]	if ok {		node := data.Value.(*Node)		node.value = value		this.increaseFreq(data)		return	}	if this.cap == len(this.kv) {		cur, ok := this.fk[this.minFreq]		if ok == false {			return		}		deleteKey := cur.Front()		cur.Remove(deleteKey)		delete(this.kv, deleteKey.Value.(*Node).key)	}	temp := &Node{		key:   key,		value: value,		count: 1,	}	if _, ok := this.fk[1]; ok == false {		this.fk[1] = list.New()	}	res := this.fk[1].PushBack(temp)	this.kv[key] = res	this.minFreq = 1}func (this *LFUCache) increaseFreq(data *list.Element) int {	node := data.Value.(*Node)	cur, ok := this.fk[node.count]	if ok == false {		return -1	}	cur.Remove(data)	if cur.Len() == 0 && this.minFreq == node.count {		this.minFreq++	}	node.count++	if this.fk[node.count] == nil {		this.fk[node.count] = list.New()	}	res := this.fk[node.count].PushBack(node)	this.kv[node.key] = res	return node.value}

總結

Hard題目，經典的LFU題目，使用雙鏈表+雜湊，也可以使用內建list