PHP
话题列表 社区 Wiki 优质外文 招聘求职 PHP 实战教程 社区文档
登录
注册

146. LRU 缓存

xiaer 的个人博客 / 0 / 0 / 创建于 2年前 / 更新于 2年前

题目

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解答一

用了两个数组，一个数组用作map，另外一个数组用作记录操作热度；
每次get或者put之后都把这个key从热度的数组中移动到队列末尾，热度最高；
当put的时候，如果已经满了，就把record队列中热度最低的删除掉；

class LRUCache {

    protected int $capacity;
    protected array $cache = []; // [key => value]
    protected array $record = []; // [key, key, key, ...]

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->capacity = $capacity;
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (false !== ($id = array_search($key, $this->record))) {
            if ($id+1 != count($this->record)) {
                array_splice($this->record, $id, 1);
                array_push($this->record, $key);
            }
            return $this->cache[$key];
        }
        return -1;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        if (isset($this->cache[$key])) {
            $this->cache[$key] = $value;
            $id = array_search($key, $this->record);
            if ($id+1 != count($this->record)) {
                array_splice($this->record, $id, 1);
                array_push($this->record, $key);
            }
        } else if (count($this->cache) < $this->capacity) {
            $this->cache[$key] = $value;
            array_push($this->record, $key);
        } else {
            unset($this->cache[$del]);
            $del = array_shift($this->record);
            $this->cache[$key] = $value;
            array_push($this->record, $key);
        }
    }
}

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

执行用时：2668 ms, 在所有 PHP 提交中击败了5.68%的用户

内存消耗：138.4 MB, 在所有 PHP 提交中击败了60.23%的用户

通过测试用例：22 / 22

解答二

这道题非常有意思，由于 PHP 中除了基础数据类型以外，主要就是 array，所以思考问题的时候总是想着如何使用 array 去承载数据，这道题让我学会了要跨越语言，并时刻记住还有很多其他之前学习的数据结构可以使用：array（数组）、hashmap（哈希映射）、linkList（单链表）、doubleLinkList（双向链表）、struct（结构体）、object（对象）、tree（树）、binaryTree（二叉树）、graph（图）等等。
单纯使用一个有序的数组来存 key 值，虽然可以给所有的 key 排序，但是无法在 get 的时候通过O(1) 的时间复杂度去获取到数组中的 key 值，并将其挪动到数组的最前面。解答1中用到的 array_search() 实际上是去循环搜索，这样是 O(n) 的时间复杂度，自然是不满足的。
如果我们此时将数组的值由原来的单纯存储数字，变成存储对象，并将这个对象放到 map 的映射中，就可以实现时间复杂度 O(1) 的目标了，但我们在数组中定位到了这个对象又如何呢。不知道这个对象在此数组中的索引，我们依旧无法去修改它的顺序。
怎样才能在获取到对象本身的时候，直接就可以更改它在序列中的顺序呢？
已知的顺序存储的数据结构中，有两种：数组和链表，这两个都是有序的。而链表刚好满足我们的要求：在得到一个元素本身的时候就可以剪切自身，然后移动到头部或者尾部，当然如果不想从头结点循环遍历过来，就需要使用双向链表。
下面是具体的代码。

class Node {
    public int $key;
    public int $value;
    public ?Node $prev = null;
    public ?Node $next = null;

    function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

class LRUCache {

    protected int $cap;
    protected array $map = []; // [key => {value}]
    protected ?Node $listHead = null; // head -> {value} <=> {value} <=> {value}, ... <- end
    protected ?Node $listEnd = null;

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->cap = $capacity;
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (!isset($this->map[$key])) return -1;

        $this->mvToHead($this->map[$key]);
        return $this->map[$key]->value;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        if (isset($this->map[$key])) {
            $this->map[$key]->value = $value;
            $this->mvToHead($this->map[$key]);
            return;
        }

        if (count($this->map) >= $this->cap) {
            $node = $this->pop();
            if ($node) {
                unset($this->map[$node->key]);
            }
        }

        $this->map[$key] = new Node($key, $value);
        $this->unshift($this->map[$key]);
    }

