leecode 解题总结：146. LRU Cache

#include <iostream>#include <stdio.h>#include <vector>#include <string>#include <unordered_map>#include <fstream>#include <sstream>using namespace std;/*问题:Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following Operations: get and put.get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.put(key, value) - Set or insert the value if the key is not already PResent. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.Follow up:Could you do both operations in O(1) time complexity?Example:LRUCache cache = new LRUCache( 2  capacity  );分析:最近最少使用缓存。题目要求能够将最近最不经常使用的元素能够在缓存超出容量的条件下在O(1)时间内删除，如果缓存不存在，那么插入缓存：耗费的时间也是O(1)。查询某个缓存是否存在也是O(1)的时间。这是程序员面试金典上的一道题目。缓存采用链表设计，采用尾插法，新来的缓存插入到链表尾部，因此一直记录尾结点即可，保证插入时间是O(1)删除：如果超出缓存最大容量，则删除链表头部的结点，并更新新的头部结点，删除时间也是O(1)每个缓存存储在哈希map中，建立<value , Node*>的映射，则查找时，根据value查找如果发现找不到，再插入，则查找时间也是O(1)。注意：查找会改变链表的顺序，将查找过的元素放在链表尾部基于以下调用cache.put(1, 1);cache.put(2, 2);cache.get(1);       // returns 1cache.put(3, 3);    // evicts key 2cache.get(2);       // returns -1 (not found)cache.put(4, 4);    // evicts key 1cache.get(1);       // returns -1 (not found)cache.get(3);       // returns 3cache.get(4);       // returns 4输入:2(缓存大小)134输出:1, -1, -1, 3, 4-1, -1, -1, -1, 41, 2, -1, 3, 41, 2, 1, 3, 4关键:1缓存采用：哈希表+双向链表的方式，插入在尾部，如果超出最大容量，删除头部结点。注意：get操作时，如果缓存对应结点存在，需要将缓存移动到链表尾部（表示最近访问过了）2 Runtime Error Message:double free or corruption (fasttop): 0x0000000000c02e70 ***说明我需要注释掉析构函数，发现注释掉析构函数，还是报这个错误//把头结点取出，怀疑这里已经删除了结点_keyToNode.erase(_head->_key);//delete _head;//需要注释，否则会崩溃_head = NULL;也就是说哈希map会直接自己删除指针2 移动的时候这里错了node->_next = NULL;//易错，设置尾结点指向为空，否则后续连接会出错previousNode->_next = nextNode;nextNode->_previous = previousNode;_tail->_next = node;node->_previous = _tail;node->_next = NULL;//易错，设置尾结点指向为空，否则后续连接会出错_tail = node;*///由于经常要修改元素位置，需要双向链表struct MyListNode{	MyListNode():_next(NULL),_previous(NULL){}	MyListNode(int key , int value):_key(key),_value(value),_next(NULL),_previous(NULL){}	int _key;	int _value;	MyListNode* _next;	MyListNode* _previous;};class LRUCache {public:    LRUCache(int capacity) {        //给定容量		_capacity = capacity;		_keyToNode.clear();		_tail = NULL;		_head = NULL;		_currentSize = 0;    }	//key对应的结点存在，但是value不同，需要修改为正确的value，并移动到链表尾部；或者当前访问过key对应的某个结点，需要移动到链表尾部	//参数说明:如果value > 0，说明是需要更新结点的值，并移动到尾部;否则，直接移动到尾部	void updateNode(MyListNode* node , int value)	{		if(!node)		{			return;		}		if(value > 0)		{			node->_value = value;		}		//将该结点移动到链表尾部，修改node前面的结点指向后面的结点，修改node后面的结点指向前面的结点		MyListNode* previousNode = node->_previous;		MyListNode* nextNode = node->_next;		if(previousNode && nextNode)		{			previousNode->_next = nextNode;			nextNode->_previous = previousNode;			_tail->_next = node;			node->_previous = _tail;			node->_next = NULL;//易错，设置尾结点指向为空，否则后续连接会出错			_tail = node;		}		//如果当前结点没有前驱，说明当前结点为头结点，		else if(nextNode)		{			_head = nextNode;			nextNode->_previous =NULL;			_tail->_next = node;			node->_previous = _tail;			node->_next = NULL;			_tail = node;		}		//如果当前结点没有后继，说明当前结点就是尾结点，而尾结点存放最新访问的结点，因此无需修改		//如果当前结点没有前驱和后继，说明当前结点为链表头部，无需修改任何情况	}    	//查找元素，查找的元素要挪动到尾部变成最新的结点    int get(int key) {		//如果找到了，还要把该结点，放到链表尾部，那么就要获取其前驱结点和后继结点		if(_keyToNode.find(key) != _keyToNode.end())		{			MyListNode* node = _keyToNode[key];			//？是否需要修改映射，应该不需要			if(node)			{				updateNode(node , -1);				return _keyToNode[key]->_value;			}			else			{				return -1;			}		}		else		{			return -1;		}    }    	//先插入元素    void put(int key, int value) {		if(6 == key && 14 == value)		{			int a = 1;		}		//插入前先查找一下，key value是否已经存在，如果存在直接返回		int realValue = get(key);		//如果已经保存了，直接返回		if(realValue == value)		{			return;		}		//如果key对应的结点存在，但是value不对，那么其实代表的是一种新的缓存对，需要修改，并且将修改后的结点放在尾部		if(_keyToNode.find(key) != _keyToNode.end())		{			MyListNode* node = _keyToNode[key];			updateNode(node , value);		}		//这个结点完全不存在，插入		else		{			MyListNode* node = NULL;			//如果没有超出容量限制，插入在链表尾部			if(_currentSize < _capacity)			{				if(_tail)				{					node = new MyListNode(key , value);					_tail->_next = node;					node->_previous = _tail;					node->_next = NULL;					_tail = node;				}				//说明这个是第一个结点，需要作为头结点				else				{					node = new MyListNode(key , value);					_head = _tail = node;				}				_currentSize++;			}			//容量超出限制，删除头部结点			else			{				MyListNode* nextNode = _head->_next;				//如果当前结点存在后继结点				if(nextNode)				{					//把头结点取出，怀疑这里已经删除了结点					_keyToNode.erase(_head->_key);					//delete _head;//需要注释，否则会崩溃					_head = NULL;					nextNode->_previous = NULL;					_head = nextNode;					//将结点插入尾部					node = new MyListNode(key , value);					_tail->_next = node;					node->_previous = _tail;//别忘记设定尾结点指向前一个节点					node->_next = NULL;//易错，设置尾结点指向为空，否则后续连接会出错					_tail = node;				}				//当前结点不存在后继结点，说明只有头结点，那么就直接修改头结点的值为当前值即可				else				{					_keyToNode.erase(_head->_key);//要删除原来的键值对					_head->_key = key;					_head->_value = value;					_tail = _head;					node = _head;				}			}			_keyToNode[key] = node;		}    }	//清空，需要删除链表	~LRUCache()	{		if(_keyToNode.empty())		{			return;		}		for(unordered_map<int , MyListNode*>::iterator it = _keyToNode.begin() ; it != _keyToNode.end() ; it++)		{			//删除指针前，先判断指针是否为空			if(it->second)			{				delete it->second;				it->second = NULL;			}		}		_keyToNode.clear();	}public:	unordered_map<int , MyListNode*> _keyToNode;	MyListNode* _tail;	MyListNode* _head;	int _capacity;	int _currentSize;};void print(vector<int>& result){	if(result.empty())	{		cout << "no result" << endl;		return;	}	int size = result.size();	for(int i = 0 ; i < size ; i++)	{		cout << result.at(i) << " " ;	}	cout << endl;}vector<string> split(string& str , string& splitStr){	vector<string> result;	if(str.empty())	{		return result;	}	if(splitStr.empty())	{		result.push_back(str);		return result;	}	int beg = 0;	size_t pos = str.find(splitStr);	string partialStr;	while(string::npos != pos)	{		partialStr = str.substr(beg , pos - beg);		if(!partialStr.empty())		{			result.push_back(partialStr);		}		beg = pos + splitStr.length();		pos = str.find(splitStr , beg);	}	//防止 aa#aa，这种最后一次找不到	partialStr = str.substr(beg , pos - beg);	if(!partialStr.empty())	{		result.push_back(partialStr);	}	return result;}//程序需要读入put或get，已经对应的数据void readData(string& fileName , vector<string>& operationArr , vector< vector<int> >& dataArr,int& capacity){	ifstream inFile(fileName , ios::in);	if(!inFile)	{		cout << "can't open file:" << fileName << endl;		return;	}	const int MAXSIZE = 100000;	char str[MAXSIZE];	vector<string> lines;	while(!inFile.eof())	{		inFile.getline(str , MAXSIZE);		string line(str);		if(line.empty())		{			continue;		}		lines.push_back(line);	}	inFile.close();	//对第一行：操作进行分割，按照","分割	if(lines.empty() || lines.size() != 2)	{		cout << "data error" << endl;		return;	}	string operation = lines.at(0);	operationArr = split(operation , string(","));	//对输入数据进行分割, ,[105],[33,219]这种，应该先按照"]"分割，对于每个分割的部分，去除掉头部的",]",然后按照","分割	string data = lines.at(1);	vector<string> Words = split(data , string("]"));	if(words.empty())	{		cout << "words empty" << endl;		return;	}	int size = words.size();	string word;	//注意第一个元素是容量	for(int i = 0 ; i < size ; i++)	{		//将每个字符串去除头部的",["		word = words.at(i);		word = word.substr(2, word.length() - 2);		//分割出数据		vector<string> tempData = split(word , string(","));		if(i)		{			vector<int> data;			if(tempData.empty())			{				cout << "The " << i << " th vector is empty" << endl;				continue;			}			int len = tempData.size();			for(int j = 0 ; j < len ; j++)			{				int num = atoi(tempData.at(j).c_str());				data.push_back(num);			}			dataArr.push_back(data);		}		else		{			capacity = atoi(tempData.at(0).c_str());		}	}	//校验操作和数据的长度是否相等	if(operationArr.size() != dataArr.size())	{		cout << "operation size is not equal data size" << endl;		return;	}	size = operationArr.size();	for(int i = 0 ; i < size ; i++)	{		if(string("put") == operationArr.at(i) )		{			if(dataArr.at(i).size() != 2)			{				cout << "The " << i << " put group is wrong"  << endl;			}		}		else if(string("get") == operationArr.at(i) )		{			if(dataArr.at(i).size() != 1)			{				cout << "The " << i << " get group is wrong " << endl;			}		}	}}void process2(){	string fileName("data.txt");	int capacity = 0;	vector<string> operationArr;	vector< vector<int> > dataArr;	readData(fileName , operationArr , dataArr , capacity);	if(operationArr.empty() || dataArr.empty() || operationArr.size() != dataArr.size())	{		return;	}	int size = operationArr.size();	LRUCache cache(capacity);	int result = 0;	stringstream stream;	for(int i = 0 ; i < size ; i++)	{		if(70 == dataArr.at(i).at(0) && dataArr.size() == 2 && 98 == dataArr.at(i).at(1))		{			int a = 1;			cout << "是第" << i << "组数据崩溃" << endl;		}		if(string("put") == operationArr.at(i) )		{			cache.put(dataArr.at(i).at(0) , dataArr.at(i).at(1));		}		else if(string("get") == operationArr.at(i) )		{			result = cache.get(dataArr.at(i).at(0));			stream << result << ", ";		}	}	cout << stream.str() << endl;}void process(){	 vector<int> nums;	 int capacity;	 while(cin >> capacity)	 {		 LRUCache cache(capacity);		cache.put(1, 1);		cache.put(2, 2);		int r1= cache.get(1);       // returns 1		cache.put(3, 3);    // evicts key 2		int r2 = cache.get(2);       // returns -1 (not found)		cache.put(4, 4);    // evicts key 1		int r3 = cache.get(1);       // returns -1 (not found)		int r4 = cache.get(3);       // returns 3		int r5 = cache.get(4);       // returns 4		cout << r1 << ", " << r2 << ", " << r3 << ", " << r4 << ", " << r5 << endl; 	 }}int main(int argc , char* argv[]){	process();	getchar();	return 0;}