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


  • 0
    U

    ''' public class LRUCache {
    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;
        
    }
    

    }

    /**

    • 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.