    /** 链表操作：插入到头部 */
    protected function unshift(Node $node) {
        $node->prev = null;

        if ($this->listHead) {
            $node->next = $this->listHead;
            $this->listHead->prev = $node;
            $this->listHead = $node;
        } else {
            $this->listHead = $this->listEnd = $node;
        }
    }

    /** 链表操作：移除尾部 */
    protected function pop() {
        if ($this->listEnd) {
            $node = $this->listEnd;
            if ($node->prev) {
                $node->prev->next = null;
                $this->listEnd = $node->prev;
                $node->prev = null;
            } else {
                $this->listHead = $this->listEnd = null;
            }
            return $node;
        } else {
            return null;
        }
    }

    /** 链表操作：移动节点到头部 */
    protected function mvToHead(Node $node) {
        // 若不在头部才移动
        if ($node->prev) {
            // 先剪切自己出来
            $node->prev->next = $node->next;
            if ($node->next) {
                $node->next->prev = $node->prev;
            } else {
                $this->listEnd = $node->prev;
            }

            // 移动到链表头部
            $this->unshift($node);
        }
    }
}

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

执行用时：400 ms, 在所有 PHP 提交中击败了77.78%的用户

内存消耗：138.8 MB, 在所有 PHP 提交中击败了37.78%的用户

通过测试用例：22 / 22

解答三

针对解答二，还可以优化一下，把链表单独设计一个类封装一下。

class Node {
    public int $key;
    public int $value;
    public ?Node $prev = null;
    public ?Node $next = null;

    function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

/** 双向链表 */
class LinkList {
    protected ?Node $head = null; // head -> {value} <=> {value} <=> {value}, ... <- end
    protected ?Node $end = null;

    /** 头部插入 */
    public function unshift(Node $node) {
        if ($this->head) {
            $node->next = $this->head;
            $this->head->prev = $node;
            $this->head = $node;
        } else {
            $this->head = $this->end = $node;
        }
    }

    /** 弹出尾部节点 */
    public function pop() {
        if ($this->end) {
            $node = $this->end;
            $this->end = $node->prev;
            if ($this->end) $this->end->next = null;
            $node->prev = null;
            return $node;
        } else {
            return null;
        }
    }

    /** 移除节点 */
    public function remove(Node $node) {
        if ($node->prev) {
            $node->prev->next = $node->next;
        } else {
            $this->head = $node->next;
        }

        if ($node->next) {
            $node->next->prev = $node->prev;
        } else {
            $this->end = $node->prev;
        }

        $node->prev = null;
        $node->next = null;
    }
}

class LRUCache {
    protected int $use = 0;
    protected int $cap;
    protected array $map = []; // [key => {value}]
    protected LinkList $list;

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->cap = $capacity;
        $this->list = new LinkList();
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (!isset($this->map[$key])) return -1;
        $this->list->remove($this->map[$key]);
        $this->list->unshift($this->map[$key]);
        return $this->map[$key]->value;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        if (isset($this->map[$key])) {
            $this->map[$key]->value = $value;
            $this->list->remove($this->map[$key]);
            $this->list->unshift($this->map[$key]);
            return;
        }

        if ($this->use >= $this->cap) {
            $node = $this->list->pop();
            if (!$node) return; // 没能弹出
            unset($this->map[$node->key]);
        } else {
            $this->use++;
        }

        $this->map[$key] = new Node($key, $value);
        $this->list->unshift($this->map[$key]);
    }
}

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

执行用时：476 ms, 在所有 PHP 提交中击败了41.11%的用户

内存消耗：139 MB, 在所有 PHP 提交中击败了15.56%的用户

通过测试用例：22 / 22

封装之后速度更慢一点了。

解答四 ✅

双向链表中关于头节点和尾节点是否存在的判断太多了，可以考虑优化一下。默认初始化的时候就先添加上两个空的头尾节点，这样所有的操作相当于都是对中间节点的操作，虽然会花费更多的内存，但是效率上应该会高一点，接下来试试。

class Node {
    public int $key;
    public int $value;
    public ?Node $prev = null;
    public ?Node $next = null;

    function __construct($key, $value) {
        $this->key = $key;
        $this->value = $value;
    }
}

/** 双向链表 */
class LinkList {
    protected Node $head; // head -> {value} <=> {value} <=> {value}, ... <- end
    protected Node $end;

