doublelinkedlist and hashmap (update the list may take o(n) time)


  • 0
    L
        private class Node{
            int key, value,access;
            Node prev, next;
            Node(int k, int v,int a){
                this.key = k;
                this.value = v;
                this.access =0;
            }
            Node(){
                this(0, 0,0);
            }
        }
        
        private int capacity, count;
        private Map<Integer, Node> map;
        private Node head, tail;
    
        // @param capacity, an integer
        public LFUCache(int capacity) {
            // Write your code here
            this.capacity = capacity;
            this.count = 0;
            map = new HashMap<>();
            head = new Node();
            tail = new Node();
            head.next = tail;head.access=Integer.MAX_VALUE;
            tail.prev = head;tail.access=Integer.MIN_VALUE;
        }
    
        // @param key, an integer
        // @param value, an integer
        // @return nothing
        public void set(int key, int value) {
            // Write your code here
            Node n = map.get(key);
            if(null==n){
                if(count==capacity){
                    Node toDel = tail.prev;
                    remove(toDel);
                    map.remove(toDel.key);
                    --count;
                }
                n = new Node(key, value,0);
                map.put(key, n);
                add(n);
                ++count;
            }
            else{
                n.value = value;
                n.access++;
                update(n);
            }
            
        }
    
        public int get(int key) {
            // Write your code here
            Node n = map.get(key);
            if(null==n){
                return -1;
            }
            n.access++;
            update(n);
            return n.value;
        }
        
        private void update(Node node){
            remove(node);
            add(node);
        }
        private void add(Node node){
            Node cur=head;
            while(node.access<cur.access){
                cur=cur.next;
            }
    
            Node before =cur.prev;
            before.next = node;
            node.prev = before;
            node.next = cur;
            cur.prev = node;
        }
        
        private void remove(Node node){
            Node before = node.prev, after = node.next;
            before.next = after;
            after.prev = before;
        }
        
    

Log in to reply
 

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