d********t 发帖数: 9628 | 1 array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ...
看起来就像找一个graph的最大loop.
要求O_n |
l*********8 发帖数: 4642 | 2 dfs, 用一个长度为N的visited数组
【在 d********t 的大作中提到】 : array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ... : 看起来就像找一个graph的最大loop. : 要求O_n
|
l*****a 发帖数: 14598 | 3 what is A_k
what is A_A_K
A[k], A[A[k]]?
and O_n
你这表示法很不通俗啊
【在 d********t 的大作中提到】 : array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ... : 看起来就像找一个graph的最大loop. : 要求O_n
|
d********t 发帖数: 9628 | 4 手机上打不出【】
【在 l*****a 的大作中提到】 : what is A_k : what is A_A_K : A[k], A[A[k]]? : and O_n : 你这表示法很不通俗啊
|
l*****a 发帖数: 14598 | 5 T家所有职位都要online test?
几道题,多长时间
【在 d********t 的大作中提到】 : array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ... : 看起来就像找一个graph的最大loop. : 要求O_n
|
l*****a 发帖数: 14598 | 6 走到一个已经用过的点就不能走了?
【在 d********t 的大作中提到】 : array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ... : 看起来就像找一个graph的最大loop. : 要求O_n
|
d********t 发帖数: 9628 | 7 不知道啊,也没说啥位子,两道题,60分。
跪了就不去想了。
【在 l*****a 的大作中提到】 : T家所有职位都要online test? : 几道题,多长时间
|
l*****a 发帖数: 14598 | 8 你这是什么复杂度?
【在 l*********8 的大作中提到】 : dfs, 用一个长度为N的visited数组
|
t**********h 发帖数: 2273 | 9 没说叫我做题啊
我现在手上叫做题的,都拖着,没搞。做题太枯燥了,
【在 d********t 的大作中提到】 : array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ... : 看起来就像找一个graph的最大loop. : 要求O_n
|
d********t 发帖数: 9628 | 10 估计我太弱所以叫做题哈哈,结果挂了。
【在 t**********h 的大作中提到】 : 没说叫我做题啊 : 我现在手上叫做题的,都拖着,没搞。做题太枯燥了,
|
|
|
k****s 发帖数: 16 | 11
这是正解。
【在 l*********8 的大作中提到】 : dfs, 用一个长度为N的visited数组
|
m****9 发帖数: 492 | 12 用图的遍历可做,找largest strongly connected component. 反正各个点都只有一个
degree,BFS/DFS都一样。
用python写个:
visited=[0 for i in range(n)]
max_loop_number = 0
k = 0
for i in range(n):
loop_number = 0
while visited[i] == 0:
loop_number += 1
visited[i]=1
i = A[i]
if loop_number > max_loop_number:
max_loop_number = loop_number
k = i
return k
每个点都只遍历一遍,时间theta(n) |
d********t 发帖数: 9628 | 13 哎,没想到用一个visited array
【在 m****9 的大作中提到】 : 用图的遍历可做,找largest strongly connected component. 反正各个点都只有一个 : degree,BFS/DFS都一样。 : 用python写个: : visited=[0 for i in range(n)] : max_loop_number = 0 : k = 0 : for i in range(n): : loop_number = 0 : while visited[i] == 0: : loop_number += 1
|
f*****e 发帖数: 2992 | 14 这好像是给fresh graduate做的。experienced还做online test?
【在 d********t 的大作中提到】 : 哎,没想到用一个visited array
|
c********p 发帖数: 1969 | |
f*****e 发帖数: 2992 | 16 A[i]存储可以跳的步数,如果i+A[i]已经visited了,或掉在0-N外就不算。
【在 c********p 的大作中提到】 : 没看懂
|
s*********n 发帖数: 191 | 17 这个。。。
两道题过不了70%的话, recruiter会觉得你太菜不会继续安排电面的。
【在 d********t 的大作中提到】 : 不知道啊,也没说啥位子,两道题,60分。 : 跪了就不去想了。
|
d********t 发帖数: 9628 | 18 第一题很简单,两题觉得不是同一个层次的。
【在 s*********n 的大作中提到】 : 这个。。。 : 两道题过不了70%的话, recruiter会觉得你太菜不会继续安排电面的。
|
r****7 发帖数: 2282 | 19 You should use undirected graph for SCC detection.
【在 m****9 的大作中提到】 : 用图的遍历可做,找largest strongly connected component. 反正各个点都只有一个 : degree,BFS/DFS都一样。 : 用python写个: : visited=[0 for i in range(n)] : max_loop_number = 0 : k = 0 : for i in range(n): : loop_number = 0 : while visited[i] == 0: : loop_number += 1
|
l********y 发帖数: 1068 | 20 T家是哪一家?
【在 d********t 的大作中提到】 : array A中含1到N-1的数,要求找到最长的S(k) = A_k, A_A_k ... : 看起来就像找一个graph的最大loop. : 要求O_n
|
|
|
d********t 发帖数: 9628 | 21 不是TMobile
【在 l********y 的大作中提到】 : T家是哪一家?
|
c********r 发帖数: 107 | |
a****o 发帖数: 25 | |
d********t 发帖数: 9628 | 24 while的i把for里的i重新赋值了有问题吗?
【在 m****9 的大作中提到】 : 用图的遍历可做,找largest strongly connected component. 反正各个点都只有一个 : degree,BFS/DFS都一样。 : 用python写个: : visited=[0 for i in range(n)] : max_loop_number = 0 : k = 0 : for i in range(n): : loop_number = 0 : while visited[i] == 0: : loop_number += 1
|