作者:朵儿lp_685 | 来源:互联网 | 2023-05-17 09:50
剑指offerLeetCode146LintCode134_LRU缓存实现声明文章均为本人技术笔记,转载请注明出处:1https:segmentfault.comuyz
剑指offer/LeetCode146/LintCode134_LRU缓存实现声明
文章均为本人技术笔记,转载请注明出处:
1 https://segmentfault.com/u/yzwall
[2] blog.csdn.net/j_dark/
解题思路
LRU缓存两种功能:
get(key)
:获取key的对应value,不存在返回-1
set(key, value)
(lintcode版本)/put(key, value)
(leetcode版本):设置
- 缓存已满,删除最近最久未被使用的节点,添加新节点进缓存
- 缓存未满,
- 节点存在,修改value;
- 节点不存在,添加新节点进缓存;
解题思路
由于LRU缓存插入和删除操作频繁,使用双向链表维护缓存节点,
+ “新节点”:凡是被访问(新建/修改命中/访问命中)过的节点,一律在访问完成后移动到双向链表尾部,保证链表尾部始终为最“新”节点;
+ “旧节点”:保证链表头部始终为最“旧”节点,LRU策略删除时表现为删除双向链表头部;
+ 从链表头部到尾部,节点访问热度逐渐递增
由于链表不支持随机访问,使用HashMap+双向链表实现LRU缓存;
+ HashMap中键值对:
+ 双向链表:维护缓存节点CacheNode
注意点
使用双向链表时,时刻记得维护pre
和next
指针;
题目链接
- lintcode 134: http://www.lintcode.com/zh-cn/problem/lru-cache/
- leetcode 146: https://leetcode.com/problems/lru-cache/#/description
Java代码
/**
* HashMap+双向链表实现LRU缓存
* http://www.lintcode.com/zh-cn/problem/lru-cache/
* https://leetcode.com/problems/lru-cache/#/description
* @author yzwall
*/
import java.util.HashMap;
class Solution {
private HashMap map;
private int capacity;
private CacheNode head = new CacheNode(-1, -1);
private CacheNode tail = new CacheNode(-1, -1);
private class CacheNode {
int key, value;
CacheNode pre, next;
CacheNode(int key, int value) {
this.key = key;
this.value = value;
this.pre = null;
this.next = null;
}
}
public Solution(int capacity) {
this.map = new HashMap<>();
this.capacity = capacity;
}
private void moveToTail(CacheNode target, boolean isNew) {
if (target != tail.next) {
if (!isNew) {
target.pre.next = target.next;
target.next.pre = target.pre;
}
tail.next.next = target;
target.pre = tail.next;
tail.next = target;
}
}
public int get(int key) {
if (map.containsKey(key)) {
CacheNode target = map.get(key);
moveToTail(target, false);
tail.next.next = null;
return target.value;
}
return -1;
}
/**
* 1. 节点命中,修改节点并移动到链表尾部tail.next
* 2. 节点未命中,
* 2.1 cache已满,删除链表头部head.next
* 2.2 cache未满,新建节点并添加到链表尾部tail.next
*/
public void set(int key, int value) {
if (map.containsKey(key)) {
CacheNode target = map.get(key);
target.value = value;
map.put(key, target);
moveToTail(target, false);
} else if(map.size()
CacheNode newNode =
new CacheNode(key, value);
map.put(key, newNode);
if (head.next ==
null) {
head.next = newNode;
newNode.pre = head;
tail.next = newNode;
}
else {
moveToTail(newNode,
true);
}
}
else {
CacheNode newNode =
new CacheNode(key, value);
map.remove(head.next.key);
map.put(key, newNode);
if (head.next == tail.next) {
head.next = newNode;
tail.next = newNode;
}
else {
head.next.next.pre = head;
head.next = head.next.next;
moveToTail(newNode,
true);
}
}
}
}