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相遇的时候,所在的结点就是入口结点。

代码实现

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();         }     } };

复杂度

运行时间

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注