2023-09-24力扣每日一题

链接：

146. LRU 缓存

题意

模拟LRU算法，没啥好说的

解：

有点忙，超了个双向链表来用

一共会有三种操作：两端的删除和插入，中间的删除

简单来说就是双向链表方便删除（更新的时候）和一端插入（更新/新的访问 的时候）一端删除（新的访问的时候）

所以只需要能够快捷找到链表中的节点就行，通过一个map来做即可

实际代码：

#include
using namespace std;
struct Node
{
	int key;
    int value;
    Node* pre;
    Node* next;
    
    Node(int key, int val):key(key),value(val),pre(nullptr),next(nullptr)
	{
		//Empty
	}
	
	void removeNode()
	{
        this->pre->next=this->next;
        this->next->pre=this->pre;
    }
};
class LRUCache {
public:
	unordered_maphmap;
	
	Node* head;
    Node* tail;
	int capacity=0;
	int size=0;
	
    LRUCache(int capacity)
	{
		this->capacity=capacity;

        this->head=new Node(-1,-1);
        this->tail=new Node(-1,-1);
        head->next=tail;
        tail->pre=head;
    }
    
    int get(int key)
	{
		if(!hmap.count(key)) return -1;
        else
		{
			hmap[key]->removeNode();
			addToHead(hmap[key]);
		}
        return hmap[key]->value;
    }
    
    void put(int key, int value)
	{
		if(hmap.count(key))
		{
        	Node* node=hmap[key];
        	node->value=value;
        	hmap[key]->removeNode();
			addToHead(hmap[key]);
        }
		else
		{
            Node* node=new Node(key, value);
            hmap[key]=node;
            addToHead(node);
            size++;
            if (size>capacity)
			{
                node=removeTail();
                hmap.erase(node->key);
                size--;
            }
        }
    }
    
protected:
	
	void addToHead(Node* node)
	{
        node->next=head->next;
        node->pre=head;
        head->next=node;
        node->next->pre=node;
    }

 	Node* removeTail()
	{
        Node* node=tail->pre;
        node->removeNode();
        return 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

限制：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 105
• 最多调用 2 * 105 次 get 和 put