버클 알고리즘 문제 - 146 LRU 캐 시 메커니즘

[제목]
당신 이 파악 한 데이터 구 조 를 활용 하여 하 나 를 설계 하고 실현 하 세 요.  LRU (최근 최소 사용) 캐 시 메커니즘.데이터 get 을 가 져 오고 데 이 터 를 기록 하 는 put 를 지원 해 야 합 니 다.
데이터 get (key) 가 져 오기 - 키 (key) 가 캐 시 에 존재 하면 키 의 값 (항상 정수) 을 가 져 옵 니 다. 그렇지 않 으 면 - 1 을 되 돌려 줍 니 다.데이터 put (key, value) 를 기록 합 니 다. - 키 가 존재 하지 않 으 면 데이터 값 을 기록 합 니 다.캐 시 용량 이 상한 선 에 이 르 렀 을 때 새 데 이 터 를 쓰기 전에 최근 에 가장 적 게 사용 한 데이터 값 을 삭제 하여 새로운 데이터 값 에 공간 을 남 겨 야 합 니 다.
진급:
당신 은 있 을 수 있 습 니까? O (1) 시간 복잡 도 에서 이 두 가지 조작 을 완성 합 니까?
예시:
LRUCache cache = new LRUCache (2 / * 캐 시 용량 * /);
cache.put(1, 1);cache.put(2, 2);cache.get(1); // 1cache. put (3, 3); /이 동작 은 키 2 를 cache. get (2) 로 폐기 합 니 다. /반환 - 1 (찾 을 수 없 음) cache. put (4, 4); /이 동작 은 키 1 을 cache. get (1) 로 폐기 합 니 다. /반환 - 1 (찾 을 수 없 음) cache. get (3); /3cache. get (4); /돌아오다
[문제 풀이 아이디어!]
블 로그 참조: 좌 신 알고리즘 진급 반 54 변경 가능 한 캐 시 구조 설계 (LRU)
【 코드 】

 1 class LRUCache {
 2 public:
 3     LRUCache(int capacity) {
 4         this->capacity = capacity;
 5     }
 6 
 7     int get(int key) {
 8         if (map.find(key) == map.end())
 9             return -1;
10         Node* p = map[key];
11         update(p);//      
12         return p->val;
13     }
14 
15     void put(int key, int value) {
16         if (map.find(key) == map.end())//      
17         {
18             if (this->map.size() == this->capacity)//      
19             {
20                 Node* p = this->head->next;
21                 this->head->next = p->next;//                
22                 if (p->next == nullptr)//      
23                     end = head;
24                 else
25                     p->next->pre = head;
26                 map.erase(p->key);//     ，                     
27                 delete p;
28             }
29             Node* p = new Node(key, value);//          
30             this->end->next = p;
31             p->pre = end;
32             end = p;
33             map[key] = p;//    
34         }
35         else//  ，          
36         {
37             Node* p = map[key];//         
38             p->val = value;//     
39             update(p);//      
40         }
41     }
42 
43 private:
44     struct Node
45     {
46         int key;
47         int val;
48         Node* pre;
49         Node* next;
50         Node(int k, int v) :key(k), val(v), pre(nullptr), next(nullptr) {}
51     };
52 
53     int capacity = 0;
54     hash_map<int, Node*>map;
55     Node* head = new Node(' ', -1);//      
56     Node* end = head;//      
57     void update(Node* p)
58     {
59         if (p == end)
60             return;//p           
61         Node* q = p->pre;
62         q->next = p->next;
63         p->next->pre = q;
64         end->next = p;
65         p->pre = end;//  p    ，       
66         end = p;
67     }
68 };
69 
70 /**
71  * Your LRUCache object will be instantiated and called as such:
72  * LRUCache* obj = new LRUCache(capacity);
73  * int param_1 = obj->get(key);
74  * obj->put(key,value);
75  */
76 
77 void Test()
78 {
79     LRUCache* rr = new LRUCache(1);
80     rr->put(2, 1);
81     cout << rr->get(2) << endl;
82     rr->put(2, 2);
83     cout << rr->get(2) << endl;
84     rr->get(2);
85     rr->put(3, 2);
86     rr->get(2);
87     rr->get(3);
88     
89 
90 }

 
다음으로 전송:https://www.cnblogs.com/zzw1024/p/11075357.html