leetcode 146. LRU 缓存-Toy模板网

这篇具有很好参考价值的文章主要介绍了leetcode 146. LRU 缓存。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

2023.10.26

leetcode 146. LRU 缓存,leetcode专栏,leetcode,java,算法,数据结构

本题核心就是要将map中，最近最少操作的那个key给剔除掉，于是我们可以使用双端链表LinkedList 来维护每个元素的操作情况，最近操作的元素就将其移至表头，越久没操作的元素，自然就会沉到表尾。一旦缓存满了，将表尾元素剔除即可。 java代码如下：文章来源地址https://www.toymoban.com/news/detail-719648.html

class LRUCache {
    private int capacity;
    Map<Integer,Integer> map = new HashMap<>();
    LinkedList<Integer> LRUlist = new LinkedList<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            LRUlist.remove((Integer)key);
            LRUlist.addFirst(key);
            return map.get(key);
        } 
        else return -1;
    }
    
    public void put(int key, int value) {
        //找到该元素
        if(map.containsKey(key)){
            LRUlist.remove((Integer)key);
            LRUlist.addFirst(key);
            map.put(key,value); 
        }
        //未找到该元素
        else{
            //map内元素未超出容量,直接put
            if(map.size() < capacity){
                map.put(key,value);
                LRUlist.addFirst(key);
            }
            //map内元素超出容量capacity，先删掉最近最少未使用的元素，再put
            else{
                int temp = LRUlist.removeLast();
                map.remove(temp);
                map.put(key,value);
                LRUlist.addFirst(key);
            }
        }
    }
}

/**
 * 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);
 */

到了这里，关于leetcode 146. LRU 缓存的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！