首页 > 代码库 > 146. LRU Cache

146. LRU Cache

2024-08-17 19:39:44   220人阅读

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.

 

难一点的设计的题一般就是double list ＋ hashmap<key, node>［LRU ， mid stack］  or tree ＋ hashmap <key, node> ［relation tree or tire］

 

//new node in the tail, old node in the head;
class DoubleList{
    int key;
    int val;
    DoubleList prev;
    DoubleList next;
    public DoubleList(int key, int val){
        this.key = key;
        this.val = val;
    }
}
public class LRUCache {
    int index = 0;
    int capacity;
    DoubleList tail;
    DoubleList head;
    HashMap<Integer, DoubleList> map;
    public LRUCache(int capacity) {
       this.capacity = capacity;
       this.map = new  HashMap<Integer, DoubleList>();
       this.head = new DoubleList(0,0);
       this.tail = new DoubleList(0,0);
       head.next = tail;
       tail.prev = head;
       this.index = 0;
    }
    
    public void addFirst(DoubleList node){
      node.next= head.next;
      node.next.prev = node;
      node.prev = head;
      head.next = node;
    }
    
    public void remove(DoubleList node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
    
    public int get(int key) {
      if(map.containsKey(key)){
         DoubleList node = map.get(key);
         remove(node);
         addFirst(node);
         return node.val;
      }
      return -1;
    }
    
    public void set(int key, int value) {
        if(map.containsKey(key)){
            map.get(key).val = value;
            DoubleList node = map.get(key);
            remove(node);
            addFirst(node);
            return;
        }
        else{
            DoubleList node =  new DoubleList(key, value);
            map.put(key, node);
            if(index < capacity){
                index ++;
                addFirst(node);
            }
            else{
                map.remove(tail.prev.key);
                remove(tail.prev);
                addFirst(node);
            }
        }
    }
   
    
}

 

146. LRU Cache


联系
我们