Go 算法和数据结构

刷题过程中会遇到一些通用数据结构的封装,在这里记录一下。注意因为是刷算法题用的,没有考虑 goroutine 安全, 不要直接用在并发环境,如果是在生产环境中使用请加锁改造。(没有泛型写起来挺繁琐的)

Stack 

typeStackstruct{
st[]int
}
funcNewStack()*Stack{
return&Stack{st:make([]int,0)}
}
func(s*Stack)Push(xint){
s.st=append(s.st,x)
}
func(s*Stack)Peek()int{
returns.st[len(s.st)-1]
}
func(s*Stack)Pop()int{
n:=len(s.st)
top:=s.st[n-1]
s.st=s.st[:n-1]
returntop
}
func(s*Stack)Empty()bool{
returnlen(s.st)==0
}

Queue 

typeItemstruct{
Numint
Orderint
}
typeQueuestruct{
items[]Item
}
funcNewQueue()*Queue{
return&Queue{
items:make([]Item,0),
}
}
func(q*Queue)Push(xItem){
q.items=append(q.items,x)
}
func(q*Queue)Pop()Item{
x:=q.items[0]
q.items=q.items[1:]
returnx
}
func(q*Queue)Front()Item{
returnq.items[0]
}
func(q*Queue)End()Item{
returnq.items[len(q.items)-1]
}
func(q*Queue)Empty()bool{
returnlen(q.items)==0
}

Deque 双端队列 

import(
"container/list"
"fmt"
)
// 滑动窗口最大值
typeDequestruct{
ll*list.List
}
funcNewDeque()*Deque{
return&Deque{ll:list.New()}
}
func(dq*Deque)PushFront(xint){
dq.ll.PushFront(x)
}
func(dq*Deque)PushBack(xint){
dq.ll.PushBack(x)
}
func(dq*Deque)Pop(){// remove back
dq.ll.Remove(dq.ll.Back())
}
func(dq*Deque)PopFront(){// remove first
dq.ll.Remove(dq.ll.Front())
}
func(dq*Deque)Front()int{
returndq.ll.Front().Value.(int)
}
func(dq*Deque)Back()int{
returndq.ll.Back().Value.(int)
}
func(dq*Deque)Len()int{
returndq.ll.Len()
}

Linked List 

packagemain
import"fmt"
// 测试链表。在 redigo 里边使用到了链表作为 pool 的实现
typeIntListstruct{
countint
// front,back 分别指向第一个和最后一个 node,或者是 nil。front.prev back.next 都是空
front,back*Node
}
// 链表节点
typeNodestruct{
next,prev*Node
}
func(l*IntList)Count()int{
returnl.count
}
func(l*IntList)pushFront(node*Node){
node.next=l.front
node.prev=nil
ifl.count==0{// note when list is empty
l.back=node
}else{
l.front.prev=node
}
l.front=node
l.count++
}
func(l*IntList)popFront(){
first:=l.front
l.count--
ifl.count==0{
l.front,l.back=nil,nil
}else{
first.next.prev=nil
l.front=first.next
}
first.next,first.prev=nil,nil// clear first
}
func(l*IntList)popBack(){
last:=l.back
l.count--
ifl.count==0{
l.front,l.back=nil,nil
}else{
last.prev.next=nil
l.back=last.prev
}
last.prev,last.next=nil,nil
}
func(l*IntList)Print(){
cur:=l.front
forcur!=l.back{
fmt.Println(cur)
cur=cur.next
}
ifl.back!=nil{
fmt.Println(l.back)
}
}

Trie 字典树 

// Package main provides ...
packagemain
import"fmt"
// https://golangbyexample.com/trie-implementation-in-go/
const(
ALBHABET_SIZE=26
)
typenodestruct{
childrens[ALBHABET_SIZE]*node
isWordEndbool
}
typetriestruct{
root*node
}
funcnewTrie()*trie{
return&trie{
root:&node{},
}
}
func(t*trie)insert(wordstring){
wordLength:=len(word)
current:=t.root
fori:=0;i<wordLength;i++{
idx:=word[i]-'a'
ifcurrent.childrens[idx]==nil{
current.childrens[idx]=&node{}
}
current=current.childrens[idx]
}
current.isWordEnd=true
}
func(t*trie)find(wordstring)bool{
wordLength:=len(word)
current:=t.root
fori:=0;i<wordLength;i++{
idx:=word[i]-'a'
ifcurrent.childrens[idx]==nil{
returnfalse
}
current=current.childrens[idx]
}
ifcurrent.isWordEnd{
returntrue
}
returnfalse
}
funcmain(){
trie:=newTrie()
words:=[]string{"zhang","wang","li","zhao"}
fori:=0;i<len(words);i++{
trie.insert(words[i])
}
toFind:=[]string{"zhang","wang","li","zhao","gong"}
fori:=0;i<len(toFind);i++{
c:=toFind[i]
iftrie.find(c){
fmt.Printf("word[%s] found in trie.\n",c)
}else{
fmt.Printf("word[%s] not found in trie\n",c)
}
}
}

