Just share my clear JAVA code


  • 0
    H

    public class LRUCache {

    // Algo thinking
    //      (1) Use a double LinkedList
    //      (2) Define a new class to hold KV pairs
    //      (3) Use a map to keep track of KV pairs
    
    class KeyValueNode {
        int key, value;
        KeyValueNode before, next;
        public KeyValueNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private int capacity = 0;
    private KeyValueNode head;
    private KeyValueNode tail;
    private Map<Integer, KeyValueNode> referenceMap;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        referenceMap = new HashMap<>();
    }
    
    public int get(int key) {
        
        if (!referenceMap.containsKey(key)) return -1;
        
        KeyValueNode kv = referenceMap.get(key);
        moveToTail(kv);
        
        return kv.value;
    }
    
    public void put(int key, int value) {
        
        if (referenceMap.containsKey(key)) {
            KeyValueNode kv = referenceMap.get(key);
            kv.value = value;       // update value
            moveToTail(kv);
        } else {
            KeyValueNode kv = new KeyValueNode(key, value);
            referenceMap.put(key, kv);
            add(kv);
            if (referenceMap.size() > capacity){
                referenceMap.remove(head.key);
                remove(head);
            } 
        }
    }
    
    private void moveToTail(KeyValueNode kv) {
        remove(kv);
        add(kv);
    }
    
    private void remove(KeyValueNode kv) {
        
        KeyValueNode before = kv.before;
        KeyValueNode next = kv.next;
        
        if (head == kv && tail == kv) {
            head = tail = null;
        } else if (kv == tail) {
            kv.next = null;
            next.before = null;
            tail = next;
        } else if (kv == head) {
            kv.before = null;
            before.next = null;
            head = before;
        } else {
            before.next = next;
            next.before = before;
            kv.before = null;
            kv.next = null;
        }
    }
    
    private void add(KeyValueNode kv) {
        
        if (head == null) {
            head = tail = kv;
        } else {
            kv.next = tail;
            tail.before = kv;
            tail = kv;
        }
    }
    

    }


Log in to reply
 

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