[leetcode/lintcode 题解] LRU 缓存策略 · LRU Cache

[题目描述]

为最近最少使用（ LRU ）缓存策略设计一个数据结构，它应该支持以下操作：获取数据和写入数据。

• get(key) 获取数据：如果缓存中存在 key，则获取其数据值（通常是正数），否则返回-1 。

• set(key, value) 写入数据：如果 key 还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。

最终, 你需要返回每次 get 的数据.

在线评测地址: https://www.lintcode.com/problem/lru-cache/?utm_source=sc-v2ex-fks0525

[样例] 样例 1:

输入：
LRUCache(2)
set(2, 1)
set(1, 1)
get(2)
set(4, 1)
get(1)
get(2)
输出：[1,-1,1]
解释：
cache 上限为 2，set(2,1)，set(1, 1)，get(2) 然后返回 1，set(4,1) 然后 delete (1,1)，因为 （ 1,1 ）最少使用，get(1) 然后返回 -1，get(2) 然后返回 1 。

样例 2:

输入：
LRUCache(1)
set(2, 1)
get(2)
set(3, 2)
get(2)
get(3)
输出：[1,-1,2]
解释：
cache 上限为 1，set(2,1)，get(2) 然后返回 1，set(3,2) 然后 delete (2,1)，get(2) 然后返回 -1，get(3) 然后返回 2 。

[题解] Singly Linked List 的版本

public class LRUCache {
    class ListNode {
        public int key, val;
        public ListNode next;
        
        public ListNode(int key, int val) {
            this.key = key;
            this.val = val;
            this.next = null;
        }
    }
    
    private int capacity, size;
    private ListNode dummy, tail;
    private Map<Integer, ListNode> keyToPrev;

    /*
    * @param capacity: An integer
    */
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.keyToPrev = new HashMap<Integer, ListNode>();
        this.dummy = new ListNode(0, 0);
        this.tail = this.dummy;
    }

    private void moveToTail(int key) {
        ListNode prev = keyToPrev.get(key);
        ListNode curt = prev.next;
        
        if (tail == curt) {
            return;
        }
        
        prev.next = prev.next.next;
        tail.next = curt;
        
        if (prev.next != null) {
            keyToPrev.put(prev.next.key, prev);
        }
        keyToPrev.put(curt.key, tail);
        
        tail = curt;
    }
    
    /*
     * @param key: An integer
     * @return: An integer
     */
    public int get(int key) {
        if (!keyToPrev.containsKey(key)) {
            return -1;
        }
        
        moveToTail(key);
        
        // the key has been moved to the end
        return tail.val;
    }
    
    /*
     * @param key: An integer
     * @param value: An integer
     * @return: nothing
     */
    public void set(int key, int value) {
        // get method will move the key to the end of the linked list
        if (get(key) != -1) {
            ListNode prev = keyToPrev.get(key);
            prev.next.val = value;
            return;
        }
        
        if (size < capacity) {
            size++;
            ListNode curt = new ListNode(key, value);
            tail.next = curt;
            keyToPrev.put(key, tail);
            
            tail = curt;
            return;
        }
        
        // replace the first node with new key, value
        ListNode first = dummy.next;
        keyToPrev.remove(first.key);
        
        first.key = key;
        first.val = value;
        keyToPrev.put(key, dummy);
        
        moveToTail(key);
    }
}

《九章算法班 2020 版》

课程适配 C++/Java/Python 等主流编程语言，30 天精通 57 个核心高频考点，9 招击破 FLAG 、BATJ 算法面试。

内容亮点：

• 课程覆盖 90%国内外一线大厂算法面试高频考点

• 2020 夏秋招最新大厂面试算法题 80+实战讲解

• 规范编程细节，实质性提升 Coding 能力避免面试“隐形坑”

• 课程体系完美匹配大厂面试考点，算法面试从容应对

戳我立即免费报名