题解 | #LRU算法实现#

整个算法采用顺序编程的方式，主要是依靠字典a进行数据查找，依靠双向链表删除和插入与缓存数据相关的节点，缺陷是没有引入结构化编程的思想，优势是对于初学者来说相对直观。

func LRU( operators [][]int ,  k int ) []int {
	// write code here
	var get []int
	a:=make(map[int]int)
	var head *node
	var tail *node
    var pre  *node
    var point *node
	for _,v:=range operators{
		if v[0]==1{
			if len(a)<k{
				a[v[1]]=v[2]
			}else{
				delete(a,(*tail).Key)
				a[v[1]]=v[2]
				tail=(*tail).Pre
				(*tail).Next=nil
			}
			point=new(node)
			(*point).Key=v[1]
			if head ==nil{
				head=point
			}else{
				(*point).Next=head
				head.Pre=point
				head=point
			}
			for (*point).Next!=nil{
				point=(*point).Next
			}
			tail=point
		}else{
			if _,ok:=a[v[1]];ok{
				get=append(get,a[v[1]])
				point:=head
				for (*point).Key!=v[1]{
					point=(*point).Next
				}
				// remove point
				if point !=head{
                    pre=(*point).Pre
					if point!=tail{
						next:=(*point).Next
						(*next).Pre=pre
						(*pre).Next=next
					}else{
						pre.Next=nil
						tail=pre
					}
					// insert point to head
					(*head).Pre=point
                    (*point).Next=head
					(*point).Pre=nil
					head=point
				}
			}else{
				get=append(get,-1)
			}
		}
	}
	return get
}

type node struct {
	Key    int
	Pre    *node
	Next   *node
}