share my solution with same idea but only one hashmap and linkedList


  • 0
    U
         class node {
            node pre;
            node next;
            int key;
            int value;
            node(int key , int value) {
                this.key = key;
                this.value = value;
            }
            void update(int key, int value) {
                this.key = key;
                this.value = value;
            }
        }
        private final int capacity;
        private node head ;
        private node tail ;
        private Map<Integer , node> map;
        public LRUCache(int capacity) {
            this.capacity = capacity;
            map = new HashMap<Integer , node>(); 
        }
        
        public int get(int key) {
            node temp = map.get(key);
            if(temp == null) {
                return -1;
            }
                remove(temp);
                append(temp);
                return temp.value;
            
        }
        
        public void put(int key, int value) {
            node temp = null;
            if(map.containsKey(key)) {
                temp = map.get(key);
                temp.value = value;
                remove(temp);
                append(temp);
            }else if(map.size() < capacity) {
                temp = new node(key, value);
                append(temp);
            }else {
                temp = tail; 
                remove(temp);
                temp.update(key ,value);
                append(temp);
            }
        }
        private void remove(node temp) {
            map.remove(temp.key);
            if(temp.pre != null) {
                temp.pre.next = temp.next;
            }
            if(temp.next != null) {
                temp.next.pre = temp.pre;
            }
            if(temp == head) {
                head = temp.next;
            }
            if(temp == tail) {
                tail = temp.pre;
            }
            temp.next = temp.pre = null;
            return;
        }
        
        private void append(node temp) {
            map.put(temp.key, temp);
            if(head == null) {
                head = tail = temp;
                //tail = temp;
             
            }else {
                temp.next = head;
                head.pre = temp;
                head = temp;
            }
          return;
            
        }
    
    }
    

Log in to reply
 

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