I don't understand, I use Double Linked List, also get TLE...........TAT.....Please Help me!


  • 1
    B
    class DoubleLinkedListNode<T>{
        public T val;
        public DoubleLinkedListNode(T t){val=t;}
        public DoubleLinkedListNode pre = null;
        public DoubleLinkedListNode next = null;
        public boolean eqauls(DoubleLinkedListNode node){
            return val==node.val && pre == node.pre && next==node.next;
        }
    }
    class DoubleLinkedList<T>{
        public DoubleLinkedListNode head;
        public DoubleLinkedListNode tail;
        HashMap<T, DoubleLinkedListNode> map = new HashMap<>();
        private int size;
        public DoubleLinkedList(){}
        public void add(T t){
            size++;
            if(head==null) {
                head = new DoubleLinkedListNode(t);
                tail = head;
            }
            else{
                tail.next = new DoubleLinkedListNode(t);
                DoubleLinkedListNode tmp = tail;
                tail = tail.next;
                tail.pre = tmp;
            }
            map.put(t,tail);
        }
        public void remove(T t){
            DoubleLinkedListNode node = map.get(t);
            if(node.pre == null)
                head = head.next;
            else{
                node.pre.next = node.next;
                if(node.next!=null)
                    node.next.pre = node.pre;
                else
                    tail = node.pre;
            }
            map.remove(t);
            size--;
        }
        public T remove(){
            T t = (T)head.val;
            if(size==1)
                tail = null;
            head = head.next;
            map.remove(t);
            size--;
            return t;
        }
        public int size(){return size;}
        public boolean contains(T t){return map.containsKey(t);}
    }
    int capacity_=0;
    HashMap<Integer,Integer> waitlist = new HashMap<>();
    HashMap<Integer,Integer> map = new HashMap<>();
    DoubleLinkedList<Integer> used = new DoubleLinkedList<>();
    LinkedList<Integer> waitqueue = new LinkedList<>();
    public LRUCache(int capacity) {
        capacity_ = capacity;
    }
    public int get(int key) {
        if(map.containsKey(key)){
            int val = map.get(key);
            if(used.contains(new Integer(key)))
                used.remove(new Integer(key));   
            used.add(new Integer(key));
            return val;
        }
        return -1;
    }
    public void set(int key, int value) {
        if(!map.containsKey(key)&&!waitlist.containsKey(key)){
            //add if has space
            if(map.size() < capacity_){
                map.put(key,value);
            }
            //map do not have space
            else{
                if(used.size()>0){
                    //remove least recently used item(FILO)
                    int k = used.remove().intValue();
                    map.remove(k);
                    if(waitlist.size()>0){
                        //remove first in list
                        int kt = waitqueue.remove();
                        map.put(kt,waitlist.get(kt));
                        waitlist.remove(kt);
                        waitlist.put(key,value);
                        waitqueue.add(key);
                    }
                    else
                        map.put(key,value);
                }
                else{
                waitlist.put(key,value);
                waitqueue.add(key);
                }
            }
        }
        else if(map.containsKey(key)){
                used.remove(new Integer(key));     
            map.put(key,value);
        }
        else{
            used.remove(new Integer(key));   
            waitlist.put(key,value);
        }
        used.add(new Integer(key));
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.