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 1cache->put(3, 3);//make (2,2) invalidint result2 = cache->get(2);//return -1cache->put(4, 4);//make (1,1) invalidint result3 = cache->get(1);//return -1int result4 = cache->get(3);//return 3int 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 cachepublic:    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();        }    }};

复杂度

运行时间