leetcode LRU Cache Golang

allenhaozi · · 663 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

package main

import(
	"fmt"
)

type Node struct {
	Key string
	Val string
	Pre *Node
	Next *Node

}

type DLinkedList struct {
	Head *Node
	Tail *Node
}

func (self *DLinkedList) IsEmpty() bool {
	if self.Head == nil && self.Tail == nil {
		return true
	} else {
		return false
	}
}

func (self *DLinkedList) RemoveLast() {
	if self.Tail != nil {
		self.Remove(self.Tail)
	}
}

func (self *DLinkedList) Remove(n *Node){
	if self.Tail == self.Head {
		self.Head = nil
		self.Tail = nil
		return
	}
	if n == self.Head {
		n.Next.Pre = nil
		self.Head = n.Next
		return
	}
	if n == self.Tail {
		n.Pre.Next = nil
		self.Tail = n.Pre
		return
	}
	n.Pre.Next = n.Next
	n.Next.Pre = n.Pre
}

func (self *DLinkedList) AddFirst(n *Node) {
	if self.Head == nil {
		self.Head = n
		self.Tail = n
		n.Pre = nil
		n.Next = nil
		return
	}
	n.Next = self.Head
	self.Head.Pre = n
    self.Head = n
    n.Pre = nil

}

type LRUCache struct {
	Cap int
	Size int
	HashMap map[string]*Node
	Cache *DLinkedList
}

func (self *LRUCache) Get(k string) string {
	if node,ok := self.HashMap[k]; ok {
		self.Cache.Remove(node)
		self.Cache.AddFirst(node)
		return node.Val
	} else {
		return ""
	}
}

func (self *LRUCache) Set(k,val string ) {
	if 	node,ok := self.HashMap[k];ok {
		self.Cache.Remove(node)
		node.Val = val
		self.Cache.AddFirst(node)
	} else {
		n := &Node{Key:k,Val:val}
		self.HashMap[k] = n
		self.Cache.AddFirst(n)
		self.Size = self.Size + 1
		if self.Size > self.Cap {
			self.Size = self.Size - 1
			delete(self.HashMap,self.Cache.Tail.Key)
			self.Cache.RemoveLast()
		}
	}
}

func main() {

	cache := new(LRUCache)
	cache.Cap = 3
	cache.HashMap = make(map[string]*Node,0)
	cache.Cache = new(DLinkedList)

	cache.Set("allen","value")
	cache.Set("a","value")
	cache.Set("b","value")
	cache.Set("c","value")

	test := cache.Get("allen")

	fmt.Println(test)
	fmt.Println(cache.HashMap)
	fmt.Println(cache.Cache)
	fmt.Println(cache.Size)

}

  


有疑问加站长微信联系(非本文作者)

本文来自:博客园

感谢作者:allenhaozi

查看原文:leetcode LRU Cache Golang

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

663 次点击  
加入收藏 微博
0 回复
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传