Design - 146. LRU Cache

146. 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

思路：

题目要求实现一个LRU Cache，提供get和put方法，时间复杂度都控制在O(1)，get操作要求时间复杂度为O(1)，说明肯定有一个hash的结构用来查找，put方法也是O(1)可以使用链表，这里使用双向链表，实现删除最后一个元素和把元素移动到链表头。对于链表类题目，最好的就是使用dummy节点，这样可以避免很多空针或者断链的情况发生。

代码：

go：

type LRUCache struct {
    idxMap map[int]*node
    size    int
    capacity int
    head, tail *node
}

type node struct {
    key, value int
    next *node
    prev *node
}

func Constructor(capacity int) LRUCache {
    lru := LRUCache{
        idxMap: make(map[int]*node, capacity),
        capacity: capacity,
        size : 0,
        head: &node{},
        tail: &node{},
    }
    
    lru.head.next = lru.tail
    lru.tail.prev = lru.head
    return lru
}

func (this *LRUCache) moveToHead(obj *node) {
    obj.prev.next = obj.next
    obj.next.prev = obj.prev
    
    this.insertToHead(obj)
}

func (this *LRUCache) insertToHead(obj *node) {
    tmp := this.head.next
    
    obj.next = this.head.next
    this.head.next = obj
    
    obj.prev = this.head
    tmp.prev = obj 
}

func (this *LRUCache) removeTail() (last *node) {
    last = this.tail.prev
    
    last.prev.next = last.next
    last.next.prev = last.prev
    
    last.next = nil
    last.prev = nil
    
    return last
}

func (this *LRUCache) Get(key int) int {
    var obj *node
    if val, ok := this.idxMap[key]; !ok {
        return -1
    } else {
        obj = val
    }
    
    // 调整key节点到head
    this.moveToHead(obj)
    return obj.value
}


func (this *LRUCache) Put(key int, value int)  {
    if target, ok := this.idxMap[key]; !ok {
        // check capacity
        if this.size == this.capacity {
            tail := this.removeTail()
            delete(this.idxMap, tail.key)
            this.size--
        }
        
        obj := &node{
            key: key,
            value:value,
        }
        this.insertToHead(obj)
        this.idxMap[obj.key] = obj
        this.size++
    } else {
        target.value = value
        this.moveToHead(target)
    }
}


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