leetcode--LRU Cache

时间：2014-03-03 17:53:03 阅读：386 评论：0 收藏：0 [点我收藏+]

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.

Have you been asked this question in an interview?

The main point of this problem is to guarantee each operation cost O(1) time, This is the main requirement of cache.

Since we need to remove a record from the cache and keep all records in order, this invloves searching, deletion and insertion. The best data structure to do this is the

one which is a combination of HashMap and doubly-linked list. So, I use a HashMap<Integer, Node>, where Node is class defined by myself.

public class LRUCache {
   public 
LRUCache(int 
capacity) {
        lruMap = new 
HashMap<Integer, Node>();
        this.capacity = capacity;
        sz = 0;     
    }
     
    public 
int get(int key) {
        int 
result = -1;
        if(lruMap.containsKey(key)){
            moveToHead(lruMap.get(key));
            lruMap.put(key, first);
            result = first.value;
        }
        return 
result;
    }
     
    public 
void set(int key, int 
value) {
        if(lruMap.containsKey(key)){
            Node temp = lruMap.get(key);
            temp.value = (temp.value == value )? temp.value : value;
            moveToHead(temp);
            lruMap.put(key, first);
        }
        else 
if(sz < capacity){
            Node node = new 
Node();
            node.key = key;
            node.value = value;
            if(sz == 0){
                first = node;
                last = node;
            }
            else{
                first.prev = node;
                node.next = first;
                first = node;
            }
            lruMap.put(key, node);
            ++sz;
        } 
        else{
            Node node = new 
Node();
            node.key = key;
            node.value = value;
            int 
lastKey = last.key;
            if(sz == 1){
                last = null;
                first = null;
                first = node;
                last = node;
                 
            }
            else{
                last = last.prev;
                last.next = null;
                first.prev = node;
                node.next = first;
                first = node;               
            }
            lruMap.remove(lastKey);
            lruMap.put(key, node);          
        }
    }
     
    public  
void moveToHead(Node node){
        if( node.prev == null)   //the node is already the head. Do nothing
            return;
        else{
            node.prev.next = node.next;
            if(node.next != null)
                node.next.prev = node.prev;
            else
                last = node.prev;
            first.prev = node;
            node.prev = null;
            node.next = first;
            first = node;            
        }
    }
     
    private 
HashMap<Integer, Node> lruMap;
    private 
int capacity;
    private 
Node first;
    private 
Node last;
    private 
int 
      sz;
}
 
class 
Node{
    int 
key; //we need use it to remove a node in the HashMap;
    int 
value;
    Node prev;
    Node next;
    //using the default constructor is enough
}

leetcode--LRU Cache,布布扣,bubuko.com

leetcode--LRU Cache

原文：http://www.cnblogs.com/averillzheng/p/3577651.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)