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

相关推荐

import&nbsp;java.util.*;class&nbsp;Node&nbsp;{public&nbsp;Integer&nbsp;key;public&nbsp;Integer&nbsp;value;public&nbsp;Long&nbsp;timeStamp;public&nbsp;Node(Integer&nbsp;key,&nbsp;Integer&nbsp;value,&nbsp;Long&nbsp;timeStamp)&nbsp;{this.key&nbsp;=&nbsp;key;this.value&nbsp;=&nbsp;value;this.timeStamp&nbsp;=&nbsp;timeStamp;}}class&nbsp;LRUCache&nbsp;{private&nbsp;Map&lt;Integer,&nbsp;Node&gt;&nbsp;map;private&nbsp;int&nbsp;capacity;public&nbsp;LRUCache(int&nbsp;capacity)&nbsp;{map&nbsp;=&nbsp;new&nbsp;LinkedHashMap&lt;&gt;();this.capacity&nbsp;=&nbsp;capacity;}public&nbsp;int&nbsp;get(int&nbsp;key)&nbsp;{Node&nbsp;node&nbsp;=&nbsp;map.get(key);//&nbsp;key&nbsp;不存在if&nbsp;(node&nbsp;==&nbsp;null)&nbsp;{return&nbsp;-1;}//&nbsp;key&nbsp;过期(懒删除策略)if&nbsp;(isExpire(node))&nbsp;{map.remove(key);return&nbsp;-1;}map.remove(key);map.put(key,&nbsp;node);return&nbsp;node.value;}public&nbsp;void&nbsp;put(int&nbsp;key,&nbsp;int&nbsp;value,&nbsp;Long&nbsp;timeStamp)&nbsp;{Node&nbsp;node&nbsp;=&nbsp;map.get(key);if&nbsp;(node&nbsp;==&nbsp;null)&nbsp;{&nbsp;&nbsp;//&nbsp;key&nbsp;不存在node&nbsp;=&nbsp;new&nbsp;Node(key,&nbsp;value,&nbsp;timeStamp);if&nbsp;(map.size()&nbsp;&lt;&nbsp;capacity)&nbsp;{&nbsp;&nbsp;//&nbsp;有额外空间map.put(key,&nbsp;node);}&nbsp;else&nbsp;{&nbsp;&nbsp;//&nbsp;没有额外空间//&nbsp;先尝试移除过期keyremoveExpireNodes();//&nbsp;如果空间还是不足,移除最老的keyif&nbsp;(map.size()&nbsp;&gt;=&nbsp;capacity)&nbsp;{map.remove(map.keySet().iterator().next());}map.put(key,&nbsp;node);}}&nbsp;else&nbsp;{&nbsp;&nbsp;//&nbsp;key&nbsp;存在map.remove(key);node&nbsp;=&nbsp;new&nbsp;Node(key,&nbsp;value,&nbsp;timeStamp);map.put(key,&nbsp;node);}}private&nbsp;void&nbsp;removeExpireNodes()&nbsp;{for&nbsp;(Node&nbsp;node&nbsp;:&nbsp;map.values())&nbsp;{if&nbsp;(isExpire(node))&nbsp;{map.remove(node.key);}}}private&nbsp;boolean&nbsp;isExpire(Node&nbsp;node)&nbsp;{if&nbsp;(node.timeStamp&nbsp;==&nbsp;null)&nbsp;{&nbsp;&nbsp;//&nbsp;没有时间戳表示永久不过期return&nbsp;false;}return&nbsp;System.currentTimeMillis()&nbsp;&gt;&nbsp;node.timeStamp;}}class&nbsp;LRUTTL&nbsp;{public&nbsp;static&nbsp;void&nbsp;main(String[]&nbsp;args)&nbsp;{LRUCache&nbsp;cache&nbsp;=&nbsp;new&nbsp;LRUCache(2);cache.put(1,&nbsp;10,&nbsp;null);cache.put(2,&nbsp;20,&nbsp;null);System.out.println(cache.get(1));&nbsp;&nbsp;//&nbsp;10cache.put(3,&nbsp;30,&nbsp;null);System.out.println(cache.get(2));&nbsp;&nbsp;//&nbsp;-1cache.put(4,&nbsp;40,&nbsp;System.currentTimeMillis()&nbsp;+&nbsp;1000);try&nbsp;{System.out.println(cache.get(1));&nbsp;&nbsp;//&nbsp;-1Thread.sleep(1500);System.out.println(cache.get(3));&nbsp;&nbsp;//&nbsp;30System.out.println(cache.get(4));&nbsp;&nbsp;//&nbsp;-1}&nbsp;catch&nbsp;(InterruptedException&nbsp;e)&nbsp;{throw&nbsp;new&nbsp;RuntimeException(e);}}}优化点:可以维护一个map结构存储&lt;最小过期时间,节点数量&gt;来判断当前LinkedList中是否存在已经过期的node,可以一定程度地减少&nbsp;removeExpireNodes&nbsp;的调用次数
点赞 评论 收藏
分享
评论
3
13
分享

创作者周榜

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