goを使ってLRUを実現します
1599 ワード
データ構造を練習するいい問題です.Go文法を練習するために、30分以上繰り返しました.いくつかのピットを踏みました.elseは単独で一行に置くことができません.mapは初期化してから使えます.下記のように実現します.
双方向チェーンテーブルを構築し、ヘッドノードheadとエンドノードtailを確立しました.
eraseインターフェースとプッシュを実現しました.frontインターフェース
双方向チェーンテーブルを構築し、ヘッドノードheadとエンドノードtailを確立しました.
eraseインターフェースとプッシュを実現しました.frontインターフェース
type ListNode struct{
key int
val int
pre*ListNode
next*ListNode
}
type LRUCache struct {
vol int
ma map[int]*ListNode
head*ListNode// ,
tail*ListNode// ,
}
func Constructor(capacity int) LRUCache {
h:= ListNode{-1,0,nil,nil}
t:= ListNode{-1,0,nil,nil}
h.next = &t
t.pre = &h
lru:= LRUCache{capacity,make(map[int]*ListNode,capacity),&h,&t}
return lru
}
func (this*LRUCache) erase(cur*ListNode){
pre,next:= cur.pre,cur.next
pre.next,next.pre = next,pre
}
func (this*LRUCache) push_front(cur*ListNode){
prehead:= this.head.next
cur.next = prehead
cur.pre = this.head
prehead.pre = cur
this.head.next = cur
}
func (this *LRUCache) Get(key int) int {
cur,exist:= this.ma[key]
if(exist){
this.erase(cur)
this.push_front(cur)
return cur.val
}else{
return -1
}
}
func (this *LRUCache) Put(key int, value int) {
cur,exist:= this.ma[key]
if(exist){
cur.val = value
this.erase(cur)
this.push_front(cur)
}else{
if(len(this.ma) == this.vol){
tail:= this.tail.pre
this.erase(tail)
delete(this.ma,tail.key)
}
newNode :=ListNode{key,value,nil,nil}
this.ma[key] = &newNode
this.push_front(&newNode)
}
}