带ttl的LRU 家人们说我写的对吗
可运行版本
import java.util.HashMap;
import java.util.Map;
class LRUCache {
class DLinkedList{
int key;
int val;
DLinkedList next;
DLinkedList prev;
long timeStamp;
public DLinkedList(){
this.timeStamp = System.currentTimeMillis();
}
public DLinkedList(int key,int val){
this.key = key;
this.val = val;
this.timeStamp = System.currentTimeMillis();
}
}
int capacity;
int size;
DLinkedList head;
DLinkedList tail;
Map<Integer,DLinkedList> map;
long ttl;
public LRUCache(int capacity,long ttl){
this.capacity = capacity;
size = 0;
head = new DLinkedList();
tail = new DLinkedList();
head.next=tail;
tail.prev = head;
map = new HashMap<>();
this.ttl = ttl;
}
public void addToHead(DLinkedList node){
node.next = head.next;
head.next.prev = node;
node.prev = head;
head.next = node;
}
public void removeOne(DLinkedList node){
node.next.prev = node.prev;
node.prev.next = node.next;
}
public boolean isExpired(DLinkedList node){
long now = System.currentTimeMillis();
long diff = now-node.timeStamp;
if(diff>ttl){
return true;//true是过期了的意思 false才是没过期!!!
}
return false;
}
public int get(int key){
if(!map.containsKey(key)){
return -1;
}else{
DLinkedList node = map.get(key);
if(isExpired(node)){
removeOne(node);
map.remove(key);
size--;
return -1;
}
node.timeStamp = System.currentTimeMillis();
removeOne(node);
addToHead(node);
return node.val;
}
}
public void put(int key,int val){
if(!map.containsKey(key)){
DLinkedList newNode = new DLinkedList(key,val);
addToHead(newNode);
map.put(key,newNode);
size++;
if(size>capacity){
DLinkedList oldNode = tail.prev;
removeOne(oldNode);
map.remove(oldNode.key);
size--;
}
}else {
DLinkedList newNode = new DLinkedList(key,val);
DLinkedList oldNode = map.get(key);
removeOne(oldNode);
addToHead(newNode);
map.put(key,newNode);
}
}
}
class Main{
public static void main(String[] args) {
LRUCache cache = new LRUCache(2, 1000); // 1秒TTL
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 返回 1
try {
Thread.sleep(1500); // 等待1.5秒让数据过期
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(cache.get(1)); // 返回 -1(已过期)
System.out.println(cache.get(2)); // 返回 -1(已过期)
}
}
import java.util.HashMap;
import java.util.Map;
class LRUCache {
class DLinkedList{
int key;
int val;
DLinkedList next;
DLinkedList prev;
long timeStamp;
public DLinkedList(){
this.timeStamp = System.currentTimeMillis();
}
public DLinkedList(int key,int val){
this.key = key;
this.val = val;
this.timeStamp = System.currentTimeMillis();
}
}
int capacity;
int size;
DLinkedList head;
DLinkedList tail;
Map<Integer,DLinkedList> map;
long ttl;
public LRUCache(int capacity,long ttl){
this.capacity = capacity;
size = 0;
head = new DLinkedList();
tail = new DLinkedList();
head.next=tail;
tail.prev = head;
map = new HashMap<>();
this.ttl = ttl;
}
public void addToHead(DLinkedList node){
node.next = head.next;
head.next.prev = node;
node.prev = head;
head.next = node;
}
public void removeOne(DLinkedList node){
node.next.prev = node.prev;
node.prev.next = node.next;
}
public boolean isExpired(DLinkedList node){
long now = System.currentTimeMillis();
long diff = now-node.timeStamp;
if(diff>ttl){
return true;//true是过期了的意思 false才是没过期!!!
}
return false;
}
public int get(int key){
if(!map.containsKey(key)){
return -1;
}else{
DLinkedList node = map.get(key);
if(isExpired(node)){
removeOne(node);
map.remove(key);
size--;
return -1;
}
node.timeStamp = System.currentTimeMillis();
removeOne(node);
addToHead(node);
return node.val;
}
}
public void put(int key,int val){
if(!map.containsKey(key)){
DLinkedList newNode = new DLinkedList(key,val);
addToHead(newNode);
map.put(key,newNode);
size++;
if(size>capacity){
DLinkedList oldNode = tail.prev;
removeOne(oldNode);
map.remove(oldNode.key);
size--;
}
}else {
DLinkedList newNode = new DLinkedList(key,val);
DLinkedList oldNode = map.get(key);
removeOne(oldNode);
addToHead(newNode);
map.put(key,newNode);
}
}
}
class Main{
public static void main(String[] args) {
LRUCache cache = new LRUCache(2, 1000); // 1秒TTL
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // 返回 1
try {
Thread.sleep(1500); // 等待1.5秒让数据过期
} catch (InterruptedException e) {
e.printStackTrace();
}
System.out.println(cache.get(1)); // 返回 -1(已过期)
System.out.println(cache.get(2)); // 返回 -1(已过期)
}
}
全部评论
这题字节手撕我遇到过
上周面字节刚遇到过,咋全都这么爱考这题。。。8说了,我还在被狠狠横向
相关推荐

点赞 评论 收藏
分享
点赞 评论 收藏
分享

点赞 评论 收藏
分享
昨天 16:11
北京邮电大学 Java 点赞 评论 收藏
分享