mayingjie116
BAN USERWe could reverse the two path and find the first different one. It will be easier.
- mayingjie116 January 06, 2015There is the same problem on LeetCode. Write some code and test it.
class LRUCache{
private:
list<int> _Cache; // node(value)
unordered_map<int, list<int>::iterator> _Map; // key->node
int _Capacity;
public:
LRUCache( int capacity ) {
_Capacity = capacity;
}
int get( int key ) {
/* Found */
if( _Map.find( key ) != _Map.end() ){
list<int>::iterator it = _Map[key];
int value = *it;
_Cache.erase( it );
_Cache.push_front( value );
_Map[key] = _Cache.begin();
return value;
}
/* Not found */
else{
return -1;
}
}
void set( int key, int value ) {
/* Found */
if( _Map.find( key ) != _Map.end() ){
list<int>::iterator it = _Map[key];
_Cache.erase( it );
}
/* Not found */
else{
if( _Cache.size() == _Capacity ){
list<int>::iterator it = _Cache.end(); // Past-the-end element
it--;
/* Find in _Map and delete it */
for( auto mapIt = _Map.begin(); mapIt != _Map.end(); ++mapIt ){
if( mapIt->second == it ){
_Map.erase( mapIt );
break;
}
}
_Cache.erase( it );
}
}
/* Insert new element */
_Cache.push_front( value );
_Map[key] = _Cache.begin();
}
};
Second one is not O(1) space cause you use recursion.
- mayingjie116 January 06, 2015