栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

LRUCache简单实现

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

LRUCache简单实现

LRUCache简单实现

来源于LeetCode. 146. LRU 缓存

题目要求实现一个LRUCache,我们使用get时,需要额外把该节点移动到开头;

我们使用put时,如果存在该节点,我们需要把该节点删除,并且插入到开头;不存在则插入到开头,此时需要判断长度是否大于给定的capacity。

并且实现这两种操作时,时间复杂度都必须为O(1);get我们使用HashMap便可以达到我们的时间复杂度,但是HashMap不是有序的,但它的子类LinkedHashMap是有序的,所以我们使用LinkedHashMap便可以达到本题的效果,但是我们还是自己实现一个双向链表,才能考验代码功底

class LRUCache {
    private DoubleLinkedList head;
    private DoubleLinkedList tail;
    private int capacity;
    private Map cache;

    public LRUCache(int capacity) {
        cache=new HashMap<>();
        this.capacity=capacity;
        head=new DoubleLinkedList(0,0);
        tail=new DoubleLinkedList(0,0);
        head.next=tail;
        tail.pre=head;
    }

    public int get(int key) {
        if(cache.containsKey(key)){
            DoubleLinkedList temp=cache.get(key);
            //删除掉这个节点
            delete(temp);
            //在头结点插入这个节点
            insert(temp);
            return temp.val;
        }else{
            return -1;
        }
    }

    public void put(int key, int value) {
        if(cache.containsKey(key)){
            DoubleLinkedList temp=cache.get(key);
            delete(temp);
            insert(temp);
            temp.val=value;
        }else{
            DoubleLinkedList temp=new DoubleLinkedList(key,value);
            insert(temp);
            if(cache.size()>capacity){
                delete(tail.pre);
            }
        }
    }

    public void delete(DoubleLinkedList temp){
        cache.remove(temp.key);
        temp.next.pre=temp.pre;
        temp.pre.next=temp.next;
    }

    public void insert(DoubleLinkedList temp){
        cache.put(temp.key,temp);
        temp.next=head.next;
        temp.pre=head;
        head.next.pre=temp;
        head.next=temp;
    }
    class DoubleLinkedList{
        DoubleLinkedList pre;
        DoubleLinkedList next;
        int key;
        int val;
        public DoubleLinkedList(int key,int val){
            this.key=key;
            this.val=val;
        }
    }
}


转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/950901.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号