December 01, 2019

460. LFU Cache

思路：

1) 记录每个key被访问的次数
2) 同访问次数的节点的先后顺序：用双向链表, add和remove都是常数时间
3) 记录Cache的大小，超出capacity要remove LFU Cache

在 146. LRU Cache 中，用一个双向链表添加和删除即可。在LFU Cache中，还需要记录访问了多少次。可以对于每个Node对于每个key记录它的访问次数。 O(1)时间获得同访问次数的节点的先后顺序：用hashmap，访问次序为key，被访问整个次数的Node形成的双向链表为value。

API设计：

get(key):

If key exist: freq++ 从 freq的map里取出加到freq+1的map里;
If key does not exist: return -1;

put(key, val):

If key exists: 1) modify node value 2) call get(key) 更新后要再调用get更新freq
If key does not exist: add a new node to the cache (if necessary, evict a node)

数据结构：
1) Node: 要记录count，代表这个Node被访问过多少次, prev/next形成双向链表 (同 LRU Cache)
2) Doubly Linked List, 用 Dummy head/tail (同 LRU Cache), 另外存双向链表len, 便于put/delete node
3) Map<Integer, Node> map: 存key和node的对应关系 (同 LRU Cache)
4) Map<Integer, DDList> freqMap

参考这个讲解视频.

class LFUCache {
    class Node {
        int key, val;
        int cnt;
        Node prev, next;
        public Node (int k, int v) {
            key = k;
            val = v;
            cnt = 1;
        }
    }
    
    class DLList {
        Node head, tail;
        int len;

        public DLList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
            len = 0;
        }
        
        public void addHead(Node node) {
            Node next = head.next;
            head.next = node;
            node.prev = head;
            node.next = next;
            next.prev = node;
            map.put(node.key, node);
            len++;
        }
        
        public void remove(Node node) {
            Node prev = node.prev;
            Node next = node.next;
            prev.next = next;
            next.prev = prev;
            len--;
            map.remove(node.key);
        }
        
        public void removeTail() {
            Node prevTail = tail.prev;
            remove(prevTail);
        }
    }
    
    Map<Integer, Node> map;
    Map<Integer, DLList> freq;
    int size, capacity;
    int maxFreq;

    public LFUCache(int capacity) {
        map = new HashMap<>();
        freq = new HashMap<>();
        this.capacity = capacity;
        size = 0;
        maxFreq = 0;
    }
    
    public int get(int key) {
        if (map.get(key) == null) {
            return -1;
        }
        Node node = map.get(key);
        int prevFreq = node.cnt;
        DLList prevList = freq.get(prevFreq);
        prevList.remove(node);
        
        int curFreq = prevFreq + 1;
        maxFreq = Math.max(maxFreq, curFreq);
        DLList curList = freq.getOrDefault(curFreq, new DLList());
        node.cnt++;
        curList.addHead(node);
        
        freq.put(prevFreq, prevList);
        freq.put(curFreq, curList);
        return node.val;
    }
    
    public void put(int key, int value) {
        if (capacity == 0) {
            return;
        }
        if (map.get(key) != null) {
            map.get(key).val = value;
            get(key);
            return;
        }
        Node node = new Node(key, value);
        DLList curList = freq.getOrDefault(1, new DLList());
        curList.addHead(node);
        size++;
        
        if (size > capacity) {
            if (curList.len > 1) {
                curList.removeTail();
            } else {
                for (int i = 2; i <= maxFreq; i++) {
                    if (freq.get(i) != null && freq.get(i).len > 0) {
                        freq.get(i).removeTail();
                        break;
                    }
                }
            }
            size --;
        }
        freq.put(1, curList);
    }
}

/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */