Leetcode LRU Cache

这里的get和set操作都要求时间复杂度为O(1)。

思考了好久才想到要用一个双向链表数据结构来保存优先级列表，代表这里的LRU Cache。这个是本题的关键。

如果使用其他方法，例如堆操作，好像最多能使得get或者set其中一个是O(1)，一个需要O(lgn)，会超时。

因为这里需要利用key快速定位value，要频繁修改优先级，即也要利用key快速定位优先级，并能修改优先级。原来要考指针的熟练使用。

关键点：

1 建立一个新数据结构：双向链表，包含数据key和value

2 使用一个map，可以快速定位这个数据结构节点，这样可以快速得到value和修改节点指针

3 保存好头指针和尾指针，代表优先级最高和最低的节点

struct LRUstruct
{
	int value;
	int key;
	LRUstruct *pre;
	LRUstruct *next;
	LRUstruct(int v=0,int k=0, LRUstruct *p=NULL, LRUstruct *n=NULL)
		:value(v), key(k), pre(p), next(n){}
};

struct HeadTail
{
	LRUstruct head;
	LRUstruct tail;
	HeadTail(LRUstruct h, LRUstruct t):head(h), tail(t){}
};

class LRUCache{
public:
	int size;
	unordered_map<int, LRUstruct *> keyMap;
	HeadTail ht;

	LRUCache(int capacity):ht(LRUstruct(),LRUstruct())
	{
		size = capacity;
	}

	int get(int key) 
	{
		if (keyMap.empty() || !keyMap.count(key)) return -1;

		LRUstruct *ls = keyMap[key];
		//拆除ls
		ls->pre->next = ls->next;
		ls->next->pre = ls->pre;

		insertTail(ls);

		return ls->value;
	}

	void set(int key, int value) 
	{
		if (keyMap.empty())
		{
			LRUstruct *ls = new LRUstruct(value, key);
			ht.head.next = ls;
			ls->pre = &ht.head;
			ht.tail.pre = ls;
			ls->next = &ht.tail;
			keyMap[key] = ls;
			return;
		}

		if (keyMap.count(key))
		{
			LRUstruct *ls = keyMap[key];
			ls->value = value;
			//拆除ls
			ls->pre->next = ls->next;
			ls->next->pre = ls->pre;

			insertTail(ls);
		}
		else
		{
			if (keyMap.size() < size)
			{
				LRUstruct *ls = new LRUstruct(value, key);
				//插入后面
				insertTail(ls);
				//更新map表
				keyMap[key] = ls;

			}
			else
			{
				LRUstruct *p_tmp = ht.head.next;
				keyMap.erase(p_tmp->key);
				deleteHead();

				LRUstruct *ls = new LRUstruct(value, key);
				insertTail(ls);

				keyMap[key] = ls;
				delete p_tmp;
			}
		}
	}

	void insertTail(LRUstruct *ls)
	{
		ls->pre = ht.tail.pre;
		ht.tail.pre->next = ls;
		ls->next = &ht.tail;
		ht.tail.pre = ls;
	}
	void deleteHead()
	{
		ht.head.next = ht.head.next->next;
		ht.head.next->pre = &ht.head;
	}
};

Leetcode LRU Cache

原文：http://blog.csdn.net/kenden23/article/details/18693921