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 我也这么想的,但是除了写代码其他的也不会
|