LRU算法

解析
题目

使用LinkedHashMap

class LRUCache {
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
    public LRUCache(int capacity) { 
        this.cap = capacity;
    }
    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);
    }
    public void put(int key, int val) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, val);
            // 将 key 变为最近使用
            makeRecently(key);
            return;
        }
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, val);
    }
    private void makeRecently(int key) {
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, val);
    }
}

不使用LinkedHashMap

class LRUCache {
    HashMap<Integer,Node> cache;
    Node head;
    Node tail;
    int capacity;
    int size;
    public LRUCache(int capacity) {
        cache=new HashMap<>();
        this.capacity=capacity;
        this.size=0;
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.pre=head;
    }
    public int get(int key) {
        if(cache.containsKey(key)){
            Node node=cache.get(key);
            moveToHead(node);
            return node.val;
        }else{
            return -1;
        }
    }
    public void put(int key, int value) {
        if(cache.containsKey(key)){
            Node node=cache.get(key);
            node.val=value;
            moveToHead(node);
        }else{
            Node cur=new Node(key,value);
            addNode(cur);
        }
    }
    private void addNode(Node node){
        if(size==capacity){
            deleteOldestNode();
        }
        node.next=head.next;
        node.next.pre=node;
        node.pre=head;
        node.pre.next=node;
        size++;
        cache.put(node.key,node);
    }
    private void deleteOldestNode(){
        Node node=tail.pre;
        tail.pre=node.pre;
        tail.pre.next=tail;
        cache.remove(node.key);
        size--;
    }
    private void moveToHead(Node node){
        node.pre.next=node.next;
        node.next.pre=node.pre;
        node.next=head.next;
        node.next.pre=node;
        node.pre=head;
        head.next=node;
    }
    public class Node{
        int key;
        int val;
        Node pre;
        Node next;
        public Node(){}
        public Node(int _key,int _val){
            this.key=_key;
            this.val=_val;
        }
    }
}
/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

LFU算法

解析
题目

public class LFUCache {
  HashMap<Integer,Integer> keyToVal=new HashMap<>();
  HashMap<Integer,Integer> keyToFreq=new HashMap<>();
  HashMap<Integer, LinkedHashSet<Integer>> freqToKeys=new HashMap<>();
  int minFreq;
  int capacity;
  public LFUCache(int capacity) {
    this.capacity=capacity;
    this.minFreq=0;
  }
  public int get(int key) {
    if(!keyToVal.containsKey(key)) return -1;
    increaseFreq(key);
    return keyToVal.get(key);
  }
  public void put(int key, int value) {
    if(this.capacity<=0) return;
    if(keyToVal.containsKey(key)){
      keyToVal.put(key,value);
      increaseFreq(key);
    }else{
      if(this.capacity==keyToVal.size()) deleteKey();
      keyToVal.put(key,value);
      keyToFreq.put(key,1);
      freqToKeys.putIfAbsent(1,new LinkedHashSet<>());
      freqToKeys.get(1).add(key);
      this.minFreq=1;
    }
  }
  private void increaseFreq(int key){
    int freq=keyToFreq.get(key);
    keyToFreq.put(key,freq+1);
    // 将 key 加入 freq + 1 对应的列表中
    freqToKeys.putIfAbsent(freq+1,new LinkedHashSet<>());
    freqToKeys.get(freq+1).add(key);
    // 将 key 从 freq 对应的列表中删除
    LinkedHashSet<Integer> keySet=freqToKeys.get(freq);
    keySet.remove(key);
    // 如果 freq 对应的列表空了，移除这个 freq
    if(keySet.isEmpty()){
      freqToKeys.remove(freq);
       // 如果这个 freq 恰好是 minFreq，更新 minFreq
      if(freq==minFreq) minFreq++;
    }
  }
  private void deleteKey(){
    // freq 最小的 key 列表
    LinkedHashSet<Integer> keySet=freqToKeys.get(minFreq);
    // 其中最先被插入的那个 key 就是该被淘汰的 key
    int deletedKey=keySet.iterator().next();
    keySet.remove(deletedKey);
    if(keySet.isEmpty()) freqToKeys.remove(minFreq);
    //在这里不需要像increaseFreq函数里面那样去更新minFreq，因为只有在插入新值的时候，会执行delete
    //而插入新缓存后，put函数会更新minFreq为1
    keyToVal.remove(deletedKey);
    keyToFreq.remove(deletedKey);
  }
}

最大频率栈

解析
题目

public class FreqStack {
  int maxFreq;
  HashMap<Integer, Integer> valToFreq = new HashMap<>();
  HashMap<Integer, Stack<Integer>> freqToVals = new HashMap<>();
  public FreqStack() {
    this.maxFreq = 0;
  }
  public void push(int val) {
    int freq = valToFreq.getOrDefault(val, 0)+1;
    valToFreq.put(val, freq);
    freqToVals.putIfAbsent(freq,new Stack<>());
    freqToVals.get(freq).push(val);
    maxFreq=Math.max(maxFreq,freq);
  }
  public int pop() {
    Stack<Integer> stack=freqToVals.get(maxFreq);
    int res=stack.pop();
    int freq=valToFreq.get(res)-1;
    valToFreq.put(res,freq);
    if(stack.isEmpty()) maxFreq--;
    return res;
  }
}