LeetCode(59) -- 146

P146. LRU Cache (Medium)

最不常用的内存，如果空间不够用，就把它覆盖掉。

我的思路

内存用map来存数据，然后再用一个queue来保证每次取出来的，都是最不常用的那个。

我的代码

class LRUCache {

    private int capacity;

    private Map<Integer, Integer> cache;

    private Queue<Integer> queue;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>();
        queue = new LinkedList<>();
    }

    public int get(int key) {
        if (!cache.containsKey(key)) {
            return -1;
        }
        queue.remove(key);
        queue.add(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            cache.put(key, value);
            queue.remove(key);
            queue.add(key);
        } else {
            if (cache.size() < capacity) {
                cache.put(key, value);
            } else {
                Integer least = queue.poll();
                cache.remove(least);
                cache.put(key, value);
            }
            queue.add(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);
 */

10%

答案

解法1：

class LRUCache extends LinkedHashMap<Integer, Integer>{
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);//三个参数分别是：初始容量、负载因子、是否基于访问排序。
        this.capacity = capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }
}

居然还有这种操作？

HashMap是无序的，当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了。

https://www.jianshu.com/p/8f4f58b4b8ab

最优解

class LRUCache {
    //head and tail are dummy nodes
    final Node head= new Node();
    final Node tail = new Node();
    Map<Integer, Node> map;
    int cache_capacity;

    class Node{
        int key;
        int val;
        Node prev;
        Node next;
    }
    public LRUCache(int capacity) {
        map = new HashMap<>(cache_capacity);
        this.cache_capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    //add node at the front of the list
    //add this node as the real head
    public void add(Node node){
        Node head_next = head.next;
        head.next = node;
        node.prev = head;
        node.next = head_next;
        head_next.prev = node;
    }

    //add remove the node at the end of the list
    //adding this node as the real tail
    public void remove(Node node){
        Node next_node = node.next;
        Node prev_node = node.prev;
        prev_node.next = next_node;
        next_node.prev= prev_node;
    }

    public int get(int key) {
        int result = -1;
        Node node = map.get(key);
        if(node != null){
            result = node.val;
            remove(node); //most recently used node will be added to front
            add(node);
        }
        return result; //node is null
    }

    //add or override
    public void put(int key, int value) {
        Node node = map.get(key);
        if (node != null){ //already exists
            remove(node); //remove the old node
            node.val = value; //update the value
            //most recenlty used node will be
            //moved to the front, least recently used gets deleted
            add(node);
        } else {
            //first remove the last key
            if (map.size() == cache_capacity){
                map.remove(tail.prev.key); //remove from the tail in the map
                remove(tail.prev); //remove from linkedlist
            }
            Node newNode= new Node();
            newNode.key = key;
            newNode.val = value;
            map.put(key, newNode); //add to map
            add(newNode);//addto lilnkedlist
        }
    }
}

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

这个就是自己实现了一个双向链表以及linkedHashMap,只实现了有用的方法。