146. LRU Cache

https://leetcode.com/problems/lru-cache/description/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. set(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.

Thoughts

实现least-recently-used cache，O(1)查找和添加，并且当cache容量达到限制时把最早没用过的元素踢出去。用双向链表配合hash表，用实体dummy head和tail能够不用检查next和pre是否为null，实现remove和add。O(1)找结点用hash map，每次接触过的节点放到头部，即调用一次remove和add。超出capacity就把tail前的元素移除。

Code

/*
 * @lc app=leetcode id=146 lang=cpp
 *
 * [146] LRU Cache
 */

// @lc code=start
class LRUCache {
public:
    class Node {
    public:
        int key, val;
        Node *pre = nullptr, *next = nullptr;
        Node(int k, int v): key(k), val(v) {} 
    };
    Node *head, *tail;
    unordered_map<int, Node*> m;
    int K;

    LRUCache(int capacity) {
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head->next = tail;
        tail->pre = head;
        K = capacity;
    }

    void rm(Node *node) {
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }

    void add(Node *node) {
        node->next = head->next;
        node->pre = head;
        head->next = node;
        node->next->pre = node;
    }

    void update(Node *node) {
        rm(node);
        add(node);
    }
    
    int get(int key) {
        if (!m.count(key)) return -1;
        auto node = m[key];
        update(node);
        return node->val;        
    }
    
    void put(int key, int value) {
        if (m.count(key)) {
            auto node = m[key];
            node->val = value;
            update(node);
        } else {
            Node *node = new Node(key, value);
            if (m.size() == K) {
                m.erase(tail->pre->key);
                rm(tail->pre);
            }
            add(node);
            m[key] = node;
        }
    }
};

/**
 * 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);
 */
// @lc code=end

class LRUCache {
    private class ListNode {
        int key, val;
        ListNode prior, next;
        ListNode (int key, int val) {
            this.key = key;
            this.val = val;
            prior = null;
            next = null;
        }
    }

    Map<Integer, ListNode> map;
    ListNode head, tail = null;
    int capacity, size;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        head = new ListNode(-1, 0);
        tail = new ListNode(-1, 0);
        head.next = tail;
        tail.prior = head;
        map = new HashMap<>();
    }

    private void rmNode(ListNode node) {
        ListNode pre = node.prior;
        ListNode next = node.next;
        pre.next = next;
        next.prior = pre;
    }

    // Add the new node right after head;
    private void addNode(ListNode node) {
        node.next = head.next;
        node.prior = head;

        node.next.prior = node;
        head.next = node;
    }

    private void mv2Head(ListNode node) {
        this.rmNode(node);
        this.addNode(node);
    }

    private ListNode popTail() {
        ListNode res = tail.prior;
        rmNode(res);
        return res;
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            mv2Head(map.get(key));
            return map.get(key).val;
        } else {
            return -1;
        }
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            ListNode node = map.get(key);
            mv2Head(node);
            node.val = value;
        } else {
            size++;
            ListNode node = new ListNode(key, value);

            if (size > capacity) {
                ListNode realTail = popTail(); 
                map.remove(realTail.key);
                size = capacity;
            }
            map.put(key, node);
            addNode(node);
        }
    }
}

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

Analysis

每次set和get都是O(1).