老实说,LeetCode在我眼中的地位并不是很高,今天偶然刷了一下,没想到,写三个不会三个……

是我变菜了,还是本来就不是那么简单,不过就结论来说,LeetCode对现在的我来说有刷一刷的价值。

这是三道成套的问题。提供题号 141,142,287。

  1. 如何判断一个链表中是否存在环。不允许修改链表,不允许申请O(N)及以上的空间。
  2. 在第一个问题的基础上,找到环的入口点。限制相同。
  3. 给 n+1 个数字,范围是 [1,n] ,找出重复的那一个数字。只允许使用O(1)的空间,不允许修改数组,复杂度低于 $ O(N^2) $

先剧透一下,第三个问题和第二个问题是一样的……我特么……惊了。

直接说解法,第一个问题。创建两个指针,一个指针走两步,一个指针走一步,一直走直到走到尽头或者是两个指针重叠。两个指针重叠就是说明有环咯。否则没有……
神了,仔细思考一下,复杂度不会超过一次遍历。具体分析请自己思考。

而关于第二个问题,在第一个问题找到环的基础之上,使得一个指针还原到起始位置,两个指针每次都只走一步,必定会相遇,相遇点就是环的入口点。这个必然性画图划一下的话是很好理解的。
小小的文字解释一下,设还原后的指针为 a 指针,没有还原的指针为 b 指针,两个指针在经过相同的时间后仍然会到达当前b指针的位置。因为最最开始的时候快指针的速度是慢指针的两倍。
那么在起点到当前b指针的位置这段路程是重叠的。而重叠则是从环的入口处开始的。所以第一次相遇的位置就是环的入口处。

第三个问题,剧透了一般人都会秒懂……复杂度O(N) ,再说个二分的方法,唉,二分一直是我的弱项,这次的二分我也没有想到。二分答案,扫描数组,记录比当前答案小的数量,再比较……没了。挺简单的,但是我就是想不到。

不提供代码。