Join UsSite Message
Only Premium Users can view the Question
Entering edit mode
#include <bits/stdc++.h>
using namespace std;
class LRUCache {
public:
class node {
public:
int key;
string value;
node * prev;
node * next;
node(int _key, string _value) {
key = _key;
value = _value;
}
};
node* head = new node(-1,"-1");
node* tail = new node(-1,"-1");
int cap;
map<int, node *> m;
LRUCache(int capacity) {
cap = capacity;
head->next = tail;
tail->prev = head;
}
void addnode(node * temp) {
node * dummy = head->next;
head->next = temp;
temp->prev = head;
temp->next = dummy;
dummy->prev = temp;
}
void deletenode(node * temp) {
node * delnext = temp->next;
node * delprev = temp->prev;
delnext->prev = delprev;
delprev->next = delnext;
}
string get(int key) {
if (m.find(key) != m.end()) {
node * res = m[key];
m.erase(key);
string ans = res->value;
deletenode(res);
addnode(res);
m[key] = head->next;
return ans;
}
return "-1";
}
void set(int key, string value) {
if (m.find(key) != m.end()) {
node * exist = m[key];
m.erase(key);
deletenode(exist);
}
if (m.size() == cap) {
m.erase(tail->prev->key);
deletenode(tail->prev);
}
addnode(new node(key, value));
m[key] = head->next;
}
};
bool code(vector<string> res, int mid, int k) {
LRUCache* cache = new LRUCache(mid);
int count = 0;
int c = 0;
int n = res.size();
map<string,int> m;
for(int t = 0; t < n; t++) {
if(m.find(res[t]) == m.end()) {
c++;
m[res[t]] = c;
cache->set(c, res[t]);
} else {
if(cache->get(m[res[t]]) == "-1") {
cache->set(m[res[t]], res[t]);
} else {
count++;
}
}
}
return count >= k;
}
int solve(vector<string> res, int k) {
int s = 1;
int n = res.size();
int e = n;
while(s <= e) {
int mid = s + (e - s) / 2;
if(code(res, mid, k)) {
e = mid - 1;
} else {
s = mid + 1;
}
}
return (s == n + 1) ? -1 : s;
}
Entering edit mode
#include <bits/stdc++.h>
using namespace std;
class LRUCache {
public:
class node {
public:
int key;
string value;
node * prev;
node * next;
node(int _key, string _value) {
key = _key;
value = _value;
}
};
node* head = new node(-1,"-1");
node* tail = new node(-1,"-1");
int cap;
map<int, node *> m;
LRUCache(int capacity) {
cap = capacity;
head->next = tail;
tail->prev = head;
}
void addnode(node * temp) {
node * dummy = head->next;
head->next = temp;
temp->prev = head;
temp->next = dummy;
dummy->prev = temp;
}
void deletenode(node * temp) {
node * delnext = temp->next;
node * delprev = temp->prev;
delnext->prev = delprev;
delprev->next = delnext;
}
string get(int key) {
if (m.find(key) != m.end()) {
node * res = m[key];
m.erase(key);
string ans = res->value;
deletenode(res);
addnode(res);
m[key] = head->next;
return ans;
}
return "-1";
}
void set(int key, string value) {
if (m.find(key) != m.end()) {
node * exist = m[key];
m.erase(key);
deletenode(exist);
}
if (m.size() == cap) {
m.erase(tail->prev->key);
deletenode(tail->prev);
}
addnode(new node(key, value));
m[key] = head->next;
}
};
bool code(vector<string> res, int mid, int k) {
LRUCache* cache = new LRUCache(mid);
int count = 0;
int c = 0;
int n = res.size();
map<string,int> m;
for(int t = 0; t < n; t++) {
if(m.find(res[t]) == m.end()) {
c++;
m[res[t]] = c;
cache->set(c, res[t]);
} else {
if(cache->get(m[res[t]]) == "-1") {
cache->set(m[res[t]], res[t]);
} else {
count++;
}
}
}
return count >= k;
}
int solve(vector<string> res, int k) {
int s = 1;
int n = res.size();
int e = n;
while(s <= e) {
int mid = s + (e - s) / 2;
if(code(res, mid, k)) {
e = mid - 1;
} else {
s = mid + 1;
}
}
return (s == n + 1) ? -1 : s;
}
Loading Similar Posts
