学步园

最晚使用缓存，简单的模拟题目，但要处理好边界条件。

测评地址：

http://oj.leetcode.com/problems/lru-cache/

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.

不做过多描述，直接贴代码。需要注意的是：链表的效率比数组的效率要高；类需要自行处理内存问题

class LRUCache{
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        this->count = 0;
        list = NULL;
        tail = NULL;
    }

    int get(int key) {
        if (count == 0) return -1;
        Node *p = list;
        bool exists = false;
        if (p->key == key)
        {
            if (p->next != NULL)
            {
                list = p->next;
                p->next = NULL;
                tail->next = p;
                tail = tail->next;
            }
            exists = true;
        }
        else
        {
            while (p->next)
            {
                if (p->next->key == key)
                {
                    tail->next = p->next;
                    p->next = p->next->next;
                    tail = tail->next;
                    tail->next = NULL;
                    exists = true;
                    break;
                }
                p = p->next;
            }

            if (!exists && p->key == key)
                exists = true;
        }

        return exists? tail->value: -1;
    }

    void set(int key, int value) {
        if (count == 0) 
        {
            list = new Node(key, value);
            tail = list;
            count = 1;
            return;
        }

        Node *p = list;
        bool exists = false;
        if (p->key == key)
        {
            if (p->next != NULL)
            {
                list = p->next;
                p->next = NULL;
                tail->next = p;
                tail = tail->next;
            }

            tail->value = value;
            exists = true;
        }
        else
        {
            while (p->next)
            {
                if (p->next->key == key)
                {
                    tail->next = p->next;
                    p->next = p->next->next;
                    tail = tail->next;
                    tail->next = NULL;
                    tail->value = value;
                    exists = true;
                    break;
                }
                p = p->next;
            }

            if (!exists && p->key == key)
            {
                tail->value = value;
                exists = true;
            }

            if (!exists)
            {
                Node *n = new Node(key, value);
                tail->next = n;
                tail = tail->next;
                count++;
            }

            if (count > capacity)
            {
                p = list;
                list = list->next;
                delete p;
                count--;
            }
        }
    }

    ~LRUCache() {
        while (list != NULL)
        {
            Node *p = list;
            list = list->next;
            delete p;
        }
    }
private:
    typedef struct node {
        int key;
        int value;
        node *next;
        node (int nKey, int nValue): key(nKey), value(nValue), next(NULL) {}
    } Node;

    Node *list;
    Node *tail;
    int capacity;
    int count;
};