模拟（三）设计LRU缓存结构_嘴大且吃雯

未知 02-07 7160

设计LRU缓存结构_牛客题霸_牛客网

描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能: 1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存 2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。 3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示: 1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。 2.当缓存的大小超过capacity时，移除最不经常使用的记录。 3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察 4.函数set和get必须以O(1)的方式运行 5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

数据范围:

1≤capacity<=1051≤capacity<=105 0≤key,val≤2×109?0≤key,val≤2×109? 1≤n≤1051≤n≤105

struct Node { int key; int value; Node(int a, int y) { key = a; value = y; } }; class Solution { public: Solution(int capacity){ // write code here _capacity = capacity; } int get(int key) { // write code here auto pos = L.begin(); bool falg = false; int _value = 0; for(auto &it : L) { if(it.key == key) { _value = it.value; L.erase(pos); falg = true; L.push_front(Node(key, _value)); break; }else { pos++; } } if(falg) return _value; else return -1; } void set(int key, int value){ // write code here auto pos = L.begin(); bool falg = false; for(auto &it : L) { if(it.key == key) { falg = true; L.erase(pos); L.push_front(Node(key, value)); break; }else { pos++; } } if(!falg) L.push_front(Node(key, value)); if(L.size() > _capacity) L.pop_back(); } list<Node> L; int _capacity; }; /** * Your Solution object will be instantiated and called as such: * Solution* solution = new Solution(capacity); * int output = solution->get(key); * solution->set(key,value); */