leetcode LRU Cache Golang

栏目: 编程工具 · 发布时间: 6年前

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)

}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

智能Web算法

智能Web算法

Haralambos Marmanis、Dmitry Babenko / 阿稳、陈钢 / 电子工业出版社 / 2011-11 / 65.00元

本书涵盖了五类重要的智能算法:搜索、推荐、聚类、分类和分类器组合,并结合具体的案例讨论了它们在Web应用中的角色及要注意的问题。除了第1章的概要性介绍以及第7章对所有技术的整合应用外,第2~6章以代码示例的形式分别对这五类算法进行了介绍。 本书面向的是广大普通读者,特别是对算法感兴趣的工程师与学生,所以对于读者的知识背景并没有过多的要求。本书中的例子和思想应用广泛,所以对于希望从业务角度更好......一起来看看 《智能Web算法》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具