My code end with Time Limit Exceede. Who can help me?


  • 0
    D
     import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.Map;
    import java.util.PriorityQueue;
    import java.util.Set;
    
    
    public class LRUCache {
    	 private int capacity=10;
    	 private int recentNum=0;
    	 
    	 private LinkedList<Integer> doubleListOfKey=new LinkedList<Integer>();
    	 private HashMap<Integer,Integer>keyValue=new HashMap<Integer,Integer>();
    	 public LRUCache(int capacity) {
    	        this.capacity=capacity;
    	    }
    	    
    	    public int get(int key) {
    	    	if(!keyValue.containsKey(key))return -1;
    			Integer value=keyValue.get(key);
     
    	         doubleListOfKey.remove(new Integer(key));
    	         doubleListOfKey.addFirst(key);
    	         return value;
    	       
    	    }
    	    
    	    public void set(int key, int value) {
    	    	if(keyValue.containsKey(key))keyValue.put(key, value);
    	    	else
    	    	{
    	    		if(recentNum==capacity)
    	    			{
    	    			 keyValue.remove(doubleListOfKey.removeLast());
    	    			 keyValue.put(key, value);
    	    			}
    	    		else {
    	    			recentNum++;
    	    			keyValue.put(key, value);
    	    		}	
    	    	}	    	
    	    	doubleListOfKey.remove(new Integer(key));
    	    	doubleListOfKey.addFirst(key);
    	    }
    
    	
    }

  • 0
    T

    I believe the reason is traversing a linked list is slow. You can use LinkedHashMap that combines the advantages of both Linkedlist and Hashmap. Here is my code for your reference:

    private LinkedHashMap<Integer, Integer> cache;
    private int capacity;
    
    public LRUCache(int capacity) {
    	this.cache = new LinkedHashMap<Integer, Integer>(capacity);
    	this.capacity = capacity;
    }
    
        public int get(int key) {
    	if(cache.containsKey(key)){
    		int ret = (int)cache.get(key);
    		cache.remove(key);
    		cache.put(key, ret);
    		return ret;
    	}
    	return -1;
    }
    
    public void set(int key, int value) {
    	if(cache.containsKey(key)) {
    		cache.remove(key);
    		cache.put(key, value);
    	}
    	else { 
    		if(cache.size() == capacity) {
    			cache.remove(cache.entrySet().iterator().next().getKey());
    		}
    		cache.put(key, value);
    	}
    }

  • 0
    D

    Thanks for your answer. I used LinkedHashMap and the code works well.


Log in to reply
 

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