2021-01-23：LFU手擼，說下時間複雜度和空間複雜度。

福哥答案2021-01-23：

這道題複雜度太高，短時間內很難寫出來。面試的時候不建議手撕程式碼。

一個存節點的map+一個存桶的map+一個存桶的雙向連結串列。桶本身也是一個雙向連結串列。

存節點的map：key是鍵，value是節點。

存桶的map：key是次數，value是桶。

程式碼用golang編寫，程式碼如下：

package mainimport (    "container/list"    "fmt")func main() {    cache := Constructor(2)    cache.Put(1, 1)    cache.Put(2, 2)    cache.Get(1)    // 返回 1    cache.Put(3, 3) // 去除鍵 2    cache.Get(2)    // 返回 -1（未找到）    cache.Get(3)    // 返回 3    cache.Put(4, 4) // 去除鍵 1    cache.Get(1)    // 返回 -1（未找到）    cache.Get(3)    // 返回 3    cache.Get(4)    // 返回 4}type LFUCache struct {    Cap int    Len int    //map快取，鍵存key，值存kv和前後    KeyCache map[int]*list.Element //key存鍵，value存節點    List *list.List    FreqCache map[int]*list.Element //key存次數，value存桶}func Constructor(capacity int) LFUCache {    ret := LFUCache{}    ret.Cap = capacity    ret.KeyCache = make(map[int]*list.Element)  //元素存節點    ret.FreqCache = make(map[int]*list.Element) //元素存桶    ret.List = list.New()    return ret}func (this *LFUCache) Get(key int) int {    //已經找到當前元素了    v := this.KeyCache[key]    if v == nil {        fmt.Println(-1)        return -1    }    //移動    this.curNodeMoveToNextBucket(v)    //返回當前元素的值    fmt.Println(v.Value.([]int)[1])    return v.Value.([]int)[1]}//當前節點移動到下一個桶func (this *LFUCache) curNodeMoveToNextBucket(v *list.Element) {    //根據當前節點的次數找到當前桶    curbucket := this.FreqCache[v.Value.([]int)[2]]    //找下一桶，找不到建立新桶    nextbucket := this.FreqCache[v.Value.([]int)[2]+1]    if nextbucket == nil {        nextbucket = this.List.InsertAfter(list.New(), curbucket)        this.FreqCache[v.Value.([]int)[2]+1] = nextbucket    }    //把當前節點放在下一桶裡    //nextbucket.Value.(*list.List).PushBack(v.Value)，這樣的程式碼，leetcode不能透過。原因是元素移動後，已經不是以前的元素了。所以map需要重新賦值。這個錯誤，我花了1個小時才找到，請謹慎。    this.KeyCache[v.Value.([]int)[0]] = nextbucket.Value.(*list.List).PushBack(v.Value)    //當前桶刪除當前節點    curbucket.Value.(*list.List).Remove(v)    //如果當前桶為空，直接刪除當前桶。    if curbucket.Value.(*list.List).Len() == 0 {        this.List.Remove(curbucket)        delete(this.FreqCache, v.Value.([]int)[2])    }    //當前節點次數加1    v.Value.([]int)[2]++}func (this *LFUCache) Put(key int, value int) {    if this.Cap == 0 {        return    }    if v, ok := this.KeyCache[key]; ok { //快取裡有        //修改值        v.Value.([]int)[1] = value        //移動        this.curNodeMoveToNextBucket(v)    } else { //快取裡沒有        if this.Len == this.Cap {            //獲取可能需要刪除的桶            deleteBucket := this.List.Front()            //獲取需要刪除的元素            deleteE := deleteBucket.Value.(*list.List).Front()            //刪除元素            delete(this.KeyCache, deleteE.Value.([]int)[0])            deleteBucket.Value.(*list.List).Remove(deleteE)            //可能需要刪除的桶如果沒有元素，刪除桶。並且需要刪除的元素的次數不是1            if deleteBucket.Value.(*list.List).Len() == 0 {                this.List.Remove(deleteBucket)                delete(this.FreqCache, deleteE.Value.([]int)[2])            }        } else {            this.Len++        }        //獲取次數為1的桶        oneTimeBucket := this.FreqCache[1]        //獲取不到就建立桶        if oneTimeBucket == nil {            oneTimeBucket = this.List.PushFront(list.New())            this.FreqCache[1] = oneTimeBucket        }        this.KeyCache[key] = oneTimeBucket.Value.(*list.List).PushBack([]int{key, value, 1})    }}

執行結果如下：

***