Share my accepted java solution


  • 0
    M
    public class LRUCache {
    
    private final HashMap<Integer, Item> map = new HashMap<>();
    private Item head,tail;
    private final int cap;
    
    public LRUCache(int capacity) {
        cap = capacity;
        head = null;
        tail = null;
    }
    
    public int get(int key) {
    	Item i = map.get(key);
    	if(i==null) return -1;
    	if(i==head) return i.value;
    	promote(i);
    	return i.value;
    }
    
    public void set(int key, int value) {
        Item item = map.get(key);
        if(item==head && head!=null)
            item.value = value;
        else if(item!=null){
            item.value = value;
            promote(item);
        }else{
            add(key, value);
            if(map.size()>cap){
                remove(tail);
            }            
        }
        
    }
    private void promote(Item item){
        if(item==tail){
            item.prev.next = item.next;
            tail = item.prev;
        }else{
            item.prev.next = item.next;
            item.next.prev = item.prev;
        }
        item.next = head;
        head.prev = item;
        head = item;        
    }
    private void remove(Item item){
        if(item==head){
            head = null;
            tail = null;
        }
        else if(item==tail){
            item.prev.next = item.next;
            tail = item.prev;
        }else{
            item.prev.next = item.next;
            item.next.prev = item.prev;
        }
        map.remove(item.key);
        return;
    }
    private Item add(Item newitem){
        if(map.size()==0){
            head = newitem;
            tail = newitem;
        }else{
            newitem.next = head;
            head.prev = newitem;
            head = newitem;
        }
        map.put(newitem.key, newitem);
        return newitem;
      	
    }
    private Item add(int key, int value){
        Item newitem = new Item(key,value);
        return add(newitem);
    }
    

    }

    class Item{
    int key;
    int value;
    Item next;
    Item prev;
    
    Item(int k, int v){
    	key   = k;
    	value = v;
    	next = null;
    	prev = null;
    }
    public String toString() {
        return key + " " + value + " ";
    }
    

    }


Log in to reply
 

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