解题思路#

单向/双向链表的各种操作烂熟于心

题解#

23.合并k个升序链表#

最直观的想法，每次遍历所有头节点，取出最小的，更新头节点切片，递归得到 时间复杂度$O(Lm)$ 空间复杂度$O(L)$ 递归来到了恐怖的L

这一题有$k<=10^4$是很影响时间复杂度的 考虑分治法，k个链表合并最终化为2个链表合并 时间复杂度$O(Llog(m))$ 空间复杂度$O(log(m))$

146.LRU缓存#

一道设计数据结构的题

首先要深刻理解题意，什么叫最久未使用，其实使用包括get，put操作

存储的是键值对，要求操作是O(1)的，我的想法是用切片存键值对？再用切片顺序储存最近使用？

不行的，因为用切片记录使用顺序无法实现O(1)的操作，因为要抽出的可能是切片中间的某个值

使用一个双向链表，自然地实现最近使用的逻辑， 只用把最近使用的放在链表开头，末尾就自然是最久未使用的

type LRUCache struct {
    Capacity int
    Data *list.List//双向链表
    Hash map[int]*list.Element //key映射到节点
}

注意各种操作的逻辑实现

对于这样的自定义数据结构，我们需要关注每一个字段在逻辑处理的时候是是否需要需要维护

这样才能让逻辑严谨

func (this *LRUCache) Get(key int) int {
    node := this.Hash[key] //取得element
	if node == nil {
		return -1
	}
	this.Data.MoveToFront(node)
	//不需要改变Hash表，因为移动节点其地址是不变的
	return node.Value.(pair).Value//注意类型断言 node.Value type is any
}

func (this *LRUCache) Put(key int, value int)  {
	//已经存在的情况
    node := this.Hash[key]
    if node != nil{
        this.Data.MoveToFront(node)
		this.Data.Front().Value = pair{key, value}
		return
    }
	//不存在的情况
	this.Data.PushFront(pair{key,value})
	this.Hash[key] = this.Data.Front()
	//逐出未使用的
	if len(this.Hash) > this.Capacity {
		this.Hash[this.Data.Back().Value.(pair).Key] = nil
        this.Data.Remove(this.Data.Back())
	}
}