2019-11-18  82 views 评论

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

代码实现

复杂度分析

运行时间

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

其它题目详见Leetcode 141(环形链表),是本题的阉割版本,具体代码如下:

Leetcode 146:LRU缓存机制

题目描述

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

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

进阶

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

示例:

解题思路

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中直接添加即可。

具体可以见代码。

代码实现

复杂度

运行时间

给我留言

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: