Simple Java Solution


  • 0
    H
    public class LRUCache {
        Map<Integer, DLinkNode> cache;
        DLinkNode head;
        DLinkNode tail;
        int capacity;
    
        public LRUCache(int capacity) {
            cache = new HashMap<Integer, DLinkNode>();
            head = new DLinkNode();
            tail = new DLinkNode();
            this.capacity = capacity;
            
            head.prev = null;
            head.next = tail;
            
            tail.prev = head;
            tail.next = null;
        }
        
        public int get(int key) {
            if(cache.containsKey(key)) {
                DLinkNode currNode = cache.get(key);
                currNode.renewNode();
                return currNode.value;
            } else {
                return -1;
            }
        }
        
        public void set(int key, int value) {
            if(cache.containsKey(key)) {
                DLinkNode currNode = cache.get(key);
                currNode.value = value;
                currNode.renewNode();
                cache.put(key, currNode);
            } else {
                if(cache.size() == capacity) {
                    cache.remove(tail.prev.key);
                    tail.prev.removeNode();
                }
                DLinkNode newNode = new DLinkNode();
                newNode.key = key;
                newNode.value = value;
                newNode.addNode();
                cache.put(key, newNode);
            }
        }
        
        public class DLinkNode {
            DLinkNode next = null;
            DLinkNode prev = null;
            int key;
            int value;
            
            public void addNode() {
                DLinkNode post = head.next;
                this.prev = head;
                this.next = post;
                head.next = this;
                post.prev = this;
            }
            
            public void removeNode() {
                DLinkNode pre = this.prev;
                DLinkNode post = this.next;
                pre.next = post;
                post.prev = pre;
            }
            
            public void renewNode() {
                this.removeNode();
                this.addNode();
            }
        }
    }

Log in to reply
 

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