Java OO solution, 161ms, using one HashMap and double linked list


  • 0
    W

    Similar with other solutions, but using linked list to maintain frequent list, instead of LinkedHashSet.

    public class LFUCache {

    Node root = new Node(0);
    int capacity;
    Map<Integer, Node> map = new HashMap<>();
    
    public LFUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        node.incr();
        return node.data.value;
    }
    
    public void set(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.data.value = value;
            node.incr();
        } else {
            if (map.size() >= capacity) {
                if (root.nextChain != null) {
                    Node node = root.nextNode();
                    node.drop();
                    map.remove(node.data.key);
                }
            }
            if (capacity > map.size()) {
                Node newNode = new Node(root, root, root, key, value);
                newNode.incr();
                map.put(key, newNode);
            }
        }
    }
    

    }

    class Node {

    Node prev, next, head;  //for data node
    Data data;
    Node nextChain;         //for chain node
    int times;
    
    public Node(int n) {
        this.prev = this;
        this.next = this;
        this.times = n;
    }
    
    public Node(Node head, Node prev, Node next) {
        this.head = head;
        this.prev = prev;
        prev.next = this;
        this.next = next;
        next.prev = this;
    }
    
    public Node(Node head, Node prev, Node next, int key, int value) {
        this(head, prev, next);
        this.data = new Data(key, value);
    }
    
    public Node nextNode() {
        Node head = this.nextChain;
        while (head.next == head) {
            this.nextChain = head.nextChain;
            head = head.nextChain;
        }
        return head.next;
    }
    
    public void incr() {
        Node chainHead = this.head;
        int times = head.times;
        this.drop();
        Node nextHead = chainHead.nextChain;
        if (nextHead == null || nextHead.times > times + 1) {
            chainHead.nextChain = new Node(chainHead.times + 1);
            chainHead.nextChain.nextChain = nextHead;
            nextHead = chainHead.nextChain;
        }
        nextHead.addToTail(this);
    }
    
    public void addToTail(Node node) {
        this.prev.next = node;
        node.prev = this.prev;
        this.prev = node;
        node.next = this;
        node.head = this;
    }
    
    public void drop() {
        this.prev.next = this.next;
        this.next.prev = this.prev;
        this.head = null;
    }
    

    }

    class Data {

    int key;
    int value;
    
    public Data(int k, int v) {
        this.key = k;
        this.value = v;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.