Java solution (AC), is this easy to understand?


  • 0
    V
     public class LRUCache {
        int capacity;
        Node head;
        Node end;
        Map<Integer, Node> map;
    
        public LRUCache(int capacity) {
            this.capacity = capacity;
            this.head = null;
            this.end = null;
            this.map = new HashMap<Integer, Node>();
        }
    
        public void moveNodeToHead(Node n) {
            if(this.head != n) {
                if(n == this.end) {
                    this.end = n.prev;
                    n.prev.next = null;
                }
                else if(this.map.containsKey(n.key)) {
                    n.prev.next = n.next;
                    n.next.prev = n.prev;
                }
                // move node to the head
                n.next = this.head;
                n.prev = null;
                this.head.prev = n;
                this.head = n;
            }
        }
    
        public int get(int key) {
            if(map.containsKey(key)) {
                // move node to the head
                moveNodeToHead(map.get(key));
                return map.get(key).value;
            }
            else {
                return -1;
            }
        }
    
        public void set(int key, int value) {
            if(map.containsKey(key)) {
                Node n = map.get(key);
                // move node to the head
                moveNodeToHead(map.get(key));
                // update node
                n.value = value;
            }
            else {
                Node n;
                if(map.size() < this.capacity) {
                    // create a new node
                    n = new Node();
                    // update head/end if this is the first node
                    if(map.size() == 0) {
                        this.head = n;
                        this.end = n;
                    }
                }
                else{
                    n = this.end;
                    // remove key -> node from the map
                    map.remove(n.key);
                }
                // update node with key/value
                n.key = key;
                n.value = value;
                // move last node to the head
                moveNodeToHead(n);
                // add key -> node to the map
                map.put(key,n);
            }
        }
    }
    
    
    class Node {
        Node next;
        Node prev;
        int value;
        int key;
    }
    

Log in to reply
 

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