146. LRU Cache 数据结构神题

146. LRU Cache 数据结构神题

题意

实现一个LRU Cache

思路

hash table + 双向链表
链表头存着最近的节点，链表尾存着最近最少使用的节点

代码

这版应该是写的最简洁的一版了，就是有很多条件需要考虑清楚
这题应该多练几遍，面试时30分钟能写出

class LRUCache {
    class ListNode {
        int key, value;
        ListNode prev, next;
        public ListNode (int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }
    
    int capacity;
    ListNode head, tail;
    Map<Integer, ListNode> map;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.map = new HashMap<>();
        this.head = null;
        this.tail = null;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        ListNode node = map.get(key);
        this.deleteNode(node);   //因为get操作也相当于使用了一次，所以应该把原来的删除，再加入到链表头！
        this.addToHead(node);
        return node.value;
    } 
    //要考虑是否是头尾节点 
    private void deleteNode(ListNode node) {
        if (node == head) {
            head = node.next;
        } else {
            node.prev.next = node.next;
        }
        if (node == tail) {
            tail = node.prev;
        } else {
            node.next.prev = node.prev;
        }
    }
    
    private void addToHead(ListNode node) {
        node.next = head;
        node.prev = null;
        if (head != null) head.prev = node;
        head = node;
        if (tail == null) tail = head;
    } 
    
    //put操作要先考虑原来有没有这个key
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            node.value = value;
            this.deleteNode(node);
            this.addToHead(node);
        } else {
            ListNode newNode = new ListNode(key, value);
            if (map.size() == this.capacity) {  //直接map.size就是当前的size
                map.remove(tail.key);
                deleteNode(tail);
            }
            addToHead(newNode);
            map.put(key, newNode);
        }
    }
}