146. LRU 缓存
80 / 0 / 创建于 2年前 /
xiaer 的个人博客
题目
请你设计并实现一个满足 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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：