LeetCode 面试题 16.25. LRU 缓存

一、题目

  设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。

  它应该支持以下操作： 获取数据 get 和 写入数据 put。

  获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
  写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

  点击此处跳转题目。

二、C# 题解

  LRU 的思想就是将不常使用的元素优先级设置最低。因此算法规则如下：

1. 新数据插入到链表头部；
2. 当缓存命中（即缓存数据被访问），数据要移到表头；
3. 当链表满的时候，将链表尾部的数据丢弃。

  这里使用数组存储链表结构，因为简单高效。

public class LRUCache {
    private struct Node
    {
        public int Key, Value, Left, Right;
    }

    private int    _cap, _size;
    private Node[] _list; // 带头结点的双向链表数组实现，_list[0] 作为头结点

    private int FirstPos { // 第一个结点的物理位置存储在 _list[0].Right 中
        get => _list[0].Right;
        set => _list[0].Right = value;
    }

    private int RearPos { // 尾结点的物理位置存储在 _list[0].Left 中
        get => _list[0].Left;
        set => _list[0].Left = value;
    }

    private Dictionary<int, int> _dic;

    public LRUCache(int capacity) {
        _cap = capacity;
        _size = 0;
        _list = new Node[_cap + 1];        // _list[0] 用作 head 结点，存储 first 和 rear 位置
        _dic = new Dictionary<int, int>(); // 记录 key 所在结点的位置 pos
    }

    public int Get(int key) {
        // Cache 中存在 key，则将其移到表头，并返回对应的 value
        if (_dic.TryGetValue(key, out int pos)) {
            MoveToFirst(pos);
            return _list[pos].Value;
        }

        // 不存在，返回 -1
        return -1;
    }

    public void Put(int key, int value) {
        // Cache 中存在 key，则将其移到表头，并更新 value
        if (_dic.TryGetValue(key, out int pos)) {
            MoveToFirst(pos);
            _list[pos].Value = value;
        }
        // 不存在 key
        else {
            // 链表未满，则直接插入新结点
            if (_size < _cap) {
                AddNode(key, value, ++_size); // 新结点的物理位置在数组的下一个位置
                _dic.Add(key, _size);         // 添加 key 的记录
            }
            // 链表已满，需要移除尾结点，将新结点插入表头
            else {
                int rear = RearPos; // 记录此时的尾结点位置
                ReMoveAt(rear);     // 移除尾结点
                _dic.Remove(_list[rear].Key);
                AddNode(key, value, rear); // 向表头插入新结点，物理位置就存储在刚删掉的尾结点 rear 处
                _dic.Add(key, rear);
            }
        }
    }

    // 向表头插入结点，结点存储在 _list[pos] 的位置中
    private void AddNode(int key, int value, int pos) {
        // 创建结点
        _list[pos].Key = key;
        _list[pos].Value = value;

        // 插入表头
        _list[pos].Left = 0;
        _list[pos].Right = FirstPos;
        _list[FirstPos].Left = pos;
        FirstPos = pos;
    }

    // 将 pos 位置处的结点移到表头
    private void MoveToFirst(int pos) {
        ReMoveAt(pos);                                  // 将该结点从链表中移出
        AddNode(_list[pos].Key, _list[pos].Value, pos); // 再插入表头
    }

    // 将 _list[pos] 处的结点从链表中移除
    private void ReMoveAt(int pos) {
        int leftPos  = _list[pos].Left;
        int rightPos = _list[pos].Right;
        _list[leftPos].Right = rightPos;
        _list[rightPos].Left = leftPos;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.Get(key);
 * obj.Put(key,value);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

• 时间：176 ms，击败 100.00% 使用 C# 的用户
• 内存：64.35 MB，击败 85.71% 使用 C# 的用户