#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;}