Lru Cache (不是并发安全的,仅示例) 

packagemain
import"container/list"
typeLRUCachestruct{
lis*list.List
mmap[int]*list.Element
capacityint
}
// 包装成一个 struct
typeKVstruct{
Keyint
Valint
}
funcConstructor(capacityint)LRUCache{
returnLRUCache{
lis:list.New(),
m:make(map[int]*list.Element),
capacity:capacity,
}
}
func(this*LRUCache)Get(keyint)int{
ifele,ok:=this.m[key];ok{
this.lis.MoveToFront(ele)
returnele.Value.(*KV).Val
}
return-1
}
func(this*LRUCache)Put(keyint,valueint){
ifele,ok:=this.m[key];ok{
ele.Value.(*KV).Val=value
this.lis.MoveToFront(ele)
return
}
ele:=this.lis.PushFront(&KV{key,value})
this.m[key]=ele// map 保存的是 节点信息
ifthis.lis.Len()>this.capacity{
back:=this.lis.Back()
delete(this.m,back.Value.(*KV).Key)
this.lis.Remove(back)
}
}

OrderedMap (类似 python collections.OrderedDict)

模拟 python collections.OrderedDict 写的,可以方便的实现 lru 等。注意这里的 order 指的是 key 插入的顺序,不是指 key 字典序。

packagemain
import(
"container/list"
"fmt"
)
// 按照 key 插入顺序遍历 map,类似 python collections.OrderedDict。注意不是 key 的字典序,而是插入顺序
typeOrderedMapstruct{
mmap[string]int
memap[string]*list.Element
ll*list.List// 记录 key order
}
funcNewOrderedMap()*OrderedMap{
return&OrderedMap{
m:make(map[string]int),
me:make(map[string]*list.Element),
ll:list.New(),
}
}
func(o*OrderedMap)Set(kstring,vint){
if_,found:=o.m[k];!found{
e:=o.ll.PushBack(k)
o.me[k]=e
}
o.m[k]=v
}
func(o*OrderedMap)Exist(kstring)bool{
_,found:=o.m[k]
returnfound
}
func(o*OrderedMap)Get(kstring)int{
returno.m[k]
}
func(o*OrderedMap)Delete(kstring){
delete(o.m,k)
node:=o.me[k]
o.ll.Remove(node)
delete(o.me,k)
}
func(o*OrderedMap)Len()int{
returnlen(o.m)
}
// 按照 key 进入顺序返回
func(o*OrderedMap)Keys()[]string{
keys:=make([]string,o.ll.Len())
i:=0
fore:=o.ll.Front();e!=nil;e=e.Next(){
keys[i]=e.Value.(string)
i++
}
returnkeys
}

Heap 堆

go 自带了一个 container/heap 模块可以用来实现堆。

// This example demonstrates an integer heap built using the heap interface.
// A heap is a tree with the property that each node is the minimum-valued node in its subtree.
// 可以用来实现优先级队列 priority queue
packagemain
import(
"container/heap"
"fmt"
)
// An IntHeap is a min-heap of ints.
typeIntHeap[]int
func(hIntHeap)Len()int{returnlen(h)}
func(hIntHeap)Less(i,jint)bool{returnh[i]<h[j]}
func(hIntHeap)Swap(i,jint){h[i],h[j]=h[j],h[i]}
// 最后追加一个元素
func(h*IntHeap)Push(xinterface{}){
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h=append(*h,x.(int))
}
// 移除并且返回最后一个元素
func(h*IntHeap)Pop()interface{}{
old:=*h
n:=len(old)
x:=old[n-1]
*h=old[0:n-1]
returnx
}
// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
funcmain(){
h:=&IntHeap{2,1,5}
heap.Init(h)
fmt.Println(h)
heap.Push(h,3)
fmt.Println(h)
fmt.Printf("minimum: %d\n",(*h)[0])// h[0] 最小的元素
forh.Len()>0{
fmt.Printf("%d ",heap.Pop(h))
}
}

参考: