Leetcode 142：环形链表2

题目描述

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

题目解析

《剑指offer》中也有此题，所以直接复制过来予以说明。

其实我的思路是把每个访问过的结点做标记，然后不断往下走后，遇到的第一个标记过的点，就是还的入口结点，如果没有遇到，则就不存在环，返回null。但是这种方法比较复杂，而且很难找到标志每个结点的特点在哪里。

所以可以这样考虑。如图4.1所示。
约束条件

图4.1 示意图

我们假设x为AB之间的距离，a为从b到c的距离（顺时针移动），c为环的长度。我们可以设置两个指针，一个快一个慢，然后快的是慢的速度的两倍。设快指针为f，慢指针为s，则当快指针和慢指针相遇的时候，s=x+mc+a，f=x+nc+a，m和n为某不同的常数，s=f。所以x=(n-2m)c-a=(n-2m-1)c+c-a。n-2m-1可为0。这里为了处理方便，省略前面这个类似于周期的东西，只留下c-a。c-a是什么？c-a就是图4.1中灰色的这条线。也就是说，AB之间的距离=灰色的线。这样，我们可以再重新将f这个指针（也可以是s）指向A，那么当f和s相遇的时候，所在的结点就是入口结点。

代码实现

ListNode *detectCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr){
            return nullptr;
        }
        ListNode *slow=head->next;
        ListNode *fast=head->next->next;
        while(fast!=slow)
        {
            if((fast->next!=nullptr)&&(fast->next->next!=nullptr)){
                fast=fast->next->next;
                slow=slow->next;
            }
            else{
                return nullptr;
            }
        }
        fast=head;
        while(fast!=slow)
        {
            fast=fast->next;
            slow=slow->next;
        }
        return slow;   
    }

复杂度分析

运行时间

时间复杂度O(n)，空间复杂度O(1)。

其它题目详见Leetcode 141（环形链表），是本题的阉割版本，具体代码如下：

bool hasCycle(ListNode *head) {
        if(head==nullptr||head->next==nullptr||head->next->next==nullptr)
        {
            return false;
        }
        ListNode *slow=head->next;
        ListNode *fast=head->next->next;
        while(fast!=slow){
            if((fast->next!=nullptr)&&(fast->next->next!=nullptr))
            {
                fast=fast->next->next;
                slow=slow->next;
            }
            else{
                return false;
            }
        }
        return true;
        
    }

Leetcode 146：LRU缓存机制

题目描述

运用你所掌握的数据结构，设计和实现一个LRU (最近最少使用)缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value)- 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例：

LRUCache* cache = new LRUCache(2);
cache->put(1, 1);
cache->put(2, 2);
int result1 = cache->get(1);//return 1
cache->put(3, 3);//make (2,2) invalid
int result2 = cache->get(2);//return -1
cache->put(4, 4);//make (1,1) invalid
int result3 = cache->get(1);//return -1
int result4 = cache->get(3);//return 3
int result5 = cache->get(4);//return 4

解题思路

LRU就是这样一个数据结构：其内部含有一个容量为cap的结构，也就是说里面有cap个元素，每一个元素是一个键值对。这个数据结构插入（put）和寻找（get）有以下特点：对于插入来说，如果这个键值对不存在，那么插入到这个元组里面，并放置在开头，如果存在则更新这个元组并放置在开头；对于寻找来说，如果没有找到，则返回-1，否则返回这个键值对的value，然后将这个键值对放在元组开头。

通过以上的功能，我们可以首先想到的基本数据结构有：哈希表（键值对）、栈（先入先出）。但是考虑到我们get之后也需要把这个键值对放在开头，所以使用栈的话操作并不方便，因为栈只能操作一头。所以我们可以使用哈希表。另外因为要求查找的时间复杂度为O(1)，所以更应该使用哈希表。
但是另外一点，我们还要求插入时间复杂度为O(1)，那么能实现该复杂度的基本数据结构只有链表。但是链表查找速度慢，那应该怎么操作呢？
这里可以考虑采用哈希表和链表相结合的方法进行操作。即对应于hash表每一个key值的value值其实指向了链表中的一个pair，这个pair的key值与hash表中的key值相等。于是无论是get还是put只需要对这个组合数据结构进行操作即可。

total

实际上这个类的数据成员一共三个：int类型的容量cap、pair类型的双向链表cache、int和list的unordered_map mymap。
所以对于构造函数来说，实际就是记录容量即可。
对于get来说，我们要判断是否存在，由于hashmap更适合做查找工作，所以就在hashmap里面查找，如果不存在，则返回-1，否则的返回key对应的value。但是不能直接这么返回，还需要将这个key-value置于mymap的开头，搜易需要做的就是获取到这个键值对，然后在链表list里面删除该键值对，然后将键值对插入到cache的开头，再领map[key]指向这个地址，最后再返回value的值。

对于put来说，也需要先判断该key是否存在，若存在，则直接更改value值并插入到cache头部，具体步骤与前面思路一致，不再重述；若不存在，则首先判断cache长度是否已经达到容量，若达到了，则删除链表cache中最后一个元素，并获取相应key值在mymap中予以删除，这样就空出来了空间。若还有空间，则直接在cache头部添加，然后在mymap中直接添加即可。

具体可以见代码。

代码实现


class LRUCache {
private:
    int cap;//capacity
    list<pair<int, int>> cache;//single key-value pair
    unordered_map<int, list<pair<int, int>>::iterator> mymap;
    //hash table:key to the position of(key,value) in cache
public:
    LRUCache(int capacity) {
        this->cap = capacity;
    }
    int get(int key) {
        auto it = mymap.find(key);
        //can not find key
        if (it == mymap.end())
            return -1;
        //find key and put it in the front of the list
        pair<int, int> visited = *mymap[key];
        cache.erase(mymap[key]);
        cache.push_front(visited);
        // update the position of (key,value) in cache
        mymap[key] = cache.begin();
        return visited.second;
    }
    void put(int key, int value) {
        //first if existed?
        auto it = mymap.find(key);
        //1--no
        if (it == mymap.end()) {
            //1.1 no position?
            if (cache.size() == cap) {
                auto lastPair = cache.back();
                int lastKey = lastPair.first;
                mymap.erase(lastKey);
                cache.pop_back();
            }
            //cache没满（或者已经删了一个位置）则可以直接添加
            cache.push_front(make_pair ( key, value));
            mymap[key] = cache.begin();
        }
        else
        {//key存在，则更改key并换到队头
            cache.erase(mymap[key]);
            cache.push_front(make_pair(key, value));
            mymap[key] = cache.begin();
        }
    }
};