当前位置:网站首页>LeetCode 146. LRU 缓存
LeetCode 146. LRU 缓存
2022-08-10 11:09:00 【水菜笔】
原题网址:https://leetcode.cn/problems/lru-cache/
固定容量的缓存,如果满了后,再次添加新的,会删除最近最少使用的那个节点
要求是get,put都是O(1),
class LRUCache {
// 用map保存数据;保证存取是O(1)
// 双向链表保存顺序。
ListNode head;
ListNode tail;
Map<Integer, ListNode> data;
int capacity;
public LRUCache(int capacity) {
data = new HashMap<>();
this.capacity = capacity;
}
private void removeNode(ListNode cur) {
// 维护顺序
ListNode next = cur.next;
ListNode prev = cur.prev;
if(prev != null) {
prev.next = next;
cur.prev = null;
}else {
// 说明删除的是头结点
head = next;
// cur.next = null;
}
if(next != null){
next.prev = prev;
cur.next = null;
}else {
// 删除的是尾结点
tail = prev;
}
}
private void insertHead(ListNode cur) {
cur.next = head;
if(head != null) {
head.prev = cur;
head = cur;
} else {
head = tail = cur;
}
}
public int get(int key) {
ListNode cur = data.get(key);
// 有值,则返回数据
if(cur != null) {
// 维护顺序
removeNode(cur);
insertHead(cur);
return cur.value;
}
return -1;
}
public void put(int key, int value) {
ListNode node = data.get(key);
if(node != null) {
node.value = value;
removeNode(node);
insertHead(node);
} else {
if(data.size()>= capacity) {
node = tail;
removeNode(tail);
data.remove(node.key);
}
node = new ListNode(key,value);
data.put(key,node);
insertHead(node);
}
}
}
class ListNode {
int key;
int value;
ListNode prev;
ListNode next;
public ListNode(int key,int value) {
this.key = key;
this.value = value;
}
}
边栏推荐
- Redis设计与实现
- 快手“弃”有赞与微盟“结亲”,电商SaaS行业竞争格局将变?
- ENVI 5.3软件安装包和安装教程
- 负载均衡原理分析与源码解读
- 孩子自律性不够?猿辅导:计划表要注意“留白”给孩子更多掌控感
- 建校仅11年就入选“双一流” ,这所高校是凭什么做到的?
- HDU 4372:Count the Buildings (Stirling数)
- WeChat applet, global variables change in one place and the state in other places also changes.
- 阻塞 非阻塞 poll机制 异步
- VSCode remote connection server error: Could not establish connection to "xxxxxx" possible error reasons and solutions
猜你喜欢
随机推荐
越折腾越好用的 3 款开源 APP
零基础想自学软件测试,有没有大佬可以分享下接下来的学习书籍和路线?
APP automation testing practice based on UiAutomator2+PageObject mode
LeetCode50天刷题计划(Day 17—— 下一个序列(14.50-16.30)
3款不同类型的自媒体免费工具,有效提高创作、运营效率
怎么加入自媒体,了解这5种变现模式,让账号快速变现
Buckle exercise - rectangular area does not exceed the maximum value of K and (hard)
L2 applications from a product perspective: why is it a playground?
Intel pushes 20220809 CPU microcode update to patch Intel-SA-00657 security vulnerability
StoneDB 文档捉虫活动第一季
Spss-多元回归案例实操
【LeetCode】640. 求解方程
力扣练习——56 寻找右区间
HDU 6040 Hints of sd0061 (技巧)
LeetCode 21. 合并两个有序链表
关于振弦采集模块及采集仪振弦频率值准确率的问题
LeetCode 82. 删除排序链表中的重复元素 II
不止跑路,拯救误操作rm -rf /*的小伙儿
态路小课堂丨如何为CXP光模块选择光纤跳线?
LeetCode 61. 旋转链表