Very simple solution using a linked list


  • 0
    A

    My idea was simple. I defined an item class for a pair of key and value, and used a linked list.

    When I "get" an item

    1. If the item exists in the list, move it to last.
    2. return item or null

    When I "put" an item

    1. "get" the item
    2. if found, update value.
    3. else, add new item to last. If queue size grows beyond capacity, remove first item.
    
    public class LRUCache {
    
        static class Item {
            
            public int key, value;
            
            Item( int k, int v ) {
                
                key = k;
                value = v;
                
            }
    
    	@Override
    	public String toString() {
    
    		return "Item [key=" + key + ", value=" + value + "]";
    
    	}
            
        }
        
        Deque<Item> queue;
        int capacity;
    
        public LRUCache(int capacity) {
            
        	this.capacity = capacity;
        	this.queue = new ArrayDeque<Item>( capacity );
        	
        }
    
        public Item getItem(int key) {
            
        	Item item = null;
        	
        	Iterator<Item> iterator = queue.iterator();
        	Item i;
    
        	while ( iterator.hasNext() ) {
        		
        		i= iterator.next();
        		
        		if ( i.key == key ) {
        			
        			item = i;
        			break;
        			
        		}
        	}
        	if ( item != null ) {
    
        		queue.remove( item );
        		queue.addLast( item );
        		
        	}
        	return item;
        	
        }
        
        public void putItem( int key, int val ) {
        	
        	Item item = getItem( key );
        	
        	if ( null != item ) {
        		
        		item.value = val;
        		return;
        		
        	}
        	
        	queue.addLast( new Item( key, val ) );
        	
        	if ( queue.size() > capacity )
        		queue.removeFirst();
        	
        }
        
        public int get(int key) {
            
        	Item item = getItem( key );
        	
        	if ( null == item )
        		return -1;
        	
        	return item.value;
        }
        public void put(int key, int value) {
            putItem( key, value );
        }
    }
    
    

    You can optimize the lookup time by using a Map. But this is the core idea and I kept it simple so that you can understand it.


Log in to reply
 

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