问题描述

Design and implement a data structure for 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.

若执行put()操作时，缓存中元素的数量大于capacity，则删除最近最少使用的元素。

举个例子：

解法1

Thanks [Y总]

先来看下get()和put()操作的流程图：

• get()

• put()

再来看下remove()和insert()操作：

• remove()

• insert()

最后来看下完整实现：

class LRUCache {

    class Node{
        private int key, val;
        private Node left, right;
        public Node(int k, int v){
            this.key = k;
            this.val = v;
            this.left  = null;
            this.right = null;
        }
    }

    private Node head, tail;
    private HashMap<Integer, Node> map;
    private int cap;

    public LRUCache(int capacity) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.right = tail;
        tail.left  = head;
        map  = new HashMap<Integer, Node>();
        this.cap = capacity;
    }

    public void remove(Node p){
        p.right.left = p.left;
        p.left.right = p.right;
    }

    public void insert(Node p){
        p.right = head.right;
        head.right.left = p;
        p.left = head;
        head.right = p;
    }

    public int get(int key) {
        if (!map.containsKey(key)){
            return -1;
        }
        Node p = map.get(key);
        remove(p);
        insert(p);
        return p.val;
    }

    public void put(int key, int value) {
        if (!map.containsKey(key)){
            if (cap == map.size()){
                Node p = tail.left;
                remove(p);
                map.remove(p.key);
            }
            Node p = new Node(key, value);
            insert(p);
            map.put(key, p);
        } else{
            Node p = map.get(key);
            p.val = value;
            remove(p);
            insert(p);
        }
    }
}

Enjoy it !