My O(1) solution in java, easy to understand!


  • 0

    To solve this problem, I keep two maps and a value;
    map1 : HashMap<Integer,ListNode>, used to store node key and the node
    map2: HashMap<Integer,Pair>, a Pair represent to a double linked-list(head, tail). The key is time "t" and value is a linked-list storing nodes who has been called "t" times;

    value low: keep the smallest time. Use this value to make a decision which node we should delete.

    hope it helps~

    public class LFUCache {
        public class ListNode {
            ListNode pre;
            ListNode next;
            int id;
            int val;
            int time;
            public ListNode(int id , int val , int time) {
                this.id = id;
                this.val = val;
                this.time = time;
            }
        }
        public class Pair {
            ListNode head;
            ListNode tail;
            public Pair(ListNode head , ListNode tail) {
                this.head = head;
                this.tail = tail;
            }
        }
        HashMap<Integer,ListNode> map = new HashMap<Integer,ListNode>();
        HashMap<Integer,Pair> timemap = new HashMap<Integer,Pair>();
        int capacity;
        int low = -1;
        public LFUCache(int capacity) {
            this.capacity = capacity;
        }
        
        public int get(int key) {
            if(capacity <= 0 || !map.containsKey(key)) return -1;
            int res = map.get(key).val;
            ListNode node = map.get(key);
            int time = node.time;
            Pair p = timemap.get(time);
            //doing original node remove
            if(node.pre == p.head && node.next == p.tail) {
                timemap.remove(time);
                if(low == time) {
                    low++;
                }
            }else {
                ListNode tp = node.pre;
                ListNode tn = node.next;
                tp.next = tn;
                tn.pre = tp;
            }
            
            //doning new node insert
            ListNode newnode = new ListNode(key , res , time+1);
            if(timemap.containsKey(time+1)) {
               Pair p2 = timemap.get(time+1);
               ListNode t = p2.head.next;
                
               p2.head.next = newnode;
               t.pre = newnode;
               
               newnode.next = t;
               newnode.pre = p2.head;
            }else {
                ListNode head = new ListNode(-1 , -1 , -1);
                ListNode tail = new ListNode(-1 , -1 , -1);
                head.next = newnode;
                tail.pre = newnode;
                newnode.next = tail;
                newnode.pre = head;
                timemap.put(time+1 , new Pair(head , tail));
            }
            map.put(key , newnode);
            return res;
        }
        
        public void put(int key, int value) {
            if(capacity <= 0) return;
            if(map.containsKey(key)) {  //remove the original node with original time and insert a new node with time+1
                //doning original node remove
                ListNode node = map.get(key);
                int time = node.time;
                Pair p = timemap.get(time);
                //if it is the only node with key time in the timemap, just remove this timekry from timemap
                if(node.pre == p.head && node.next == p.tail) {
                    timemap.remove(time);
                    if(low == time) {
                        low++;
                    }
                }else {//if it is not the only node, just remove it
                    ListNode tp = node.pre;
                    ListNode tn = node.next;
                    tp.next = tn;
                    tn.pre = tp;
                }
                
                //doning new node insert
                ListNode newnode = new ListNode(key , value , time+1);
                if(timemap.containsKey(time+1)) {
                   Pair p2 = timemap.get(time+1);
                   ListNode t = p2.head.next;
                    
                   p2.head.next = newnode;
                   t.pre = newnode;
                   
                   newnode.next = t;
                   newnode.pre = p2.head;
                }else {
                    ListNode head = new ListNode(-1 , -1 , -1);
                    ListNode tail = new ListNode(-1 , -1 , -1);
                    head.next = newnode;
                    tail.pre = newnode;
                    newnode.next = tail;
                    newnode.pre = head;
                    timemap.put(time+1 , new Pair(head , tail));
                }
                map.put(key , newnode);
                
            }else {
                //doning original node remove
                if(map.size() >= capacity) {
                    Pair p = timemap.get(low);
                    ListNode removenode = p.tail.pre;
                    ListNode n = p.tail.pre.pre;
                    n.next = p.tail;
                    p.tail.pre = n;
                    map.remove(removenode.id);
                    if(p.head.next == p.tail) {
                        timemap.remove(low);
                    }
                }
                low = 1;
                
                //doing new node insert.
                ListNode newnode = new ListNode(key , value , 1);
                if(timemap.containsKey(1)) {
                   Pair p = timemap.get(1);
                   ListNode t = p.head.next;
                    
                   p.head.next = newnode;
                   t.pre = newnode;
                   
                   newnode.next = t;
                   newnode.pre = p.head;
                }else {
                    ListNode head = new ListNode(-1 , -1 , -1);
                    ListNode tail = new ListNode(-1 , -1 , -1);
                    head.next = newnode;
                    tail.pre = newnode;
                    newnode.next = tail;
                    newnode.pre = head;
                    timemap.put(1 , new Pair(head , tail));
                }
                map.put(key , newnode);
            }
        }
    }
    
    /**
     * 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);
     */

Log in to reply
 

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