当前位置:网站首页>Force buckle 146 LRU cache
Force buckle 146 LRU cache
2022-07-06 02:32:00 【Yangshiwei....】
subject :
analysis :
You can add a two-way linked list to the hash table ,size Record the amount of data in the current cache ,capacity The maximum amount of data that can be stored in the cache , It is also the input parameter brought when initializing the class ,first,last The two nodes represent the head and tail of the bidirectional linked list respectively , Insert data using tail interpolation , The previous node of the tail node is the most recently used node , The next node of the head node is the most rarely used node , That is to say LRU The one replaced in the algorithm ,hash Responsible for indexing , If there is this index value in the hash , Then he is in the cache , Otherwise, it's not in .
Code :
class LRUCache {
class Node{
int key;
int val;
Node next;
Node pre;
public Node(){}
public Node(int key,int val){
this.key=key;
this.val=val;
this.next=null;
this.pre=null;
}
}
HashMap<Integer,Node> hash=new HashMap<Integer,Node>();
int size;
int capacity;
Node first;
Node last;
public LRUCache(int capacity) {
this.size=0;
this.capacity=capacity;
this.first=new Node();
this.last=new Node();
first.next=last;
last.pre=first;
}
public int get(int key) {
Node n=hash.get(key);
if(n!=null){
Node pre=n.pre;
Node nex=n.next;
if(nex!=last){
nex.pre=pre;
pre.next=nex;
n.pre=last.pre;
last.pre.next=n;
n.next=last;
last.pre=n;
}
return n.val;
}else{
return -1;
}
}
public void put(int key, int value) {
Node n=hash.get(key);
if(n!=null){
Node pre=n.pre;
Node nex=n.next;
if(nex!=last){
nex.pre=pre;
pre.next=nex;
n.pre=last.pre;
last.pre.next=n;
n.next=last;
last.pre=n;
}
n.val=value;
}else{
if(size==capacity){
int k=first.next.key;
hash.remove(k);
first.next=first.next.next;
first.next.pre=first;
size--;
}
n=new Node(key,value);
n.pre=last.pre;
last.pre.next=n;
n.next=last;
last.pre=n;
hash.put(key,n);
size++;
}
}
}
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache obj = new LRUCache(capacity);
* int param_1 = obj.get(key);
* obj.put(key,value);
*/
边栏推荐
- 模板_快速排序_双指针
- 2022 edition illustrated network pdf
- Multiple solutions to one problem, asp Net core application startup initialization n schemes [Part 1]
- Zero foundation self-study STM32 - Review 2 - encapsulating GPIO registers with structures
- 2022.02.13
- [untitled] a query SQL execution process in the database
- [Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 17
- Crawler (9) - scrape framework (1) | scrape asynchronous web crawler framework
- Lecture 4 of Data Engineering Series: sample engineering of data centric AI
- 更改对象属性的方法
猜你喜欢
Ue4- how to make a simple TPS role (II) - realize the basic movement of the role
[community personas] exclusive interview with Ma Longwei: the wheel is not easy to use, so make it yourself!
Spark accumulator
[robot library] awesome robots Libraries
Initial understanding of pointer variables
零基础自学STM32-野火——GPIO复习篇——使用绝对地址操作GPIO
Blue Bridge Cup group B provincial preliminaries first question 2013 (Gauss Diary)
Déduisez la question d'aujourd'hui - 729. Mon emploi du temps I
[Wu Enda machine learning] week5 programming assignment EX4 - neural network learning
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 16
随机推荐
Easy to use js script
Multi function event recorder of the 5th National Games of the Blue Bridge Cup
数据准备工作
Multiple solutions to one problem, asp Net core application startup initialization n schemes [Part 1]
MySQL winter vacation self-study 2022 11 (9)
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 19
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 8
Accident index statistics
Sword finger offer 30 Stack containing min function
HDU_p1237_简单计算器_stack
There are so many giants, why should we independently develop POS store cashier system?
在GBase 8c数据库中使用自带工具检查健康状态时,需要注意什么?
事故指标统计
729. 我的日程安排表 I / 剑指 Offer II 106. 二分图
"Hands on learning in depth" Chapter 2 - preparatory knowledge_ 2.5 automatic differentiation_ Learning thinking and exercise answers
力扣今日題-729. 我的日程安排錶 I
Adapter-a technology of adaptive pre training continuous learning
Global and Chinese market of wheelchair climbing machines 2022-2028: Research Report on technology, participants, trends, market size and share
[Yunju entrepreneurial foundation notes] Chapter II entrepreneur test 9
SQL table name is passed as a parameter