LRU Cache, Leetcode 解题笔记

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.

第一次出现这种设计题,还是很有意思的,问题的关键是想清楚该用什么数据结构,目前最流行的解法是利用一个HashMap和一个双向链表的结合体。HashMap用来O(1)速度的查找和更新,双向链表则用来维护最近使用节点的队列,这里使用双向链表而不是单向链表的原因是双向链表可以用O(1)的速度删除链表中的节点,而单向链表只能达到O(n)的速度。



public class LRUCache {
    
    HashMap<Integer, DoubleLinkedListNode> map = new HashMap<Integer, DoubleLinkedListNode>();
    DoubleLinkedListNode recent;
    DoubleLinkedListNode early;
    int capacity;
    int size;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        size = 0;
    }
    
    public int get(int key) {
        if(map.containsKey(key)){
            DoubleLinkedListNode n = map.get(key);
            removeNode(n);
            setHead(n);
            return n.val;
        }
        else{
            return -1;
        }
    }
    
    public void set(int key, int value) {
        if(map.containsKey(key)){
            DoubleLinkedListNode n = map.get(key);
            n.val = value;
            removeNode(n);
            setHead(n);
        }
        else{
            DoubleLinkedListNode n = new DoubleLinkedListNode(key, value);
            if(size < capacity){
                setHead(n);
                size++;
            }
            else{
                map.remove(early.key);
                removeNode(early);
                setHead(n);
            }
            map.put(key, n);
        }
    }
    
    public void removeNode(DoubleLinkedListNode n){
        DoubleLinkedListNode cur = n;
        DoubleLinkedListNode pre = n.pre;
        DoubleLinkedListNode post = n.next;
        if(pre != null){
            pre.next = post;
        }
        else{
            recent = post;
        }
        if(post != null){
            post.pre = pre;
        }
        else{
            early = pre;
        }
    }
    
    public void setHead(DoubleLinkedListNode head){
        head.next = recent;
        head.pre = null;
        if(recent != null){
            recent.pre = head;
        }
        recent = head;
        if(early == null){
            early = head;
        }
    }
}

class DoubleLinkedListNode {
    int val;
    int key;
    DoubleLinkedListNode pre;
    DoubleLinkedListNode next;
    public DoubleLinkedListNode(int key, int val){
        this.val = val;
        this.key = key;
        pre = null;
        next = null;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s