小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

Leetcode题目解析(191118):141&142&146

2019年11月18日 717点热度 0人点赞 0条评论

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

复杂度

运行时间

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode
最后更新:2019年11月18日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
[leetcode]题目解析(190422) Single Channel Noise Suppression based on WebRTC Python语言程序设计(第9周)知识点整理 2009 S.V Beijing Travel 23~25:杂谈 《鸟哥的Linux私房菜》(基础篇)笔记整理(第19章)Part.1 下学期微机课的第一篇日志
标签聚合
学习 算法 生活 鸟哥的linux私房菜 linux leetcode Java Python python学习 高中
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 9 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号