146. LRU Cache #

题目 #

设计并实现一个满足 LRU（最近最少使用）缓存 约束的数据结构。

实现 LRUCache 类：

LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value；如果不存在，则向缓存中插入该组 key-value，如果插入操作导致关键字数量超过 capacity，则应该逐出最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

思路 #

使用 双向链表 结合 哈希表 实现 LRU Cache 数据结构。

代码 #

class LRUCache {
    private class ListNode {
        int key;
        int val;
        public ListNode prev;
        public ListNode next;
        
        ListNode (int key, int val, ListNode prev, ListNode next) {
            this.key = key;
            this.val = val;
            this.prev = prev;
            this.next = next;
        }
    }
    
    int size;
    int capacity;
    HashMap<Integer, ListNode> map;
    ListNode sentinel;
    
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.map = new HashMap<Integer, ListNode>();
        this.sentinel = new ListNode(-1, -1, null, null);
        this.sentinel.next = this.sentinel.prev = this.sentinel;
    }
    
    public int get(int key) {
        if (this.map.containsKey(key) == false) return -1;
        ListNode ptr = this.map.get(key);
        moveToHead(ptr);
        return ptr.val;
    }
    
    public void put(int key, int value) {
        if (this.map.containsKey(key) == false) {
            if (this.size == capacity) removeTail();
            else this.size += 1;
            
            ListNode ptr = new ListNode(key, value, this.sentinel, this.sentinel.next);
            this.sentinel.next = ptr;
            ptr.next.prev = ptr;
            
            this.map.put(key, ptr);
        }
        else {
            ListNode ptr = this.map.get(key);
            ptr.val = value;
            moveToHead(ptr);
        }
    }
    
    public void moveToHead(ListNode ptr) {
        ptr.prev.next = ptr.next;
        ptr.next.prev = ptr.prev;
        
        ptr.next = this.sentinel.next;
        ptr.prev = this.sentinel;
        ptr.next.prev = ptr;
        ptr.prev.next = ptr;
    }
    
    public void removeTail() {
        ListNode tail = this.sentinel.prev;
        this.sentinel.prev = tail.prev;
        this.prev.next = this.sentinel;
        this.map.remove(tail.key); /** Is HashMap.remove() O(1) ? */
    }
}

146. LRU Cache #

题目 #

思路 #

代码 #

致谢 #