java use one hashmap to solve the LFU cache


  • 0
    J

    import java.util.HashMap;

    public class LFUCache {

    public static void main(String[] args) {
    	LFUCache cache = new LFUCache(0);
    
    	cache.put(1, 1);
    	cache.put(2, 2);
    	cache.get(1); // returns 1
    	cache.put(3, 3); // evicts key 2
    	cache.get(2); // returns -1 (not found)
    	cache.get(3); // returns 3.
    	cache.put(4, 4); // evicts key 1.
    	cache.get(1); // returns -1 (not found)
    	cache.get(3); // returns 3
    	cache.get(4); //
    }
    
    private HashMap<Integer, LFU> hashMap;
    private LFU head = new LFU(-1, -1, Integer.MIN_VALUE);
    private LFU tail = new LFU(-1, -1, Integer.MAX_VALUE);
    private int capacity;
    
    class LFU {
    	int key;
    	int value;
    	int fre = 0;
    	LFU next;
    	LFU front;
    
    	public LFU(int key, int value, int fre) {
    		this.key = key;
    		this.value = value;
    		this.fre = fre;
    	}
    
    }
    
    public LFUCache(int capacity) {
    	hashMap = new HashMap<Integer, LFU>(capacity);
    	head.next = tail;
    	tail.front = head;
    	this.capacity = capacity;
    }
    
    public int get(int key) {
    	if (capacity <= 0)
    		return -1;
    	if (hashMap.containsKey(key)) {
    		hashMap.get(key).fre++;
    		// adjust point
    		adjust(hashMap.get(key));
    		// System.out.println(hashMap.get(key).value);
    		return hashMap.get(key).value;
    	} else {
    		System.out.println(-1);
    		return -1;
    	}
    }
    
    public void put(int key, int value) {
    
    	if (capacity <= 0)
    		return;
    
    	if (hashMap.containsKey(key)) {
    		hashMap.get(key).fre++;
    		hashMap.get(key).value = value;
    		adjust(hashMap.get(key));
    	} else {
    		if (hashMap.size() >= capacity) {
    			// System.out.println("evicts key " + head.next.key);
    			hashMap.remove(head.next.key);
    			head.next = head.next.next;
    			head.next.front = head;
    
    		}
    		LFU tmp = new LFU(key, value, 1);
    
    		Insert(tmp);
    		hashMap.put(key, tmp);
    	}
    }
    
    private void adjust(LFU tmp) {
    
    	if (tmp.next.fre > tmp.fre)
    		return;
    	tmp.front.next = tmp.next;
    	tmp.next.front = tmp.front;
    	tmp.front = null;
    
    	while (tmp.next.fre <= tmp.fre) {
    		tmp.next = tmp.next.next;
    	}
    	tmp.next.front.next = tmp;
    	tmp.front = tmp.next.front;
    	tmp.next.front = tmp;
    }
    
    private void Insert(LFU tmp) {
    	tmp.next = head.next;
    
    	while (tmp.next.fre <= tmp.fre) {
    		tmp.next = tmp.next.next;
    	}
    	tmp.next.front.next = tmp;
    	tmp.front = tmp.next.front;
    	tmp.next.front = tmp;
    
    }
    

    }


Log in to reply
 

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