Leetcode - lru-cache

https://leetcode.com/problems/lru-cache/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Use double-linked list for the data structure. Maintain a hash to store key-value pairs. When a key-value pair put in the cache, if it already exists, move it to the head, otherwise create it and move it to the head. Once it's over-capacity, remove the tail.

type ListNode struct {
	Key  int
	Val  int
	Prev *ListNode
	Next *ListNode
}

type LRUCache struct {
    Hash map[int]*ListNode
    Len  int
    Capacity int
    Head *ListNode
    Tail *ListNode
}

func Constructor(capacity int) LRUCache {
    head := &ListNode{}
    tail := &ListNode{}
    head.Next = tail
    tail.Prev = head
    return LRUCache{
        Hash: map[int]*ListNode{},
        Len: 0,
        Capacity: capacity,
        Head: head,
        Tail: tail,
    }
}


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

    val, ok := this.Hash[key]
    if !ok {
        return -1
    }
    this.moveToHead(val)
    return val.Val
}


func (this *LRUCache) Put(key int, value int)  {
    val, ok := this.Hash[key]
    if ok {
        val.Val = value
        this.moveToHead(val)
        return
    }
    this.Len++
    if this.Len > this.Capacity {
        this.removeTail()
        this.Len--
    }

    node := &ListNode{
        Key: key,
        Val: value,
        Prev: this.Head,
        Next: this.Head.Next,
    }
    node.Next.Prev = node
    this.Head.Next = node
    this.Hash[key] = node
}

func (this *LRUCache) moveToHead(node *ListNode) {
    if node == this.Head.Next {
        return
    }
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev

    node.Prev = this.Head
    node.Next = this.Head.Next
    this.Head.Next = node
    node.Next.Prev = node
}

func (this *LRUCache) removeTail() {
    node := this.Tail.Prev
    node.Prev.Next = this.Tail
    this.Tail.Prev = node.Prev
    delete(this.Hash, node.Key)
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

• 相关文章
• 全局相关文章