Accepted Java Solution Without extra space


  • 4
    S

    I use a double-pointer Linked List Node to carry the value. And hashmap would map a key to a Node. Setting a head and end pointer.

    Once a Node is visited, move it right next to head.

    Once capacity is reached, delete the end Node.

    The run time for all is O(1) except deleting a key from hashmap. (need to go through the map to get key by value)

    public class LRUCache {
        int cap;
        int curNum;
        HashMap<Integer,Node> map;
        Node head;
        Node end;
        
        public LRUCache(int capacity) {
             cap = capacity;
             curNum = 0;
             map = new HashMap<Integer,Node>();
             head = new Node(0);
             end = head;
        }
        
        public int get(int key) {
            if(map.get(key) == null){return -1;}
            else{
                // set lst
                Node temp = map.get(key);
                if(head.next != temp){
                    if(end == temp){end = temp.pre;}
                    temp.pre.next = temp.next;
                    if(temp.next != null)
                        temp.next.pre = temp.pre;
                    
                    head.next.pre = temp;
                    temp.next = head.next;
                    head.next = temp;
                    temp.pre = head;
                }
                // return value
                return temp.value;
            }
        }
        
        public void set(int key, int value) {
            if(map.get(key)== null){
                // insert
                if(curNum < cap){
                    curNum++;
                }else{
                    // remove from map
                    for (Map.Entry<Integer, Node> entry : map.entrySet()) {
                        if (entry.getValue() == end) {
                            map.remove(entry.getKey());
                            break;
                        }
                    }
                    
                    end.pre.next = null;
                    end = end.pre;
                }
                Node newNode = new Node(value);
                // set map
                map.put(key,newNode);
                // set lst
                newNode.next = head.next;
                newNode.pre = head;
                if(head == end){
                    end = newNode;
                }
                else{
                    head.next.pre = newNode;
                }
                head.next = newNode;
            }else{
                // change
                // set map
                Node temp = map.get(key);
                temp.value = value;
                // set lst
                if(head.next != temp){
                    if(end == temp){end = temp.pre;}
                    temp.pre.next = temp.next;
                    if(temp.next != null)
                        temp.next.pre = temp.pre;
                    
                    head.next.pre = temp;
                    temp.next = head.next;
                    head.next = temp;
                    temp.pre = head;
                }
            }
        }
    }
    
    class Node{
        int value;
        Node pre;
        Node next;
        Node(int x){value = x;}
    }

  • 0
    W

    and you made an awesome point! I voted up . quick question, instead of haing newNode with value only , can we create an inner class like Pair(int key, int value) ? when we setValue(key, value), we just get the Pair form hashmap.get(key), and update the value , or create new Pair attach it on the head. does that make sense ? I dont have it implemented, just a quick curious quesiton. thanks. Again, awesome code.


  • 0
    S

    Based on my understanding of what you describe, a new class Pair(int key, int value) is exactly what I implement it as class Node. The reason why I don't make a (int key) for class Node is the HashMap do that for me. I am actually mapping (int key, int value) pairs but wrap the "value" in a new class.


  • 0
    W

    yeah, right . i have to say, use double linked list to restore the order, and hashMap to offer O(1) search without worrying about order, is really smart.


Log in to reply
 

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