题解 | #设计LFU缓存结构#

设计LFU缓存结构

http://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1

如何更新minFre是关键,有两种办法更新,第一种是该元素的本来就是位于最少次数的list的唯一元素,则该元素的fre增加之后,minFre也要跟着变,第二种是有新的元素***来了,minFre要变为1,进行最小访问频率的同步。
两个HashMap,一个用来查找,存放<key,Lfu>,另一个用来维护频率,存放<key,LinkedList<Lfu>>
import java.util.*;


public class Solution {
    /**
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    class Lfu{
        int key,val,frequency;
        public Lfu(int key,int val){
            this.key=key;
            this.val=val;
            this.frequency=0;
        }
        
    }
    int fre=0;
    int minFre=1;
    Map<Integer,Lfu> valueMap=new HashMap<>();
    Map<Integer,LinkedList<Lfu>>freMap=new HashMap<>();
    public void updateFre(Lfu lfu){
        if(freMap.containsKey(lfu.frequency)){
            LinkedList tmp=freMap.get(lfu.frequency);
            tmp.remove(lfu);
            if(tmp.isEmpty()&&lfu.frequency==minFre){
                minFre++;
            }
        }
        lfu.frequency++;
        if(lfu.frequency==1){
            minFre=1;
        }
        if(freMap.containsKey(lfu.frequency)){
            freMap.get(lfu.frequency).addFirst(lfu);
        }
        else{
            freMap.put(lfu.frequency,new LinkedList<Lfu>());
            freMap.get(lfu.frequency).addFirst(lfu);
        }
    }
    public int get(int key){
        if(!valueMap.containsKey(key)){
            return -1;
        }
        Lfu tmp=valueMap.get(key);
        updateFre(tmp);
        return tmp.val;
        
    }
    public void put(Lfu lfu,int k){
        int key=lfu.key;
        int val=lfu.val;
        if(valueMap.containsKey(key)){
            Lfu tmp=valueMap.get(key);
            tmp.val=val;
            updateFre(tmp);
        }
        else{
            if(valueMap.size()<k){
                ;
            }
            else{
                Lfu tmp=freMap.get(minFre).removeLast();
                valueMap.remove(tmp.key);
                
            }
              valueMap.put(key,lfu);
              updateFre(valueMap.get(key));
        }

    }
    public int[] LFU (int[][] operators, int k) {
        // write code here
        int n=operators.length;
        List<Integer> res=new ArrayList<>();
         
        for(int i=0;i<n;i++){
            if(operators[i][0]==1){
               
                put(new Lfu(operators[i][1],operators[i][2]),k);
               
            }
            else{
                res.add(get(operators[i][1]));
            }
        }
        int[]result=new int[res.size()];
        for(int i=0;i<res.size();i++){
            result[i]=res.get(i);
        }
        return result;
    }
}
全部评论

相关推荐

找不到工作死了算了:没事的,雨英,hr肯主动告知结果已经超越大部分hr了
点赞 评论 收藏
分享
10-27 17:26
东北大学 Java
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
昨天 12:19
点赞 评论 收藏
分享
评论
点赞
收藏
分享
牛客网
牛客企业服务