146. LRU缓存机制

题意：

解题思路：

思路：LRU (最近最少使用)
1. 初始化容量，cache，大小；
2. 获取key时，如果存在key，则先取出，然后删除对应的key，同时将元素插入在数组的最前面；
3. 插入值时，如果缓存中存在要插入的key，则删除对应的key，同时将新的key前移[即插在数组最前面]；
4. 如果不存在，则先判断容量，如果超出最大容量值，则先删除数组末尾元素[末尾元素代表最近很少使用]对应的key，如果为['a'=>'','b' => '','c' => '']则删除a对应的元素值,再将元素插入在数组最前面['b' => '','c' => '','a'=>'']

PHP代码实现：

class LRUCache {
    private $capacity;
    private $size;
    private $cache = [];
    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->capacity = $capacity;
    }
    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (isset($this->cache[$key])) {
            $value = $this->cache[$key];
            unset($this->cache[$key]);
            $this->cache[$key] = $value;
            return $value;
        }
        return -1;
    }
    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        if (isset($this->cache[$key])) {
            unset($this->cache[$key]);
            $this->cache[$key] = $value;
        } else {
            if ($this->size < $this->capacity) {
                $this->size++;
            } else {
                $curKey = key($this->cache);
                unset($this->cache[$curKey]);
            }
            $this->cache[$key] = $value;
        }
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * $obj = LRUCache($capacity);
 * $ret_1 = $obj->get($key);
 * $obj->put($key, $value);
 */

GO代码实现：

type LRUCache struct {
    Cap  int
    Map  map[int]*Node
    Head *Node
    Last *Node
}
type Node struct {
    Val  int
    Key  int
    Pre  *Node
    Next *Node
}
func Constructor(capacity int) LRUCache {
    cache := LRUCache{
        Cap:  capacity,
        Map:  make(map[int]*Node, capacity),
        Head: &Node{},
        Last: &Node{},
    }
    cache.Head.Next = cache.Last
    cache.Last.Pre = cache.Head
    return cache
}
func (this *LRUCache) Get(key int) int {
    node, ok := this.Map[key]
    if !ok {
        return -1
    }
    this.remove(node)
    this.setHeader(node)
    return node.Val
}
func (this *LRUCache) Put(key int, value int) {
    node, ok := this.Map[key]
    if ok {
        this.remove(node)
    } else {
        if len(this.Map) == this.Cap {
            delete(this.Map, this.Last.Pre.Key)
            this.remove(this.Last.Pre)
        }
        node = &Node{Val: value, Key: key}
        this.Map[node.Key] = node
    }
    node.Val = value
    this.setHeader(node)
}
func (this *LRUCache) setHeader(node *Node) {
    this.Head.Next.Pre = node
    node.Next = this.Head.Next
    this.Head.Next = node
    node.Pre = this.Head
}
func (this *LRUCache) remove(node *Node) {
    node.Pre.Next = node.Next
    node.Next.Pre = node.Pre
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */