Leetcode146--LRU Cache

ゝ一纸荒年。 2023-01-16 11:19 133阅读 0赞

### 题目分析 ###

***对于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);
     */