Algorithm（一）LRU-cache

2019/04/28 23:15

Leetcode-264

from collections import OrderedDict
class LRUCache(object):

def __init__(self, capacity):
self.capacity = capacity
self.cache = OrderedDict()

def get(self, key):
if key not in self.cache:
return -1

value = self.cache[key]
self.cache.pop(key)
self.cache[key] = value
return value

def put(self, key, value):
if key in self.cache:
self.cache.pop(key)
self.cache[key] = value
else:
if len(self.cache.keys()) == self.capacity:
self.cache.popitem(last=False)

self.cache[key] = value

/************************************************************************/
/* 单链表版本
/************************************************************************/
struct Node {
int        m_nKey;
int        m_nValue;
Node*    m_pNext;
};

class LRUCache {
public:
LRUCache(int capacity) {
m_nSize        = capacity;
m_nCount    = 0;
m_lruList    = NULL;
}

int get(int key) {
if (NULL == m_lruList)
return -1;
map<int, Node *>::iterator it = m_lruMap.find(key);
if (it == m_lruMap.end()) //没有找到
return -1;
else {
Node *p = it->second;
//把节点移到链表的开头
pushFront(p);
}
return m_lruList->m_nValue;
}

void set(int key, int value) {
if (NULL == m_lruList) {
m_lruList = new Node();
m_lruList->m_nKey = key;
m_lruList->m_nValue = value;
m_lruList->m_pNext = NULL;
m_nCount ++;
m_lruMap[key] = m_lruList;
}
else {
map<int, Node *>::iterator it = m_lruMap.find(key);
if (it == m_lruMap.end()){ //没有命中,将链表的最后一个节点删除
if (m_nSize == m_nCount) { //cache已满
}
m_nCount --;
else
pTemp->m_pNext = NULL;
}
Node *p = new Node(); //插入新的节点于头部
p->m_nKey = key;
p->m_nValue = value;
p->m_pNext = m_lruList;
m_lruList = p;
m_lruMap[key] = m_lruList;
m_nCount ++;
}
else { //命中，则将该命中的节点移至链表头部
Node *pCur = it->second;
pCur->m_nValue = value;
pushFront(pCur);
}
}
}

void pushFront(Node *pCur) {  //把节点移动到链表头部，时间复杂度O(n)
if (NULL == pCur)
return;
if (m_nCount == 1 || pCur == m_lruList)
return;
pCur->m_pNext = m_lruList;
m_lruList = pCur;
}

void printCache() {
Node *p = m_lruList;
while (p) {
cout << p->m_nKey << ":" << p->m_nValue << " ";
p = p->m_pNext;
}
}

private:
int                    m_nSize;
int                    m_nCount;
map<int, Node *>    m_lruMap;
Node*                m_lruList;
};

/************************************************************************/
/* 双链表版本
/************************************************************************/
struct Node {
int        m_nKey;
int        m_nValue;
Node*    m_pNext;
Node*   m_pPre;
};

class LRUCache {
public:
LRUCache(int capacity) {
m_nSize            = capacity;
m_nCount        = 0;
m_lruListTail    = NULL;
}

int get(int key) {
return -1;
map<int, Node *>::iterator it = m_lruMap.find(key);
if (it == m_lruMap.end()) //没有找到
return -1;
else {
Node *p = it->second;
//把节点移到链表的开头
pushFront(p);
}
}

void set(int key, int value) {
m_nCount ++;
}
else {
map<int, Node *>::iterator it = m_lruMap.find(key);
if (it == m_lruMap.end()){ //没有命中,将链表的最后一个节点删除
if (m_nSize == m_nCount) { //cache已满
}
else {
Node *p = m_lruListTail;
m_lruListTail->m_pPre->m_pNext = NULL;
m_lruListTail = m_lruListTail->m_pPre;
m_lruMap.erase(p->m_nKey);

p->m_nKey = key;
p->m_nValue = value;
p->m_pPre = NULL;
}
}
else {
Node *p = new Node(); //插入新的节点于头部
p->m_nKey = key;
p->m_nValue = value;
p->m_pPre = NULL;
m_nCount ++;
}
}
else { //命中，则将该命中的节点移至链表头部
Node *pCur = it->second;
pCur->m_nValue = value;
pushFront(pCur);
}
}
}

void pushFront(Node *pCur) {  //把节点移动到链表头部，时间复杂度O(1)
if (NULL == pCur)
return;
if (m_nCount == 1 || pCur == m_lruListHead)
return;
if (pCur == m_lruListTail) { //假如是尾节点
pCur->m_pPre->m_pNext = NULL;
m_lruListTail = pCur->m_pPre;
}
else {
pCur->m_pPre->m_pNext = pCur->m_pNext;
pCur->m_pNext->m_pPre = pCur->m_pPre;

}
}

void printCache() {
while (p) {
cout << p->m_nKey << ":" << p->m_nValue << " ";
p = p->m_pNext;
}
}

private:
int                    m_nSize;
int                    m_nCount;
map<int, Node *>    m_lruMap;
Node*                m_lruListTail;
};


STL

#include <iostream>
#include <hash_map>
#include <list>
#include <utility>
using namespace std;
using namespace stdext;

class LRUCache{
public:
LRUCache(int capacity) {
m_capacity = capacity ;
}
int get(int key) {
int retValue = -1 ;
hash_map<int, list<pair<int, int> > :: iterator> ::iterator it = cachesMap.find(key) ;
//如果在Cashe中，将记录移动到链表的最前端
if (it != cachesMap.end())
{
retValue = it ->second->second ;
//移动到最前端
list<pair<int, int> > :: iterator ptrPair = it -> second ;
pair<int, int> tmpPair = *ptrPair ;
caches.erase(ptrPair) ;
caches.push_front(tmpPair) ;
//修改map中的值
cachesMap[key] = caches.begin() ;
}
return retValue ;
}
void set(int key, int value) {
hash_map<int, list<pair<int, int> > :: iterator> ::iterator it = cachesMap.find(key) ;
if (it != cachesMap.end()) //已经存在其中
{
list<pair<int, int> > :: iterator ptrPait = it ->second ;
ptrPait->second = value ;
//移动到最前面
pair<int , int > tmpPair = *ptrPait ;
caches.erase(ptrPait) ;
caches.push_front(tmpPair) ;
//更新map
cachesMap[key] = caches.begin() ;
}
else //不存在其中
{
pair<int , int > tmpPair = make_pair(key, value) ;

if (m_capacity == caches.size()) //已经满
{
int delKey = caches.back().first ;
caches.pop_back() ; //删除最后一个

//删除在map中的相应项
hash_map<int, list<pair<int, int> > :: iterator> ::iterator delIt = cachesMap.find(delKey) ;
cachesMap.erase(delIt) ;
}

caches.push_front(tmpPair) ;
cachesMap[key] = caches.begin() ; //更新map
}
}

private:
int m_capacity ;                                               //cashe的大小
list<pair<int, int> > caches ;                                 //用一个双链表存储cashe的内容
hash_map< int, list<pair<int, int> > :: iterator> cachesMap ;  //使用map加快查找的速度
};


0
0 收藏

0 评论
0 收藏
0