这是一个创建于 1716 天前的主题，其中的信息可能已经有所发展或是发生改变。
1 问：如何确定单向链表有环
答：快慢指针
2 问：找出环入口
答：用 hash 保存在循环列表，第一个重复的 hash 值就是入口。
其实我记得书上写的是先计算出环的大小，再用两个偏移指针，我害怕这样回答太标准答案了，让人怀疑。
——
所以，面试中遇到这种标准范文问题该如何回答呢？
 |
1
optional 2020-03-12 16:43:38 +08:00
面试官又不排斥刷过题。。。刷题本身就是学习啊。
当然如果只会用嘴描述，不能把思路转化成代码是另外一回事。 |
 |
2
Jacky23333 2020-03-12 16:43:50 +08:00 via Android
只要自己是真的理解这道题而不是纯粹背答案，这怕什么
|
 |
3
bbao 2020-03-12 16:44:17 +08:00
你不怕你说的答案面试官不会或者没转明白么？该给标准答案就给。
|
 |
4
hebin 2020-03-12 16:44:38 +08:00  3
"就这？“，反手就把话语权交给面试官 😄
|
 |
5
wyg1997 2020-03-12 16:47:04 +08:00
有点巧，我昨天刚做这题。。。不过第 2 个还有空间复杂度 O(1)的做法。
|
 |
6
tonytonychopper 2020-03-12 16:47:52 +08:00
不然你就梭哈，讲出所有解法，不然你就装傻，假装思考然后再回答。
|
 |
8
also24 2020-03-12 17:23:24 +08:00 via Android
想起来一件事儿，小时候有次转学，新学校教导主任丢给我一张数学卷子让我做。
诚实的我：老师这张卷子我做过。 教导主任换了一张给我。 诚实的我：老师这张卷子我也做过。 教导主任换了第三张卷子给我：你就做这张吧。 诚实的我：老师这张我恰好没做过。 |
 |
9
qpily 2020-03-12 18:37:34 +08:00
环出口不用那么麻烦，快慢指针相交之后，把其中一个指针移到入口，俩指针全都继续 1 步 1 步走，下个相交点就是环入口
|
 |
10
across 2020-03-12 18:44:13 +08:00
当然是答最优解。
面试官： 我早知道第一层会被你破解 现在我们进入第二层 空间 o(1)查入口有想法吗？ 这你也会？ 好，第三层，为什么这个方法刚好能定位到入口，如何推导的？ 答出来了？ 抱歉，我在第五层，所以我又想到了一个问题， 这个带环的链表怎么复制最高效？ |
|
11
qpily 2020-03-12 18:44:52 +08:00
相交时
慢指针 x 步 快指针 2x 步 环头 a 步 环长 b 步 相交说明快指针比慢指针快整整 n 圈，即 2x - x = nb，x = nb 也就是慢指针一共走了 nb 步，由于环头 a 步，所以实际上慢指针离入环口就差 a 步，补足 a 步就找到入环口了 |
 |
12
Jimmy2Angel 2020-03-12 18:46:58 +08:00 via Android
@hebin 反手给你两道 hard 变型
|
 |
15
8a9a09dw12 2020-03-13 09:23:14 +08:00
就这？
|
 |
16
p1094358629 2020-03-13 15:30:31 +08:00
业务部门,平时工作 80%时间在处理业务问题,导致技术积累不深,那么面试的时候又问一些算法类的问题很是头疼,所以有点放弃继续干开发的想法.
|
 |
17
1069401249 OP @p1094358629 我也这么想的，但是除了写代码其他的也不会
|
Select Language