146. LRU Cache

Link

Solution

這題要透過double link node來紀錄每個key的使用頻率

形式會像這樣 head<-> ..... <->tail，其中越接近tail的表示最近越少使用，然後每次put ，或get，都會把node移到head之後。

如此就能追蹤哪個node是在滿容量時要刪除的，這個node就是tail的前一個node。

要實作幾個functions 1. removeNode(node) //刪除node 2. moveToFront(node) //將現存node刪除，並重新加到head之後 3. addNode(node) // 確保都放到head之後

   class DlinkNode{
        public int value;
        public int key;
        public DlinkNode pre;
        public DlinkNode next;
    }
    public void addNode(DlinkNode node){
        node.next = head.next;
        head.next.pre = node;
        node.pre = head;
        head.next = node;
    }
    
    
    public void removeNode(DlinkNode node){
        node.pre.next = node.next;
        node.next.pre = node.pre;
        node.pre = null;
        node.next = null;
    }
    
    public void moveToFront(DlinkNode node){
        removeNode(node); 
        addNode(node);
    }
    
    public DlinkNode head, tail;
    public HashMap<Integer, DlinkNode> map;
    public int capacity, count = 0;
    
    public LRUCache(int capacity) {
        map = new HashMap<>();
        this.capacity = capacity;
        
        head = new DlinkNode();
        tail = new DlinkNode();
        head.next = tail;
        tail.pre = head;
    }
    
    public int get(int key) {
        DlinkNode node = map.get(key);
        if(node == null){
            return -1;
        }
        
        moveToFront(node);
        return node.value;
    }
    
    public void put(int key, int value) {
        
        DlinkNode node = map.get(key);
        if(node == null){
            node = new DlinkNode();
            node.value = value;
            node.key = key;
            addNode(node);
            map.put(key, node);
            count++;
            if(count > capacity){
                DlinkNode remove = tail.pre;
                if(remove != head){
                    map.remove(remove.key);
                    removeNode(remove);
                }
                count--;
            }
        }
        else{
            //update
            node.value = value;
            //to The top
            moveToFront(node);
        }
    }