    function __construct() {
        $this->head = new Node(0, 0);
        $this->end = new Node(0, 0);
        $this->head->next = $this->end;
        $this->end->prev = $this->head;
    }

    /** 头部插入 */
    public function unshift(Node $node) {
        $node->prev = $this->head;
        $node->next = $this->head->next;
        $this->head->next = $node;
        $node->next->prev = $node;
    }

    /** 弹出尾部节点 */
    public function pop() {
        $node = $this->end->prev;
        if ($node === $this->head) return null;
        $this->remove($node);
        return $node;
    }

    /** 移除节点 */
    public function remove(Node $node) {
        $node->prev->next = $node->next;
        $node->next->prev = $node->prev;
        $node->prev = null;
        $node->next = null;
    }
}

class LRUCache {
    protected int $use = 0;
    protected int $cap;
    protected array $map = []; // [key => {value}]
    protected LinkList $list;

    /**
     * @param Integer $capacity
     */
    function __construct($capacity) {
        $this->cap = $capacity;
        $this->list = new LinkList();
    }

    /**
     * @param Integer $key
     * @return Integer
     */
    function get($key) {
        if (!isset($this->map[$key])) return -1;
        $this->list->remove($this->map[$key]);
        $this->list->unshift($this->map[$key]);
        return $this->map[$key]->value;
    }

    /**
     * @param Integer $key
     * @param Integer $value
     * @return NULL
     */
    function put($key, $value) {
        if (isset($this->map[$key])) {
            $this->map[$key]->value = $value;
            $this->list->remove($this->map[$key]);
            $this->list->unshift($this->map[$key]);
            return;
        }

        if ($this->use >= $this->cap) {
            $node = $this->list->pop();
            if (!$node) return; // 没能弹出
            unset($this->map[$node->key]);
        } else {
            $this->use++;
        }

        $this->map[$key] = new Node($key, $value);
        $this->list->unshift($this->map[$key]);
    }
}

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

执行用时：400 ms, 在所有 PHP 提交中击败了78.49%的用户

内存消耗：138.8 MB, 在所有 PHP 提交中击败了43.01%的用户

通过测试用例：22 / 22
这个结果确实没有想到，增加了两个首尾空节点，让代码的复杂程度大大降低，与此同时执行效率提高了，而且内存占用也降下来了，挺好的。

算法题
本作品采用《CC 协议》，转载必须注明作者和本文链接
xiaer
84 声望
Developer @ Free
学而不思则罔，思而不学则殆。
讨论数量: 0
排序：
时间 投票
(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！
支持 MD 帮助
xiaer
Developer @ Free
文章
23
粉丝
3
喜欢
11
收藏
25
排名：1620
访问：1868
私信
所有博文
文章归档
1 篇 2022 年 7 月 12 篇 2022 年 5 月 10 篇 2022 年 4 月
最新文章 最受欢迎
2年前 Linux C 中的 fork()、vfork()、exec*()、system() 等进程函数 2年前 PHP 源码中的 zval 2年前 用 PHP 实现自己的 sha-256 哈希算法 2年前 215. 数组中的第K个最大元素 2年前 六、堆排序
3 用 PHP 实现自己的 sha-256 哈希算法 1 215. 数组中的第K个最大元素 1 二、选择排序 1 25. K 个一组翻转链表 1 C/C++ 中如何引入第三方库
博客标签
数据结构
1
 加密解密
1
 php源码
2
 排序算法
8
 算法题
5
 C和C++
6
社区赞助商
成为赞助商

关于 LearnKu

LearnKu 是终身编程者的修道场
做最专业、严肃的技术论坛
LearnKu 诞生的故事

资源推荐

  • 《社区使用指南》
  • 《文档撰写指南》
  • 《LearnKu 社区规范》
  • 《提问的智慧》

    • 服务提供商

    其他信息

  • 成为版主
  • 所有测验
  • 联系站长（反馈建议）

    • 粤ICP备18099781号-6 | 粤公网安备 44030502004330号 | 违法和不良信息举报

    由 Summer 设计和编码 ❤

    请登录

    内容举报
    匿名举报，为防止滥用，仅管理员可见举报者。

    我要举报该，理由是：

    取消