77.LRU Cache（最近最久未使用算法）

骑猪看日落 2021-11-29 07:50 192阅读 0赞

#### Level： ####

Hard

#### 题目描述： ####

Design and implement a data structure for [Least Recently Used (LRU) cache][Least Recently Used _LRU_ cache]. It should support the following operations: `get` and `put`.

`get(key)` \- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.  
`put(key, value)` \- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

**Follow up:**  
Could you do both operations in **O(1)** time complexity?

**Example:**

LRUCache cache = new LRUCache( 2 /* capacity */ );
    
    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.put(4, 4);    // evicts key 1
    cache.get(1);       // returns -1 (not found)
    cache.get(3);       // returns 3
    cache.get(4);       // returns 4

#### 思路分析： ####

设置一个map存放对应的键和值，同时设置一个双向链表，来保存最近最久未使用的关系，如果访问一个键，键存在于map中，访问完成后，我们在链表中将该键删除，然后将其添加到链表的首部，表示最近刚访问过这个键，当缓存满了后，如果要添加一个键值对，我们要删除的就是位于链表尾部的键和其对应的值，因为它是最久未访问的值。

#### 代码： ####

class LRUCache {
        HashMap<Integer,Integer>cache=new HashMap<>();
        LinkedList<Integer>keys=new LinkedList<>();
        private static int sizeOfCache;
        public LRUCache(int capacity) {
            sizeOfCache=capacity;
        }
        
        public int get(int key) {
            if(cache.get(key)!=null){
                keys.remove(Integer.valueOf(key));//先在链表中删掉该键
                keys.addFirst(key); //然后将该键放到链表首部，表示刚被访问
                return cache.get(key);
            }
            return -1;
        }
        
        public void put(int key, int value) {
            if(cache.get(key)!=null)
                keys.remove(Integer.valueOf(key));
            else if(keys.size()==sizeOfCache){ //存储块已满
                int keyToRemove=keys.removeLast(); //链表最后一个键，代表最久未访问。
                cache.remove(keyToRemove);
            }
            keys.addFirst(key);
            cache.put(key,value);
        }
    }
    
    /**
     * Your LRUCache object will be instantiated and called as such:
     * LRUCache obj = new LRUCache(capacity);
     * int param_1 = obj.get(key);
     * obj.put(key,value);
     */

转载于:https://www.cnblogs.com/yjxyy/p/11098732.html

[Least Recently Used _LRU_ cache]: https://en.wikipedia.org/wiki/Cache_replacement_policies#LRU