Got Time Limit Exceeded error. Please help!!!


  • 0
    H
    import java.util.Hashtable;
    

    public class LRUCache {
    private int currentSize;
    private int capacity;
    private Node first;
    private Node last;
    private Hashtable<Integer, Node> hashtable;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.currentSize = 0;
        this.first = null;
        this.last = null;
        this.hashtable = new Hashtable<Integer, Node>();
    }
    
    public int get(int key) {
        if (this.hashtable.containsKey(new Integer(key))) {
            // move the node to head
            Node node = this.hashtable.get(new Integer(key));
            moveNodeToHead(node);
            // return the node's value
            return node.val;
        } else {
            return -1;
        }
    }
    
    public void set(int key, int value) {
        Node node = null;
        if (this.hashtable.containsKey(new Integer(key))) {
            node = this.hashtable.get(new Integer(key));
            node.val = value;
        } else {
        	if (this.currentSize >= this.capacity) {
                // remove last, no need to change currentSize because it's already full
                removeLast();
            } else {
                this.currentSize++;
            }
            // create new node
            node = new Node(key, value);
        }
        // move to head
        moveNodeToHead(node);
        this.hashtable.put(new Integer(key), node);
    }
    
    public void moveNodeToHead(Node node) {
        // if node is already head, no need to move
        if (node == first) {
            return;
        }
        // free the node
        if (node.prev != null) {
            node.prev.next = node.next;
        }
        if (node.next != null) {
            node.next.prev = node.prev;
        }
        // if the node is last, need to move last to prev
        if (node == last) {
            if (last.prev != null) {
                last = last.prev;    
            } else {
                return;
            }
        }
        // connect node and fist
        if (first != null) {
            node.next = first;
            first.prev = node;
        } else {
            first = node;
            last = node;
        }
    }
    
    public void removeLast() {
        if (last == null) {
            return;
        }
        this.hashtable.remove(last.key);
        if (last.prev != null) {
            last = last.prev;
        } else {
            // meaning only 1 element in cache
            last = null;
            first = null;
        }
    }
    
    class Node {
        private Node prev;
        private Node next;
        private int key;
        private int val;
        public Node(int key, int value) {
            this.prev = null;
            this.next = null;
            this.key = key;
            this.val = value;
        }
    }
    

    }


  • 0
    S

    Pay attention to "Writing code? Select all code then click on the {} button to preserve code formatting.” above text editor.


Log in to reply
 

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