LeetCode - Medium - 146. LRU Cache

￡神魔★判官ぃ 2022-11-13 14:29 51阅读 0赞

## Topic ##

*  Design
 *  Hash Table
 *  Linked List

## Description ##

[https://leetcode.com/problems/lru-cache/][https_leetcode.com_problems_lru-cache]

Design a data structure that follows the constraints of a **Least Recently Used (LRU) cache**.

Implement the `LRUCache` class:

*  `LRUCache(int capacity)` Initialize the LRU cache with positive size `capacity`.
 *  `int get(int key)` Return the value of the `key` if the key exists, otherwise return `-1`.
 *  `void put(int key, int value)` Update the value of the `key` if the key exists. Otherwise, add the `key-value` pair to the cache. If the number of keys exceeds the `capacity` from this operation, evict the least recently used key.

**Follow up**:  
Could you do `get` and `put` in `O(1)` time complexity?

**Example 1**:

Input
    ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
    [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
    Output
    [null, null, null, 1, null, -1, null, -1, 3, 4]
    
    Explanation
    LRUCache lRUCache = new LRUCache(2);
    lRUCache.put(1, 1); // cache is {1=1}
    lRUCache.put(2, 2); // cache is {1=1, 2=2}
    lRUCache.get(1);    // return 1
    lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3}
    lRUCache.get(2);    // returns -1 (not found)
    lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3}
    lRUCache.get(1);    // return -1 (not found)
    lRUCache.get(3);    // return 3
    lRUCache.get(4);    // return 4

**Constraints**:

*  1 <= `capacity` <= 3000
 *  0 <= `key` <= 3000
 *  0 <= `value` <=  1 0 4 10^4 104
 *  At most 3 \*  1 0 4 10^4 104 calls will be made to `get` and `put`.

## Analysis ##

方法一：利用LinkedHashMap

方法二：哈希表 + 双向链表

## Submission ##

import java.util.HashMap;
    import java.util.LinkedHashMap;
    import java.util.Map;
    
    //方法一
    public class LRUCache { 
    	
    	private LinkedHashMap<Integer, Integer> cache;
    	
        public LRUCache(int capacity) { 
            cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){ 
            	
    			private static final long serialVersionUID = 1L;
    			
    
    			@Override
            	protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) { 
            		return size() > capacity;
            	}
            	
            };
        }
        
        public int get(int key) { 
        	return cache.getOrDefault(key, -1);
        }
        
        public void put(int key, int value) { 
            cache.put(key, value);
        }
        
        @Override
        public String toString() { 
        	return cache.toString();
        }
        
    }
    
    //方法二
    class LRUCache2{ 
    	class Node<K, V>{ 
    		K key;
    		V value;
    		Node<K, V> prev;
    		Node<K, V> next;
    		
    		public Node() { 
    			this.prev = this.next = null;
    		}
    		public Node(K key, V value) { 
    			super();
    			this.key = key;
    			this.value = value;
    		}
    	}
    	
    	class DoublyLinkedList<K, V>{ 
    		Node<K, V> head;
    		Node<K, V> tail;
    		
    		public DoublyLinkedList() { 
    			this.head = new Node<K, V>();
    			this.tail = new Node<K, V>();
    			this.head.next = this.tail;
    			this.tail.prev = this.head;
    		}
    		
    		public void addHead(Node<K, V> node) { 
    			node.next = this.head.next;
    			node.prev = this.head;
    			this.head.next.prev = node;
    			this.head.next = node;
    		}
    		
    		public void removeNode(Node<K, V> node) { 
    			node.prev.next = node.next;
    			node.next.prev = node.prev;
    			node.prev = null;
    			node.next = null;
    
    		}
    		
    		public Node<K, V> getLast() { 
    			if(this.tail.prev == this.head)
    				return null;
    			return this.tail.prev;
    		}
    
    	}
    	
    	private int cacheSize;
    	private Map<Integer, Node<Integer, Integer>> map;
    	private DoublyLinkedList<Integer, Integer> doublyLinkedList;
    	
    	
    	public LRUCache2(int cacheSize) { 
    		this.cacheSize = cacheSize;
    		map = new HashMap<>();
    		doublyLinkedList = new DoublyLinkedList<>();
    	}
    
    	public int get(int key) { 
    		if(!map.containsKey(key)) { 
    			return -1;
    		}
    		
    		Node<Integer, Integer> node = map.get(key);
    		doublyLinkedList.removeNode(node);
    		doublyLinkedList.addHead(node);
    		
    		return node.value;
    	}
    	
    	public void put(int key, int value) { 
    		
    		if(map.containsKey(key)) { 
    			
    			Node<Integer, Integer> node = map.get(key);
    			node.value = value;
    			map.put(key, node);
    			
    			doublyLinkedList.removeNode(node);
    			doublyLinkedList.addHead(node);
    		}else { 
    			
    			if(map.size() == cacheSize) { 
    				Node<Integer, Integer> lastNode = doublyLinkedList.getLast();
    				map.remove(lastNode.key);
    				doublyLinkedList.removeNode(lastNode);
    			}
    			
    			Node<Integer, Integer> newNode = new Node<>(key, value);
    			map.put(key, newNode);
    			doublyLinkedList.addHead(newNode);
    		}
    	}
    }

## Test ##

import static org.junit.Assert.*;
    
    
    import org.junit.Test;
    
    public class LRUCacheTest { 
    
    	@Test
    	public void test() { 
    		LRUCache obj = new LRUCache(2);
    
    		obj.put(1, 1);
    		obj.put(2, 2);
    		assertEquals(1, obj.get(1));
    		obj.put(3, 3);
    		assertEquals(-1, obj.get(2));
    		//System.out.println(obj);
    		
    		obj.put(4, 4);
    		assertEquals(-1, obj.get(1));
    		assertEquals(3, obj.get(3));
    		assertEquals(4, obj.get(4));
    	}
    	
    	@Test
    	public void test2() { 
    		LRUCache2 obj = new LRUCache2(2);
    		
    		obj.put(1, 1);
    		obj.put(2, 2);
    		assertEquals(1, obj.get(1));
    		obj.put(3, 3);
    		assertEquals(-1, obj.get(2));
    		//System.out.println(obj);
    		
    		obj.put(4, 4);
    		assertEquals(-1, obj.get(1));
    		assertEquals(3, obj.get(3));
    		assertEquals(4, obj.get(4));
    	}
    }

[https_leetcode.com_problems_lru-cache]: https://leetcode.com/problems/lru-cache/