带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(已过期)
    }
}
全部评论
这题字节手撕我遇到过
点赞 回复 分享
发布于 昨天 18:34 广东
上周面字节刚遇到过,咋全都这么爱考这题。。。8说了,我还在被狠狠横向
点赞 回复 分享
发布于 今天 11:15 辽宁

相关推荐

评论
1
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务