力扣146题：LRU缓存_lru 力扣

力扣146题：LRU缓存

题目描述

请你设计并实现一个满足 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) 的平均时间复杂度运行。

输入输出样例

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

解法一，自定义双链表

//自定义双链表
struct DLinkedNode{
    //存放键值
    int key;
    int value;

    //定义头指针和尾指针
    DLinkedNode *prev;
    DLinkedNode *next;

    //定义初始化函数 
    DLinkedNode():key(0),value(0),prev(nullptr),next(nullptr){}
    DLinkedNode(int keys,int values):key(keys),value(values),prev(nullptr),next(nullptr){}

};


class LRUCache{

    //public 存函数
    //private 存放变量
private:
    //建立hash表，表中存放 键key 和结点 ，通过对键的查找可以查找到对应的结点
    unordered_map<int,DLinkedNode*>cache;
    //定义头节点和尾结点
    DLinkedNode *head;
    DLinkedNode *tail;
    int size;
    int capacity;

public:

//一旦需要 key 和 value 肯定是 hash表

//要求：1.需要能随机访问 2.能够把数据插入头部或尾部

//使用hash表跟双向链表维护所有在缓冲中的键值对
//双向链表，按照顺序存储键值对，头部是最近使用，尾部是最久未使用
//哈希表，缓存数据键映射到链表中的位置
//构造函数
//初始化变量
    LRUCache(int capa)
    {
        capacity=capa;
        size=0;
        //构建双链表结点的头指针和尾指针的指向关系
        head=new DLinkedNode();
        tail=new DLinkedNode();

        head->next=tail;
        tail->prev=head;
    }

//显示数据
//首先判断数据是否存在，通过hash查找结点在双向链表中的位置，并移动到链表头部
    int get(int key)
    {
        //如果键key在hash表中不存在则返回-1
        if(!cache.count(key))
        {
            // cout<<-1<<endl;
            return -1;
        }
        //若键key存在，则通过hash表进行定位，并将其移动到hash表的头部
        DLinkedNode *node=cache[key];

        //将结点移动到头节点
        moveToHead(node);
        // cout<<node->value<<endl;
        return node->value;

    }

//添加函数
//首先判断数据是否存在，若不存在，则新建一个结点，添加到双向链表中和哈希表中，并移动到首部  
//                     若存在，则先根据hash表进行定位，再将值更新为value，移动到链表的头部
    void put(int key,int value)
    {
        //如果hash表的key不存在，则创建一个新的结点
        if(!cache.count(key))
        {
            DLinkedNode *node=new DLinkedNode(key,value);
            //将其值添加到hash表
            cache[key]=node;
            //并将结点添加到双向链表的头部
            addToHead(node);
            ++size;
            //如果hash表中数据的大小大于容量，则删除双向链表的最末尾的结点
            if(size>capacity)
            {   
                DLinkedNode *removed=removeTail();
                //删除待删除的结点在hash表中对应的项
                cache.erase(removed->key);
                //删除结点 避免内存泄漏
                delete removed;
                --size;
            }

        }

        //如果key在hash表中存在，首先通过hash表的定位，再修改value，并且移动到头部
        else{
            DLinkedNode*node=cache[key];
            node->value=value;
            moveToHead(node);
        }

    }



//将结点从当前位置挪出去
    void removeNode(DLinkedNode *node)
    {
        node->prev->next=node->next;
        node->next->prev=node->prev;
    }

    void addToHead(DLinkedNode *node)
    {
        node->prev=head;
        node->next=head->next;

        head->next->prev=node;
        head->next=node;
    }

//删除双向链表的尾结点
    DLinkedNode * removeTail()
    {
        DLinkedNode *node=tail->prev;
        removeNode(node);
        return node;
    }

//首先需要将当前结点从当前位置移除出去
//在将当前结点添加到链表的头部
    void moveToHead(DLinkedNode *node)
    {
        removeNode(node);
        addToHead(node);
    }


};


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
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148

解法二：使用链表的迭代器

//使用简便版本的LRUCache

class LRUCache2
{
    private:
        int capacity;
        list<pair<int,int>>cache;
        //定义hash表存储键和链表
        unordered_map<int,list<pair<int,int>>::iterator>map;

    public:
        LRUCache2(int cap)
        {
            capacity=cap;
        }

        int get(int key)
        {
            if(!map.count(key))
            {
                cout<<-1<<endl;
                return -1;
            }

            //key指向的结点
            auto key_value=*map[key];
            //找到指定的结点，删除当前结点，并将结点插入到链表的头部
            cache.erase(map[key]);
            cache.push_front(key_value);

            map[key]=cache.begin();
            //返回当前结点的值

            cout<<key_value.second<<endl;
            return key_value.second;
        }

        void put(int key,int value)
        {
            //如果hash表中不包含key 
            if(!map.count(key))
            {
                //hash中的长度刚好等于capacity长度
                //将最久的删除
                if(cache.size()==capacity)
                {
                    map.erase(cache.back().first);
                    cache.pop_back();
                }
            }
            //如果存在则将当前的结点先删除
            else{
                cache.erase(map[key]);
            }
            //插入头节点
            cache.push_front({key,value});
            map[key]=cache.begin();

        }
};

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