Skip to content

Latest commit

 

History

History
172 lines (145 loc) · 5.38 KB

146.md

File metadata and controls

172 lines (145 loc) · 5.38 KB
Raw

✏️Leetcode基础刷题之(146. LRU Cache)

2019-09-010146 吴亲库里 库里的深夜食堂

✏️描述

实现一个LRU缓存淘汰机制，支持get和put两个操作。什么是LRU缓存淘汰，简单的说遵循最近最少使用的原则。就像是你搬家，东西不能全部带去，那么最后你肯定会把最少使用，最近最少使用的丢下。如果是最新使用过的东西，那么他肯定会入你法眼，在挑选的时候也会优先选择。ps:我搬家从来都只需要一步Maxc即可。

✏️题目实例

​

✏️题目分析

对于LRU缓存淘汰算法，这里是基于链表实现的。对于get操作，如果不存在缓存中，直接返回-1,如果存在的话，当前我们又是在get他，那么我们就需要把当前的缓存节点转移到存储的最前方，也就是链表的头部。说明它最近刚被调用过。如果是put操作，首先我们需要判断当前缓存的空间是否满了，如果满了，说明我需要给新来的腾出位置，那么腾出来的位置当然就是最近最少使用的元素。所以这里就分为两步，第一步是判断当前键是否已在缓存中存在或者缓存是否已满，如果是键存在，那么需要删除缓存中对应的键值，如果是缓存位置已满，那么也需要删除对应最近最少使用节点，删除的过程其实就是在遍历链表，需要注意调整当前节点前后指针指向位置，第二步就是把当前要put的节点插入到链表的头部,即可。

class LRUCache {
    private $capacity;
    private $list;
    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->capacity=$capacity;
        $this->list=new HashList();
        
    }
  
    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if($key<0) return -1;
        return $this->list->get($key);
    }
  
    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        $size=$this->list->size;
        $isHas=$this->list->checkIndex($key);
        if($isHas || $size+1 > $this->capacity){
            $this->list->removeNode($key);
        }
        $this->list->addAsHead($key,$value);
    }
}



class HashList{
    public $head;
    public $tail;
    public $size;
    public $buckets=[];
    public function __construct(Node $head=null,Node $tail=null){
        $this->head=$head;
        $this->tail=$tail;
        $this->size=0;
    }
    
    //检查键是否存在
    public function checkIndex($key){
        $res=$this->buckets[$key];
        if($res){
            return true;
        }
        return false;
    }
    
    public function get($key){
        $res=$this->buckets[$key];
        if(!$res) return -1;
        $this->moveToHead($res);
        return $res->val;
    }
    
    //新加入的节点
    public function addAsHead($key,$val)
    {
        $node=new Node($val);
        if($this->tail==null && $this->head !=null){
            $this->tail=$this->head;
            $this->tail->next=null;
            $this->tail->pre=$node;
        }
        $node->pre=null;
        $node->next=$this->head;
        $this->head->pre=$node;
        $this->head=$node;
        $node->key=$key;
        $this->buckets[$key]=$node;
        $this->size++;
    }
    
    //移除指针(已存在的键值对或者删除最近最少使用原则)
    public function removeNode($key)
    {
        $current=$this->head;
        for($i=1;$i<$this->size;$i++){
            if($current->key==$key) break;
            $current=$current->next;
        }
        unset($this->buckets[$current->key]);
        //调整指针
        if($current->pre==null){
            $current->next->pre=null;
            $this->head=$current->next;
        }else if($current->next ==null){
            $current->pre->next=null;
            $current=$current->pre;
            $this->tail=$current;
        }else{
            $current->pre->next=$current->next;
            $current->next->pre=$current->pre;
            $current=null;
        }
        $this->size--;
        
    }
    
    //把对应的节点应到链表头部(最近get或者刚刚put进去的node节点)
    public function moveToHead(Node $node)
    {
        if($node==$this->head) return ;
        //调整前后指针指向
        $node->pre->next=$node->next;
        $node->next->pre=$node->pre;
        $node->next=$this->head;
        $this->head->pre=$node;
        $this->head=$node;
        $node->pre=null;
    }
    
    
}


class Node{
    public $key;
    public $val;
    public $next;
    public $pre;
    public function __construct($val)
    {
        $this->val=$val;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * $obj = LRUCache($capacity);
 * $ret_1 = $obj->get($key);
 * $obj->put($key, $value);
 */

联系

​