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

LeetCode - 460 LFU 缓存(设计 - 哈希表+双向链表 哈希表+平衡二叉树(TreeSet))*

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

LeetCode - 460 LFU 缓存(设计 - 哈希表+双向链表 哈希表+平衡二叉树(TreeSet))*


哈希表 + 平衡二叉树(TreeSet)

class LFUCache {
    class Node{
        int key;//key
        int val;//val
        int freq;//使用频率
        int t;//最后一次被使用的时间
        public Node(int key,int val,int freq,int t){
            this.key = key;
            this.val = val;
            this.freq = freq;
            this.t = t;
        }
    }

    class NodeComparator implements Comparator{
        //当使用频率不一样时 按使用频率升序排序
        public int compare(Node n1,Node n2){
            if(n1.freq != n2.freq)
                return n1.freq - n2.freq;
            else//当使用频率一样的时候 按使用的时间升序排序
                return n1.t - n2.t;
        }
    }
    private Map map;
    private TreeSet set;
    //时间计数器 从0开始
    private int t;
    //LFU缓存的容量
    private int capacity;
    public LFUCache(int capacity) {
        this.map = new HashMap<>();
        this.set = new TreeSet<>(new NodeComparator());
        this.t = 0;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        //时间计数器加一
        this.t += 1;
        if(map.get(key) == null){
            return -1;
        }
        else{
            Node node = map.get(key);
            set.remove(node);
            //该key的使用频率加一
            node.freq = node.freq + 1;
            //更新key最后被使用的时间
            node.t = this.t;
            set.add(node);
            map.put(key,node);
            return node.val;
        }
    }
    
    public void put(int key, int value){
          if(this.capacity == 0)
            return ;
          this.t += 1;
         //如果key本来就存在于map中
         if(map.get(key)!=null){
             Node node = map.get(key);
             set.remove(node);
             //更新val值
             node.val = value;
             //更新最后使用时间
             node.t = this.t;
             //使用频率加一
             node.freq = node.freq + 1;
             set.add(node);
             map.put(key,node);
         }else{
             //如果LFU缓存中没有空间 弹出最近最久未使用的
             if(set.size() >=  this.capacity){
                 map.remove(set.first().key);
                 set.remove(set.first());
             }
            Node node = new Node(key,value,1,this.t);
            map.put(key,node);
            set.add(node);
         }
    }
}


哈希表 + 双向链表

class LFUCache {
    class Node{
        int key;//key
        int val;//val
        int freq;//key 使用频率
        Node prev;//前驱指针
        Node next;//后驱指针
        public Node(int key,int val,int freq){
            this.key = key;
            this.val = val;
            this.freq = freq;
        }
    }
    class DoublyLinkedList{
         //双向链表
         Node head;//头指针
         Node tail;//尾指针
         int size;//双向链表中节点个数
         public DoublyLinkedList(){
             head = new Node(0,0,0);//头节点
             tail = new Node(0,0,0);//尾节点
             head.next = tail;
             tail.prev = head;
             size = 0;
         }
         public void addFirst(Node node){
               Node headNext = head.next;
               head.next = node;
               node.prev = head;
               node.next = headNext;
               headNext.prev = node;
               size += 1;
         }
         public void remove(Node node){
             Node nodePrev = node.prev;
             Node nodeNext = node.next;
             nodePrev.next = nodeNext;
             nodeNext.prev = nodePrev;
             size -= 1;
         }
         public Node getHead(){
              return head.next;
         }
         public Node getTail(){
               return tail.prev;
         }
    }
    // key, Node
    private Map keyMap;
    //每个频率 对应的节点放在双向链表中 双向链表按操作时间排序 越久没操作的节点在链表中的位置越靠后
    private Map freqMap;
    //LFU缓存容量
    private int capacity;
    //最小操作频率
    private int minFreq;
    public LFUCache(int capacity) {
        keyMap = new HashMap<>();
        freqMap = new HashMap<>();
        this.capacity =  capacity;
        minFreq = 0;
    }
    
    public int get(int key) {
        if(this.capacity == 0)
           return -1;
        if(keyMap.get(key) == null){
            return -1;
        }
        else{
            Node node = keyMap.get(key);
            DoublyLinkedList dl = freqMap.get(node.freq);
            dl.remove(node);
            if(dl.size == 0){
                freqMap.remove(node.freq);
                if(node.freq == minFreq)
                   minFreq += 1;
                
            }
            node.freq += 1;
            if(freqMap.get(node.freq) == null)
               freqMap.put(node.freq,new DoublyLinkedList());
            freqMap.get(node.freq).addFirst(node);
            keyMap.put(key,node);
            return node.val;
        }
    }
    
    public void put(int key, int value) {
         if(this.capacity == 0)
           return ;
        if(keyMap.containsKey(key)){
            Node node = keyMap.get(key);
            DoublyLinkedList dl = freqMap.get(node.freq);
            dl.remove(node);
            if(dl.size == 0){
                freqMap.remove(node.freq);
                if(node.freq == minFreq)
                   minFreq += 1;
                
            }
            node.freq += 1;
            node.val = value;
            if(freqMap.get(node.freq) == null)
               freqMap.put(node.freq,new DoublyLinkedList());
            freqMap.get(node.freq).addFirst(node);
            keyMap.put(key,node);
        }
        else{
            if(keyMap.size() >= capacity){
                Node node = freqMap.get(minFreq).getTail();
                keyMap.remove(node.key);
                freqMap.get(minFreq).remove(node);
                if(freqMap.get(minFreq).size == 0)
                   freqMap.remove(minFreq);
            }
            Node newNode = new Node(key,value,1);
            if(freqMap.get(newNode.freq) == null)
               freqMap.put(newNode.freq,new DoublyLinkedList());
            freqMap.get(newNode.freq).addFirst(newNode);
            minFreq = 1;
            keyMap.put(key,newNode);
        }
    }
}


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

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

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