leetcode-146 LRU缓存机制

146. LRU缓存机制

难度: 中等

---

type LRUCache struct {

    head,tail *Node
    Keys map[int]*Node
    Cap int
}

type Node struct {
    Key,Val int
    Prev,Next *Node
}


func Constructor(capacity int) LRUCache {
    return LRUCache{Keys:make(map[int]*Node),Cap:capacity}

}


func (this *LRUCache) Get(key int) int {

    	if node, ok := this.Keys[key]; ok {
		this.Remove(node)
		this.Add(node)
		return node.Val
	}
	return -1

}


func (this *LRUCache) Put(key int, value int)  {
	if node, ok := this.Keys[key]; ok {
		node.Val = value
		this.Remove(node)
		this.Add(node)
		return
	} else {
		node = &Node{Key: key, Val: value}
		this.Keys[key] = node
		this.Add(node)
	}
	if len(this.Keys) > this.Cap {
		delete(this.Keys, this.tail.Key)
		this.Remove(this.tail)
	}
}



func (this *LRUCache) Add(node *Node) {
	node.Prev = nil
	node.Next = this.head
	if this.head != nil {
		this.head.Prev = node
	}
	this.head = node
	if this.tail == nil {
		this.tail = node
		this.tail.Next = nil
	}
}

func (this *LRUCache) Remove(node *Node) {
	if node == this.head {
		this.head = node.Next
		node.Next = nil
		return
	}
	if node == this.tail {
		this.tail = node.Prev
		node.Prev.Next = nil
		node.Prev = nil
		return
	}
	node.Prev.Next = node.Next
	node.Next.Prev = node.Prev
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

---

LRU算法浅析

go实现LRU cache

文章目录

原文链接: https://dashen.tech/2015/03/01/leetcode-146-LRU缓存机制/

版权声明: 转载请注明出处.