Leetcode基础刷题之PHP解析(146. LRU Cache)


Github整理地址:https://github.com/wuqinqiang/leetcode-php

上一题链接Leetcode基础刷题之PHP解析(143. Reorder List)

2cb8a5469024dbbc722d4d04c9c0f8bc.png

题目描述

实现一个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);
 */

Vote Vote Cancel Collect Collect Cancel

<< 上一篇: Leetcode基础刷题之PHP解析(143. Reorder List)

>> 下一篇: MySQL 事务最全详解