3.训练go的container

go刷题带来的思考【少即是多】

感觉4个广义的数据结构即可

• slice【数组, 比如模拟栈, 队列】
• map【映射or字典】
• container/list【双向链表,比如模拟：队列、栈、双端队列】
• container/heap【主要是堆，解决topk】

1.实战container/list

• 1, 需要记忆的是, go的list里面的元素其实是个Element, 我们自己定义的list要存什么结构体其实是放在Element下面的Value中的(因为他是any类型) ( ⚠️⚠️一定注意⚠️⚠️)
  • 所以, 写代码的时候大概要写断言!

type Element struct {
    // 元素保管的值
    Value any // 这个就是[你以后做题的核心, 你要给这个list存什么样的节点]
    // 内含隐藏或非导出字段
}

• 2,往list中插入元素可以分2个方向( 但是要注意! 你插入的元素, 其实是那个Element下面的any类型的Value ) ( ⚠️⚠️一定注意⚠️⚠️)
  • func (l *List) PushFront(v any) *Element
  • func (l *List) PushBack(v any) *Element
• 3, go的双链表, 获取前后元素
  • func (l *List) Back() *Element
  • func (l *List) Front() *Element
• 4, go和C++之类的一样, 是可以删除链表节点的
  • func (l *List) Remove(e *Element) any
• 5, go比C++实现LRU和LFU啥的能精简代码的原因是有这2个函数 ( ⚠️⚠️一定注意⚠️⚠️)
  • MoveToFront将元素e移动到链表的第一个位置，如果e不是l的元素，l不会被修改。
    • func (l *List) MoveToFront(e *Element)
  • MoveToBack将元素e移动到链表的最后一个位置，如果e不是l的元素，l不会被修改。
    • func (l *List) MoveToBack(e *Element)

LRU算法实现

• LRU的题目使用了container包的list
• 0x3f的LRU题解

//  ( ⚠️⚠️一定注意⚠️⚠️)
// 后边list.Element的Value那个any可以就是这样的1个结构体类型
type HelpListNode struct {
    Key int // 其Key, 唯一用途,用于删掉map
    Value int // 真正的值
}

type LRUCache struct {
	//  ( ⚠️⚠️一定注意⚠️⚠️ 注意是list.Element哈! )
    InnerMap map[int]*list.Element // 从key映射到链表的节点 
    Queue *list.List   
    CurLen int // 当前Queue的实际长度
    LimitLen int // Queue预设的最大长度
}


func Constructor(capacity int) LRUCache {
    queue := list.New()
    ret := LRUCache {
        // 因为container/list的Element元素里面的任何元素都是any
        InnerMap : map[int]*list.Element{},
        Queue : queue,
        CurLen : 0,
        LimitLen : capacity,
    }
    return ret
}


func (this *LRUCache) Get(key int) int {
    node, ok := this.InnerMap[key]
    if !ok {
        return -1
    }
    // 需要断言
    ret := node.Value.(HelpListNode).Value
    
    // 需要断言!
    assertNode := node
    this.Queue.MoveToFront(assertNode)
    return ret
}


func (this *LRUCache) Put(key int, value int)  {
    if elem, ok := this.InnerMap[key]; ok {
        // 更新已存在的节点
        elem.Value = HelpListNode{
            Key: key,
            Value: value,
        }
        this.Queue.MoveToFront(elem)
        return
    }

    if this.CurLen == this.LimitLen {
        // 删除最久未使用的节点（队尾）
        oldest := this.Queue.Back()
        if oldest != nil {
            oldNode := oldest.Value.(HelpListNode)
            delete(this.InnerMap, oldNode.Key)
            this.Queue.Remove(oldest)
        }
        // CurLen保持不变，因为会添加新节点
    } else {
        this.CurLen++
    }

    // 添加新节点到队首
    newNode := HelpListNode{
        Key: key,
        Value: value,
    }
    element := this.Queue.PushFront(newNode)
    this.InnerMap[key] = element
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

LFU的算法实现

• 460. LFU 缓存