Java for LeetCode 146 LRU Cache 【HARD】

浏览数：173 / 时间：2015年06月08日

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.

解题思路：

实现LRU算法的缓冲类，由于cache会有频繁的读改操作，所以要有合适的数据结构来让 set 和 get 的复杂度很小，最好近 O(1)。
主要有两种思路：

一、用 Splay 实现，Splay 是棵 BST，同时在查找和修改的时候会让那个节点上浮到根节点，不过操作都是 O(log(n)) 级别的，而且有个问题，就是这棵树可能会变成一条链（正常节点都是按查询频率从上到下，所以很快，均摊小于 O(log(n))）。Splay 实现过于复杂，这里就不给出。
二、用双链表和 HashMap 实现。

链表的作用是记录节点的使用顺序。正常情况下 LRU 都是用这种做法的。
HashMap 实现用 key 找到 List 中的节点对象，找不到就在 List 中增加节点，并插入 HashMap。
按照要求得到或修改节点的 value。
修改节点的使用时间，也就是把 List 中的节点拉到 List 头部。
在第一步时如果节点个数大于可用容量，就将 List 的最后一个节点删去。
JAVA实现如下：

package oj.leetcode;

import java.util.*;

public class LRUCache {

    private int capacity;
    private Node head, tail;
    private HashMap<Integer, Node> keyNodeMap;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(0, 0);
        head.next = tail;
        tail.pre = head;
        this.keyNodeMap = new HashMap<Integer, Node>();
    }

    public int get(int key) {
        Node node = keyNodeMap.get(key);
        if (node != null) {
            moveToHead(node);
            return node.value;
        }
        return -1;
    }

    public void set(int key, int value) {
        Node node = null;
        if (keyNodeMap.containsKey(key)) {
            node = keyNodeMap.get(key);
            node.value = value;
        } else {
            node = new Node(key, value);
            if (keyNodeMap.size() == capacity) {
                keyNodeMap.remove(removeTail());
            }
            keyNodeMap.put(key, node);
        }
        moveToHead(node);
    }

    private void moveToHead(Node node) {
        if (node.pre != null || node.next != null) {
            node.next.pre = node.pre;
            node.pre.next = node.next;
        }
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }

    private int removeTail() {
        int lastKey = -1;
        if (tail.pre != head) {
            Node lastNode = tail.pre;
            lastKey = lastNode.key;
            lastNode.pre.next = tail;
            tail.pre = lastNode.pre;
            lastNode = null;
        }
        return lastKey;
    }

    class Node{
        int key;
        int value;
        Node pre;
        Node next;
        public Node(int k, int v) {
            key = k;
            value = v;
        }
    }
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

Java for LeetCode 146 LRU Cache 【HARD】