本文共 2976 字，大约阅读时间需要 9 分钟。

链接：https://leetcode-cn.com/problems/lru-cache/

// 思路：// 1.java中LinkedHashMap,实现就是题解的一种类型，需要重写removeEldestEntry方法，初始化时将按照读取顺序设置为true// 2.通过 hashmap 和 LinkedList (双向链表) 实现// 第一种：// class LRUCache {
   //     int capacity;//     LinkedHashMap
   
     cache;//     public LRUCache(int capacity) {
   //         this.capacity = capacity;//         cache = new LinkedHashMap
    
     (capacity, 0.75f, true){
   //             @Override//             protected boolean removeEldestEntry(Map.Entry eldest){
   //                 return cache.size() > capacity;//             }//         };//     }    //     public int get(int key) {
   //         return cache.getOrDefault(key, -1);//     }    //     public void put(int key, int value) {
   //         cache.put(key, value);//     }// }// 第二种：class LRUCache {
       class DLinkedNode {
           int key;        int value;        DLinkedNode prev;        DLinkedNode next;        public DLinkedNode() {
   }        public DLinkedNode(int _key, int _value) {
   key = _key; value = _value;}    }    private Map
     
       cache = new HashMap
      
       ();    private int size;    private int capacity;    private DLinkedNode head, tail;    public LRUCache(int capacity) {
           this.size = 0;        this.capacity = capacity;        // 使用头伪节点和伪尾节点        head = new DLinkedNode();        tail = new DLinkedNode();        head.next = tail;        tail.prev = head;    }        public int get(int key) {
           DLinkedNode node = cache.get(key);        // 如果不存在        if(node == null) {
               return -1;        }        // 如果存在，返回数值，并将该节点放到头节点之后        moveToHead(node);        return node.value;    }        public void put(int key, int value) {
           DLinkedNode node = cache.get(key);        // 如果已存在        if(node != null) {
               node.value = value;            moveToHead(node);        }else {
                //  如果不存在            DLinkedNode newNode = new DLinkedNode(key, value);            cache.put(key, newNode);            addToHead(newNode);            ++size;            if(size > capacity){
                   // 如果size超过容量，删除尾节点，哈希表中删除                DLinkedNode tail = removeTail();                cache.remove(tail.key);                --size;            }        }    }    private void addToHead(DLinkedNode node) {
           node.prev = head;        node.next = head.next;        head.next = node;        node.next.prev = node;    }        private void removeNode(DLinkedNode node) {
           node.prev.next = node.next;        node.next.prev = node.prev;    }    private void moveToHead(DLinkedNode node) {
           removeNode(node);        addToHead(node);            }        private DLinkedNode removeTail() {
           DLinkedNode res = this.tail.prev;        removeNode(res);        return res;    }}/** * 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); */
      
     
    
   

转载地址：http://gtjwi.baihongyu.com/