Leetcode: LRU Cache 理解分析

时间:2023-01-26 04:51:31

题目大意:设计一个数据结构实现LRU(Least Recently Used)缓存机制,必须实现以下两个操作:get和set

get(key) -- 如果key存在,返回key所对应的value(为正数);否则返回-1;

set(key, value) -- key不存在时,设置或插入这个(key, value)对,当cache的容量已满时,插入前应该移除least recently used元素。

理解:1)题目要求设计并实现一个cache,使用LRU调度机制来进行存储管理。LRU调度是指当存储满时,选择最近最少使用的元素移除缓存,我们知道LRU调度最新调用或使用的对象都会放在第一个,随着时间的推移,当存储满时,排在最后个那个元素就是最长时间没有被再次使用的,就是该被移除的那个。

2)设计的数据结构要满足插入、删除和移动很容易,所有很容易想到用链表,为满足插入首节点和删除最后一个元素很简单,我们同时为链表增加首节点(head)和尾节点(tail),并使用双向链表。只需要实现对链表的三种操作:插入首节点,移除尾节点和将某个给定节点移到首位(表示最新使用)。

实现:

public class LRUCache {
    private int capacity;
    
    class node { // 节点类型
        int key;
        int val;
        node next;
        node pre;
        private node(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
            this.pre = null;
        }
    }
    
    private class cacheList { // 内部类 实现对双向链表的插入、删除和移动的操作
        private node head, tail; // 增加首尾节点,方便插入首节点和删除尾节点
        private cacheList() {
            head = new node(0, 0);
            tail = new node(0, 0);
            head.next = tail;
            tail.pre = head;
        }
        
        private void insertFirst(node p) { // 插入到第一个节点位置
            p.next = head.next;
            head.next.pre = p;
            p.pre = head;
            head.next = p;
        }
        
        private node removeLast() { // 删除最后一个节点,并返回被删除的节点
            node last = tail.pre;
            last.next.pre = last.pre;
            last.pre.next = last.next;
            
            return last;
        }
        
        private void removeToFirst(node p) { // 将特定节点移动到第一个节点位置
            p.pre.next = p.next;
            p.next.pre = p.pre;
            this.insertFirst(p);
        }
    }
    
    private cacheList cachelist;
    public HashMap<Integer, node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        cachelist = new cacheList();
        map = new HashMap<Integer, node>();
    }
    
    public int get(int key) { // 查找某个key对应的value,若不存在则返回-1
        node res = map.get(key);
        if(res != null) {
            cachelist.removeToFirst(res);
            return res.val;
        }
        return -1;
    }
    
    public void set(int key, int value) { // 插入一(key, value)对
        if(map.containsKey(key)) { // 若该key已存在,则更新其对应的value,并移动到第一个节点位置
            node res = map.get(key);
            res.val = value;
            map.put(key, res);
            cachelist.removeToFirst(res);
        }
        else { // 不存在,则将(key, value)对插入到第一个节点位置
            if(map.size() == capacity) { // 若cache容量已满,则移除LRU节点,即链表的最后一个节点
                node last = cachelist.removeLast();
                map.remove(last.key);
            }
            node q = new node(key, value);
            cachelist.insertFirst(q);
            map.put(key, q);
        }
    }
}