Java solution, utilize get() to finish put() , with proper explanation


  • 0
    public class LRUCache {
        class Node{
            Node pre;
            Node next;
            int val;
            int key;
            public Node(int value, int key){
                val = value;
                this.key = key;
                pre = null;
                next = null;
            }
        }
        int count;
        int capacity;
        Node head;
        Node tail;
        Map<Integer, Node>map;//key -> Node
        public LRUCache(int capacity) {
            this.capacity = capacity;
            count = 0;
            head = null;
            tail = null;
            map = new HashMap<Integer, Node>();
        }
        
        public int get(int key) {
            if(capacity == 0)
                return -1;
            if(!map.containsKey(key))
                return -1;
            else{
                Node cur = map.get(key);
                if(cur == tail){//cur is the tail
                    return cur.val;
                }
                else{//cur is not tail
                    if(cur == head){//cur is head
                        if(capacity == 1)//there is only one node
                            return cur.val;
                        else{//there is at least two node;
                            head = head.next;
                            head.pre = null;
                            tail.next = cur;
                            cur.pre = tail;
                            tail = cur;
                            tail.next = null;//change the link
                            return cur.val;
                        }
                    }
                    else{//cur is neither head nor tail
                        cur.pre.next = cur.next;
                        cur.next.pre = cur.pre;
                        tail.next = cur;
                        cur.pre = tail;
                        tail = cur;
                        tail.next = null;
                        return cur.val;
                    }
                }
            }
        }
        
        public void put(int key, int value) {
            if(capacity == 0)
                return;
            if(!map.containsKey(key)){//there is no such key
                if(tail == null){//the cache is empty;
                    Node cur = new Node(value, key);
                    tail = cur;//link
                    head = cur;
                    map.put(key, cur);//map
                    count++;//count
                }
                else{//the cache is not empty
                    if(count < capacity){//the cache is not full
                        Node cur = new Node(value, key);
                        tail.next = cur;//link
                        cur.pre = tail;
                        tail = cur;
                        map.put(key, cur);//map
                        count++;//count
                    }
                    else{//the cache is full
                        Node cur = new Node(value, key);
                        map.remove(head.key);//map delete head
                        tail.next = cur;
                        cur.pre = tail;
                        tail = cur;
                        head = head.next;
                        head.pre = null;//link
                        map.put(key, cur);//map
                        //no need to change count;
                    }
                }
            }
            else{//there is such key
                this.get(key);//put the node to the end
                tail.val = value;
            }
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */
    

Log in to reply
 

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