Google 电面（准备二面求人品）

不是太懂诶， 楼主能给个例子或简单Po一下代码么？
感觉这意思好像是直接一个N次的循环就能找到了。。。

williamwjs 发表于 2015-10-6 07:11
同祝你好运！！！

先求cycle 吗？但可能有多个cycle，对每个a_init 都求？

又见紫风铃 发表于 2015-10-6 09:25
不是太懂诶， 楼主能给个例子或简单Po一下代码么？
感觉这意思好像是直接一个N次的循环就能找到了。。。

如果N很大很大，那么时间要求非常高，有环的话，最多k次就能找到了。

题看不太懂 能说说吗?

saberkun 发表于 2015-10-6 09:48
先求cycle 吗？但可能有多个cycle，对每个a_init 都求？

好像意思是a_init是input，对这个求就行了

nothingtrouble 发表于 2015-10-6 11:16
如果N很大很大，那么时间要求非常高，有环的话，最多k次就能找到了。

哦哦，所以建个hashset保存每次遇到的值，出现相同的时候就说明有环了，然后set有x个元素，只用找N % x次就行了？

补充内容 (2015-10-6 20:47):
不对，这样只能记录从头开始的cycle，还是得用hashtable记下重复开始的位置

lz的免题和我的一样啊http://www.1point3acres.com/bbs/thread-142154-1-1.html，我当时表现不好就一轮游了，lz加油哈，祝好运~

感觉是这个意思，大概写了下

1. class Solution:
   
2.     def bruteForce(self, nums, N, a_init):
   
3.         # O(N)
   
4.         if not nums: return None
   
5.         A = a_init
   
6.         for i in range(N):
   
7.             A = nums[A]
   
8. 
   
9.         return A
   
10. 
    
11.     def countinuousFinding(self, nums, N, a_init):
    
12.         # O(k)
    
13.         if not nums: return None
    
14.         occuredIndex = {}
    
15.         A = a_init
    
16.         occuredIndex[A] = 1
    
17. 
    
18.         cycleStart = None
    
19.         for i in range(1, N+1):
    
20.             A = nums[A]
    
21.             if A in occuredIndex:
    
22.                 cycleStart = occuredIndex[A]
    
23.                 break
    
24.             else:
    
25.                 occuredIndex[A] = i + 1
    
26. 
    
27.         if not cycleStart:
    
28.             return A
    
29.         else:
    
30.             N = (N - cycleStart + 1) % (len(occuredIndex) - cycleStart + 1)
    
31. 
    
32.         A = a_init
    
33.         for i in range(cycleStart - 1 + N):
    
34.             A = nums[A]
    
35.         return A

复制代码

hulahu 发表于 2015-10-6 08:08
看是简单， 楼主举个例子吧。

arr = [1, 2, 3, 4, 5, 6…]
N = 3
例子大概是这样的：

a_init = 0

A_0 = 0                                   
A_1 = arr[A_0] = arr[0] = 1
A_2 = arr[A_1] = arr[1] = 2
A_3 = arr[A_2] = arr[2] = 3
return 3

uuuouou 发表于 2015-10-6 20:25
lz的免题和我的一样啊http://www.1point3acres.com/bbs/thread-142154-1-1.html，我当时表现不好就一轮游了 ...

要是早点儿看见就好了