Leetcode题目解析（191118）：141&142&146
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相遇的时候，所在的结点就是入口结点。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
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（环形链表），是本题的阉割版本，具体代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
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) 时间复杂度内完成这两种操作？
示例：
|
1 2 3 4 5 6 7 8 9 10 11 |
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只需要对这个组合数据结构进行操作即可。
实际上这个类的数据成员一共三个：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中直接添加即可。
具体可以见代码。
代码实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
<br />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(); } } }; |
复杂度
![[leetcode]题目解析（190524）](http://www.yushuai.xyz/wp-content/themes/MyDream/timthumb.php?src=http://tech.yushuai.xyz/wzpt/largestrectangle.png&h=180&w=300&zc=1)
![[Leetcode]merge sorted array](http://www.yushuai.xyz/wp-content/themes/MyDream/img/random/22.jpg)
![[leetcode]populating next right pointers in each node](http://www.yushuai.xyz/wp-content/themes/MyDream/timthumb.php?src=https://dqhplhzz2008-1251830035.cos.ap-guangzhou.myqcloud.com/wp-content/uploads/2019/04/pnrpien1.png&h=180&w=300&zc=1)
